旅行推销员问题

维基百科,自由的百科全书
跳转至: 导航搜索

旅行推销员问题(Travelling Salesman Problem, 又称为旅行商问题货郎担问题TSP问题)是一个多局部最优最优化问题:有n个城市,一个推销员要从其中某一个城市出发,唯一走遍所有的城市,再回到他出发的城市,求最短的路线。也即求一个最短的哈密顿回路

利用遗传算法解决的100个城市的旅行推销员问题

计算的复杂性[编辑]

最明显的算法就是穷举法,即寻找一切组合并取其最短。这种算法的排列数为n!(其中n为节点个数)。用动态规划技术,我们可以在O(n^2 2^n)[1]时间内解决此问题。虽然这仍然是指数级的,但要比O(n!)快得多。

NP困难(NP-hard)[编辑]

旅行推销员问题被证明是NP-困难的。

解法[编辑]

參考來源[编辑]

  1. ^ Held, Michal; Karp, Richard M., A Dynamic Programming Approach to Sequencing Problems, Journal of the Society for Industrial and Applied Mathematics, 1962, 10 (1): 196–210, doi:10.1137/0110015 

外部链接[编辑]