基于蚂蚁算法的中国邮路问题  

Chinese Postman Problem Based on Ant Algorithm

作　　者：于红斌[1] 薛占熬[1] 

机构地区：[1]河南师范大学计算机与信息技术学院,河南新乡453007

出　　处：《河南师范大学学报（自然科学版）》2011年第5期169-171,共3页Journal of Henan Normal University(Natural Science Edition)

基　　金：河南省重点科技攻关项目(092102210149);河南师范大学科研启动课题(0111660008)

摘　　要：针对中国邮路问题中先寻找奇数度结点,再进行奇数度结点之间路线添加的问题,引入了蚂蚁算法,通过其随机概率选择和最短路线激励策略,有效地解决了结点之间的最短路线的问题,避免了常规方法中必须先进行奇数度结点匹配的问题.算法易于实现,实验仿真表明算法耗时短、效率高.For Chinese postman problem,most of the methods must find odd-degree nodes first,then adding the route of them.Using ant algorithm,through its probability of random selection method and shortest route incentive strategy,not only shortest route can be found in the graph,but also the problem about matching odd-degree nodes in the conventional methods can be avoided.Algorithm is easy to implement,simulations show that it has less time-consuming and has high efficiency.

关 键 词：中国邮路问题 蚂蚁算法 随机概率选择 最短路线 

分 类 号：TP312[自动化与计算机技术—计算机软件与理论]