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

摘要

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