旅行推销员问题

维基百科，自由的百科全书

旅行推销员问题（Traveling Salesman Problem， 又称为旅行商问题、货郎担问题、TSP问题）是一个多局部最优的最优化问题：有n个城市，一个推销员要从其中某一个城市出发，唯一走遍所有的城市，再回到他出发的城市，求最短的路线。

目录 1 计算的复杂性 2 NP困难(NP-hard) 3 解法 4 參考來源 5 外部链接

[编辑] 计算的复杂性

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

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

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

[编辑] 解法

• 遗传算法
• 模拟退火
• 群集智能
• 局部搜索
• 多主体优化系统

[编辑] 參考來源

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

[编辑] 外部链接

• TSP源代码链接