自旋玻璃模型的建立是为了解释无序磁性材料的一些奇异现象，这些材料通过对非磁性金属材料渗入少量磁性金属材料来得到的。铁磁与反铁磁性材料当中，磁矩自旋方向的分布是长程有序的，但是在自旋玻璃材料当中磁矩自旋方向的分布是短程有序长程无序的。因为这个磁矩方向的长程随机性，人们提出了许多自旋玻璃模型，并且利用平均场理论和复本方法对其进行了深入的研究。Viana-Bray模型出现以后，有限连通的自旋玻璃模型引起了人们的广泛的兴趣，此外空腔方法(Cavity method)出现以后，统计物理学家利用自旋玻璃的理论工具解决了越来越多的组合优化问题。除此之外，自旋玻璃理论在信息编码，复杂网络，神经网络等领域，也发挥了重要的作用。　　本文的研究主要集中在组合优化问题，我们将空腔方法应用到有向网络和无向网络中的最小支配点集问题上。在第一章，我们将要简要介绍自旋玻璃理论的基本概念，模型，介绍复本方法，空腔方法，并且引入求解置信度传播迭代方程的几种方式。在第二章中，我们介绍了无向网络中的最小支配点集(MDS)问题，全域掐叶探索算法(GLR)，贪心探索算法(Greedy)，复合探索算法(Hybreed)，消息传递算法(BP)的复本方法(RS)和概率图求解过程。我们用这四种算法研究了MDS问题并比较了它们的结果，我们还为GLR发展了一种解析方法叫核渗透(Core Percolation)理论，MDS问题在约束密度2.41处有一个相变点。在第三章中，我们介绍了有向网络中的最小支配点集(MDS)问题，全域掐叶探索算法(GLR)，贪心探索算法(Greedy)，复合探索算法(Hybrid)，消息传递算法(BP)的复本方法(RS)和概率图求解过程。我们用这四种算法研究了MDS问题并比较了它们的结果，我们还为GLR发展了一种解析方法叫核渗透(Core Percolation)理论，MDS问题在约束密度1.852处有一个相变点。