最小支配集问题(MDS)是图论中的一个重要问题，在网络资源配置中有广泛的应用。上述问题是一个NP难问题，传统的启发式算法求解最小支配集问题时速度慢，且易于陷入局部最优解。将上述问题原有的无向图转化为对应的因子图，基于因子图构建最小支配集问题的线性规划方程，将方程代入图模型(GM)中，设计了一种求解最小支配集问题的置信传播算法。当算法收敛时，获得每个节点取值的边缘概率，利用边缘概率高概率地决定最小支配集节点。在随机生成的无向图上进行数值实验，结果表明，算法有效。
科研之友
微信
新浪微博
Facebook
分享链接
