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

摘要：

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

关键词：约束满足问题、p-RB模型、约束紧度、相变现象

所属期刊栏目：37

分类号：TP301.5(计算技术、计算机技术)

资助基金：国家自然科学基金资助项目;国家自然科学基金国际地区合作与交流项目

在线出版日期：2020-10-26（万方平台首次上网日期，不代表论文的发表时间）

页数：共5页

页码：2739-2743