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

来源：计算机应用研究杂志2020年第9期北京时间：

作者：赵春艳,范如梦,刘雅楠,

单位：上海理工大学理学院,上海200093；

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

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

基金资助：国家自然科学基金资助项目(11301339)；国家自然科学基金国际(地区)合作与交流项目(11491240108)；；