计算机工程2012，Vol.38Issue(13)：185-187,191,4.DOI:10.3969/j.issn.1000-3428.2012.13.055
基于组合拆分策略求解TSP的动态规划算法
Dynamic Programming Algorithm Based on Combination and Division Strategy for Solving TSP
摘要
Abstract
Because of the deficiency that the typical dynamic programming algorithm can only solve the small-scale Traveling Salesman Probiem(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分类
信息技术与安全科学引用本文复制引用
杨忠程,徐新黎,叶双挺..基于组合拆分策略求解TSP的动态规划算法[J].计算机工程,2012,38(13):185-187,191,4.基金项目
国家自然科学基金资助项目(60874074) （60874074）
浙江省自然科学基金资助项目(Y1090592) （Y1090592）
