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

• 作者: 叶双挺 徐新黎 杨忠程
• 来源期刊: 计算机工程
• 学科: 工学
• 关键词: 旅行商问题 动态规划 序列拆分 序列组合 组合优化
• 年，卷（期）: 2012,（13）
• 所属期刊栏目: 人工智能及识别技术
• 页码范围: 185-187,191
• 分类号: TP18
• 字数: 4389字
• 语种: 中文
• DOI: 10.3969/j.issn.1000-3428.2012.13.055

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	杨忠程	浙江工业大学计算机科学与技术学院	1	10	1.0	1.0
2	徐新黎	浙江工业大学计算机科学与技术学院	48	725	15.0	25.0
3	叶双挺	浙江工业大学计算机科学与技术学院	1	10	1.0	1.0