信息传播算法(Information Propagation Algorithm)是一种基于因子图(Factor Graph)的消息传播算法,在求解组合优化问题时有良好的效果。该算法在因子图上表现出的良好收敛特性可用于图论问题的建模。警示传播(Warning Propagation Algorithm,WP)算法和置信传播(Belief Propagation Algorithm,BP)算法是两种相对较为基础的信息传播算法,本文通过对警示传播算法和置信传播算法原理进行分析,设计了求解图论问题(最小割问题、双目标最小生成树问题和最小顶点覆盖集问题)的信息传播算法,取得良好效果,具体地讲,研究内容如下:(1)求解最小点覆盖集的置信传播算法利用随机图的马尔可夫性原理,将随机图各个节点的度映射为置信传播算法的不协调赋值集中的元素。选取度最大的节点,使用信息迭代方程,调整参数p的值,使算法收敛。最后,取收敛的节点作为最小顶点覆盖集中的点.实验证明,此方法有效。(2)求解双目标最小生成树的警示传播算法借助于受限Boltzmann机模型,将一个随机无向图转换为因子图,把求解无向图上的双目标最小生成树问题映射为求解因子图上的对应问题,进而设计一种求解双目标最小生成树问题的警示传播算法。选取由随机数种子产生的若干随机数构造邻接矩阵,生成对应的无向图实例,数值实验结果表明,该算法优于同类算法。(3)求解最小割的警示传播算法借助隐马尔可夫模型将无向图转换为因子图,把最小割问题映射为求解因子图上的相应问题,进而设计一种求解最小割的警示传播算法。选取了几组随机无向图实例进行数值实验,实验结果表明,该算法在求解速度上优于同类算法。