论文部分内容阅读
近年来，物理学家尝试用统计力学的方法分析组合优化问题，并取得了很多好的结果，引起了数学家与计算机学家的广泛关注。Zecchina等人将统计力学的空穴方法(cavity method)应用于K-SAT问题，对K-SAT问题的相变现象进行了分析，并用统计方法给出了精确的阈值。独立集问题作为另一个NP难的组合优化问题，同样是理论计算机科学中的核心问题。我们同样利用空穴方法对独立集问题进行了分析，给出了相应的独立集问题的SP算法。这是一种结果很好的不完全算法，对于c较大(c>e)的情况，也可以得到很好的近似解。文章还给出了带权值独立集问题的模型和变形的SP算法。