不同紧度下约束满足问题的相变现象

• 作者: 刘雅楠 范如梦 赵春艳
• 来源期刊: 计算机应用研究
• 关键词: 约束满足问题 p-RB模型 约束紧度 相变现象
• 年，卷（期）: 2020,（9）
• 所属期刊栏目: 算法研究探讨
• 页码范围: 2739-2743
• 页数: 5页
• 分类号: TP301.5
• 语种: 中文
• DOI: 10.19734/j.issn.1001-3695.2019.04.0120

摘要

提出了一个基于RB模型的随机约束满足问题即p-RB模型.该模型考虑了约束紧度的多样性,将所有约束按照不同的权重分成若干组,同一组具有相同的约束紧度,而相异组具有不同的约束紧度.用二阶矩方法严格证明了随着控制参数的不断增加,p-RB模型发生了精确的可满足性相变现象.数值实验表明该模型的有解概率经历了从1到0的突然转变,同时求解难度在相变区域达到高峰,表明该模型在相变区域能产生大量的难解实例.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	赵春艳		6	17	1.0	4.0
2	范如梦		2	0	0.0	0.0
3	刘雅楠		1	0	0.0	0.0