检索
E-mail
RSS
作者投稿和查稿 主编审稿 专家审稿 编委审稿 远程编辑

计算机工程 ›› 2011, Vol. 37 ›› Issue (10): 149-151.

• 人工智能及识别技术 • 上一篇    下一篇

基于学习自动机的最小连通支配集算法

赵学锋，王秀花，杨海斌，张贵仓   

  1. (西北师范大学数学与信息科学学院，兰州 730070)
  • 出版日期:2011-05-20 发布日期:2011-05-20
  • 作者简介:赵学锋(1965－)，男，副教授、硕士，主研方向：网络算法设计与分析；王秀花、杨海斌，硕士研究生；张贵仓，教授、博士
  • 基金项目:
    甘肃省科技攻关计划基金资助项目

Minimum Connected Dominating Set Algorithm Based on Learning Automata

ZHAO Xue-feng, WANG Xiu-hua, YANG Hai-bin, ZHANG Gui-cang   

  1. (College of Mathematics and Information Science, Northwest Normal University, Lanzhou 730070, China)
  • Online:2011-05-20 Published:2011-05-20

PDF

1099

被引次数

11 | 3

摘要： 为解决连通支配集的最小化问题，提出基于改进的分布式学习自动机的近似算法，在分布式学习自动机按随机选择进行深度搜索的基础上考虑回溯策略。该算法构造的是网络中的一棵支配树，只需要节点的局部信息。在网络建模图——单位圆盘图上对支配树性质进行分析和模拟实验。实验结果表明，与现有算法相比，该算法能得到更优的最小连通支配集。

关键词: 最小连通支配集, 学习自动机, 单位圆盘图, 支配树, 深度优先搜索

Abstract: Connected Dominating Set(CDS) has a wide range of applications in wireless networks. For the Minimal Connected Dominating Set(MCDS) problem, an approximation algorithm is presented based on an improved Distributed Learning Automata(DLA). The proposed algorithm considers not only the deeper exploration with random selections, but also the strategy of backtracking. The dominating tree is constructed using only neighborhood information, and some properties of the dominating tree are analyzed on Unit Disk Graph(UDG) to model networks. Experimental results on those graphs show the superiority of the proposed algorithm over the existing algorithms in terms of the MCDS size.

Key words: Minimum Connected Dominating Set(MCDS), Learning Automata(LA), Unit Disk Graph(UDG), dominating tree, Depth-First Search(DFS)

中图分类号: