信息传播算法在支配集问题中的应用研究

作     者：刘子琳 

作者单位：北方民族大学 

学位级别：硕士

导师姓名：王晓峰;杨晓亮

授予年度：2022年

学科分类：07[理学] 070104[理学-应用数学] 0701[理学-数学] 

主      题：最小支配集问题 信息传播算法 线性规划 因子图 

摘      要：最小支配集（Minimum Dominating Set,MDS）问题是图论中的一个重要问题,在网络资源配置中有广泛的应用。城市交通网与通讯网建造、物流网络中心选址、连通设施选址、自适应网络设置等,都可归结为MDS问题。该问题的求解对于图着色、最大匹配、最大独立集、最小顶点覆盖、最大集合覆盖等问题的研究具有重要的理论指导意义。然而,该问题是一个经典的NP难问题,在P≠NP时,不存在求解该问题的多项式时间算法。目前,对于该问题的算法研究主要集中在精确算法和近似算法两个方面:精确算法的求解精度较高,而算法的运行时间较长;近似算法的运行时间较短,而通常无法获取问题的精确解。事实上,大量的实际问题对解的精度要求并不高,只需要解的精度达到某种近似度即可,这就佐证了近似算法的广泛应用。启发式方法是近似算法的一种有效策略,具有能在合理时间内求解复杂问题的特点。常用于求解MDS问题的启发式算法有:遗传算法、蚁群算法、禁忌搜索算法等,这类算法的一个共同的特征是容易陷入局部最优。信息传播算法是一种基于因子图的消息传递算法,当算法收敛时能够给出因子图中变量节点取值的边缘概率,大量的研究结果表明,该算法可用于有效求解组合优化问题。因此,本文探索用信息传播算法求解MDS问题。具体地讲,主要有以下几方面的研究工作:（1）将最小支配集问题映射为因子图模型,基于该因子图模型构建线性规划方程,根据线性规划方程的目标函数和约束方程构造信息传播算法的势函数;（2）设计求解最小支配集问题的信息传播算法,当算法收敛时,获得每个节点取值的边缘概率,利用边缘概率高概率地确定最小支配集节点,并在随机生成的无向图上进行数值实验,结果表明该方法有效。（3）设计基于信息传播算法的通信基站选址系统,为最小支配集问题给出了现实应用场景,为现有的通信行业提供帮助。