论文部分内容阅读
RB模型是一种随机约束满足问题模型。基于RB模型产生的难解实例被广泛应用于算法竞赛和理论研究。本文从如下两个角度研究了RB模型的难解性。
1.首先，本文研究了RB模型的约束图g(?)，并给出了它与经典随机图模型gn，p的关系。在此基础上，本文研究了两种结构分解方法：树分解和铰链分解，分析了RB模型下树宽度和铰链宽度。文献中作者证明了RB模型下的树宽度渐近的等于变量个数，因此采用树分解不能降低计算RB模型的复杂度。本文中给出了简化的证明，并且将结果推广到了约束超图的情况。关于RB模型下的铰链宽度，本文首次给出了下界并进行了严格的证明。本文的研究结果表明，RB模型的铰链宽度渐近的等于约束个数，因此采用铰链分解也不能降低计算RB模型实例的难度。
2.其次，本文研究了线性规划求解RB模型的性能。通过实验表明，随着实例规模的增大，线性规划能够精确求解的RB模型实例的参数p是趋近于0的。这意味着线性规划只能求解非常平凡的实例。
这两方面的结果不仅证明了RB模型的难解性，也揭示了结构化分解方法以及线性规划在求解困难实例时的不足之处。