论文部分内容阅读
自旋玻璃模型的建立是为了解释渗入杂质的金属中的磁化现象,人们陆续提出了很多理论模型,并且利用复本方法对其进行了深入的研究。近年来,随着Viana-Bray模型的提出,有限连通的自旋玻璃模型进入了人们的视野,同时由于空腔方法(cavity method)的出现,统计物理学家利用自旋玻璃的理论工具解决了越来越多的组合优化问题。当然除此之外,在复杂网络、神经网络、信息编码等领域,统计物理的方法也发挥了重要的作用。
本文的研究主要集中在组合优化问题,我们将空腔方法应用到包括随机K-SAT问题以及顶点覆盖问题中,以期对其解空间的结构和性质有更深刻的理解。在第一章中,我们将简要介绍自旋玻璃理论的基本概念、模型,介绍复本方法以及空腔方法,并且引入求解空腔方法迭代方程的几种方式。在第二章中,我们通过相空间的耦合来研究随机K-SAT问题在难解区间的解空间性质,我们提出了通过引入耦合的一种新的研究方法,通过信念传播方程和模拟退火方法的计算,发现了一个各态历经破缺相变,并将其与由温度引发的相变进行了比较。在第三章中,我们关注组合优化问题空腔方法解的稳定性。我们分别计算了复本对称层次、一阶复本对称性破缺层次的情况,发现对于顶点覆盖问题,如连通度较大,当温度不太低时,其物理性质可以由一阶复本对称性破缺的空腔理论完整描述,但当温度进一步降低时,需要更高阶的复本对称性破缺理论。