摘要: 为解决连通支配集的最小化问题,提出基于改进的分布式学习自动机的近似算法,在分布式学习自动机按随机选择进行深度搜索的基础上考虑回溯策略。该算法构造的是网络中的一棵支配树,只需要节点的局部信息。在网络建模图——单位圆盘图上对支配树性质进行分析和模拟实验。实验结果表明,与现有算法相比,该算法能得到更优的最小连通支配集。
中图分类号:
赵学锋, 王秀花, 杨海斌, 张贵仓. 基于学习自动机的最小连通支配集算法[J]. 计算机工程, 2011, 37(10): 149-151.
DIAO Hua-Feng, WANG Xiu-Hua, YANG Hai-Bin, ZHANG Gui-Cang. Minimum Connected Dominating Set Algorithm Based on Learning Automata[J]. Computer Engineering, 2011, 37(10): 149-151.