● 摘要
对约束满足问题 (CSP) 相变现象的研究起源于数学、统计物理和计算机科学三个学科. 相变现象是指在一定的约束条件下, 存在一个临界值, 使得在该点附近, CSP 经历由几乎确定有解到几乎确定无解的突变现象. 这种现象在自然界广泛存在, 比如物质的三态变化, 它反映了从量变到质变的内在规律. 经过大量研究, 人们发现在相变现象发生的区域存在最难解的实例, 正是这些难解实例决定了 ~NP 完全问题的难解性. 对相变现象的研究能加深对~NP 完全问题难解的本质的理解, 进而据此构造出更为高效的求解算法. 本文主要对约束满足问题中的相变现象进行研究, 全文分为六章. 第一章, 介绍了约束满足问题的研究背景, 给出了本文所研究的几个特殊的~CSP 模型的基本定义以及主要的研究工具. 第二章, 用局部最大可满足赋值的方法研究了随机 ~$(2+p)$-SAT ($0
相关内容
相关标签