《计算机应用研究》|Application Research of Computers

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

Phase transitions in random constraint satisfaction problem with various constraint tightness

免费全文下载 (已被下载 次)  
获取PDF全文
作者 赵春艳,范如梦,刘雅楠
机构 上海理工大学 理学院,上海 200093
统计 摘要被查看 次,已被下载
文章编号 1001-3695(2020)09-035-2739-05
DOI 10.19734/j.issn.1001-3695.2019.04.0120
摘要 提出了一个基于RB模型的随机约束满足问题即<i>p</i>-RB模型。该模型考虑了约束紧度的多样性,将所有约束按照不同的权重分成若干组,同一组具有相同的约束紧度,而相异组具有不同的约束紧度。用二阶矩方法严格证明了随着控制参数的不断增加,<i>p</i>-RB模型发生了精确的可满足性相变现象。数值实验表明该模型的有解概率经历了从1到0的突然转变,同时求解难度在相变区域达到高峰,表明该模型在相变区域能产生大量的难解实例。
关键词 约束满足问题; <;i>;p<;/i>;-RB模型; 约束紧度; 相变现象
基金项目 国家自然科学基金资助项目(11301339)
国家自然科学基金国际(地区)合作与交流项目(11491240108)
本文URL http://www.arocmag.com/article/01-2020-09-035.html
英文标题 Phase transitions in random constraint satisfaction problem with various constraint tightness
作者英文名 Zhao Chunyan, Fan Rumeng, Liu Yanan
机构英文名 College of Science,University of Shanghai for Science & Technology,Shanghai 200093,China
英文摘要 This paper proposed a random constraint satisfaction problem based on RB model named <i>p</i>-RB model, which took into account the diversity of constraint tightness. The model divided all constraints into several groups in accordance with different weights. The same group had the same constraint tightness, while the different group had different constraint tightness. This paper used the second moment method to prove that <i>p</i>-RB model existed exact satisfiability phase transition phenomenon as the control parameter increased. Numerical experiments show that the satisfiable probability of the model does undergo a sudden change from 1 to 0, and the solving hardness reaches the peak in the phase transition region, which indicates that a large number of intractable instances emerge in the phase transition region.
英文关键词 constraint satisfaction problem; < i> p< /i> -RB model; constraint tightness; phase transition
参考文献 查看稿件参考文献
 
收稿日期 2019/4/22
修回日期 2019/6/18
页码 2739-2743
中图分类号 TP301.5
文献标志码 A