摘要
较佳路径的求解问题事实上是货郎担近似算法的问题。现有算法实质上属于一种经典的单向增长的贪婪法,存在着改进的余地。本文提出一种改进的双向增长的贪婪算法,与经典算法相比,其策略有所增强,因而其结果得到进一步改善,更加接近于理想的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.
出处
《计算机应用与软件》
CSCD
北大核心
2001年第1期57-61,共5页
Computer Applications and Software
关键词
路径
货郎担问题
近似算法
贪婪法
Path Travelling salesman problem Approximition algorithm Greedy algorithm.
