摘要:
提出通过寻找精确解的边获得旅行商问题(TSP)近似解的思想,并以该思想为指导,设计一种新的碰撞算法。对国际通用的TSPLIB中不同城市规模的数据进行测试表明,该算法可以得到与目前已知最优解或相同或相近的结果。该算法不仅可以计算小规模的TSP,而且同样适用较大规模的TSP。
关键词:
旅行商问题,
三角剖分,
组合优化,
碰撞算法
Abstract:
This paper proposes the thought of getting the edges of exact solution to access the approximate solution of the whole Traveling Salesman Problem(TSP). On the basic of the thought, a new algorithm called collision algorithm is designed. Experiments with the test data from internationally accepted TSPLIB in different cities and size show that the results got through the algorithm is the same or similar with current optimal solution. The algorithm can apply the TSP on a large scale as well as small scale ones.
Key words:
Traveling Salesman Problem(TSP),
triangulation,
combinatorial optimization,
collision algorithm
中图分类号:
邱伟星, 王舒榕, 程栋材, 邢晓伟, 陈春玲, 姜冬健. 求旅行商问题近似解的碰撞算法[J]. 计算机工程, 2011, 37(10): 284-286.
QIU Wei-Xing, WANG Shu-Rong, CHENG Dong-Cai, GENG Xiao-Wei, CHEN Chun-Ling, JIANG Dong-Jian. Collision Algorithm for Approximate Solution of Traveling Salesman Problem[J]. Computer Engineering, 2011, 37(10): 284-286.