一个改进的较佳路径求解算法  

AN IMPROVED ALGORITHM FOR BETTERING PATHS PROBLEM

作　　者：仲盛[1] 周笑波[1] 谢立[1] 

机构地区：[1]南京大学计算机系,南京210093

出　　处：《计算机应用与软件》2001年第1期57-61,共5页Computer Applications and Software

摘　　要：较佳路径的求解问题事实上是货郎担近似算法的问题。现有算法实质上属于一种经典的单向增长的贪婪法,存在着改进的余地。本文提出一种改进的双向增长的贪婪算法,与经典算法相比,其策略有所增强,因而其结果得到进一步改善,更加接近于理想的Hamilton通路。算法的理论分析和实际测试数据都证实,改进是有效的。Bettering path is actually a problem of seeking an approximition algorithm for the travelling salesman problem. The original algorithm is a traditional greedy one, which adds nodes to the path in one direction.In this paper,an improved algorithm is presented,which adds nodes to the path in both directions. As is proved by theoretical analyses and testing data, a better result is obtained by the improved algorithm.

关 键 词：路径 货郎担问题 近似算法 贪婪法 

分 类 号：O224[理学—运筹学与控制论] TP301.6[理学—数学]