作者投稿和查稿 主编审稿 专家审稿 编委审稿 远程编辑

计算机工程 ›› 2012, Vol. 38 ›› Issue (13): 185-187,191. doi: 10.3969/j.issn.1000-3428.2012.13.055

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

基于组合拆分策略求解TSP的动态规划算法

杨忠程,徐新黎,叶双挺   

  1. (浙江工业大学计算机科学与技术学院,杭州 310023)
  • 收稿日期:2011-09-15 出版日期:2012-07-05 发布日期:2012-07-05
  • 作者简介:杨忠程(1989-),男,学士,主研方向:优化算法,车辆调度;徐新黎(通讯作者),副教授、博士;叶双挺,学士
  • 基金资助:
    国家自然科学基金资助项目(60874074);浙江省自然科 学基金资助项目(Y1090592)

Dynamic Programming Algorithm Based on Combination and Division Strategy for Solving TSP

YANG Zhong-cheng, XU Xin-li, YE Shuang-ting   

  1. (School of Computer Science and Technology, Zhejiang University of Technology, Hangzhou 310023, China)
  • Received:2011-09-15 Online:2012-07-05 Published:2012-07-05

摘要: 针对传统动态规划算法只能解决小规模旅行商问题(TSP)的不足,提出一种基于组合拆分策略的动态规划算法,通过5种不同的拆分策略将TSP序列拆分成若干段子序列,利用动态规划方法将子序列优化组合成新的TSP序列,重复该过程直到获得最优解散解。仿真结果表明,该算法能有效减小误差率,求解精确度较高,具有较低的计算复杂度和较好的稳健性。

关键词: 旅行商问题, 动态规划, 序列拆分, 序列组合, 组合优化

Abstract: Because of the deficiency that the typical dynamic programming algorithm can only solve the small-scale Traveling Salesman Problem(TSP), this paper proposes a new dynamic programming algorithm based on the combination and division. The whole sequence of TSP is divided into several parts by five strategies mentioned by the paper. Those parts are combined using the proposed dynamic programming algorithm to get a new better sequence. It repeats the process until it gets the optimum solution. Simulation results show that this algorithm with the higher solution accuracy can effectively reduce the error rate, and have low complexity and good robustness of the solution.

Key words: Traveling Salesman Problem(TSP), dynamic programming, sequence division, sequence combination, combinatorial optimization

中图分类号: