旅行推销员问题

旅行推销员问题 （正體）

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

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

计算的复杂性

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

NP困难(NP-hard)

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

解法

• 遗传算法
• 模拟退火
• 群集智能
• 局部搜索

外部链接

• TSP源代码链接

Why are we here?
All text is available under the terms of the GNU Free Documentation License
This page is cache of Wikipedia. History