Day 26：旅行推销员问题(TSP)

之前在贪婪演算法的文章中有提到，现实生活中并不是所有问题都能用演算法快狠准地解决，有些困难的问题只有非常慢的解法。旅行推销员问题(travelling salesman problem)就是这样的一个问题。

旅行推销员问题是：给定一系列城市及任两个城市间的距离，找出造访每个城市一次并回到起始城市的最短路线。

最直接的解法就是把所有可能的路线都列出来，再比较哪一个路线是最短的。我们会发现：

两个城市的路线数：2

三个城市的路线数：3个不同的起点 * 两个城市的路线数 = 6

四个城市的路线数：4个不同的起点 * 三个城市的路线数 = 24

也就是以n个城市来说，会有n!条路线，找出其中的最短路线就需要O(n!)，即所谓阶层时间(factorial time)。如果对大O符号的图有印象的话，O(n!)的线正是最陡的那一条，代表执行时间随着输入n变大会急遽增加，光是十个城市，路线数就会增加到3628800。这样的演算法已经不是慢可以形容，往往不是合理范围的资源可以进行的方法。

除了暴力解法外，也可以尝试用上一回提到的动态规划。例如选定任一个城市为起点，从小范围开始，计算并记录起点与任一个城市的最小距离、任两个城市的最小距离...这样作法的执行时间为会是O(n²2^n)，虽然比阶层时间快，仍然是指数时间(exponential time)，也就是随着n增加执行时间会指数成长。

旅行推销员问题是个NP困难问题，目前还没有快速的演算法可以解决。这点可能有些令人好奇，毕竟这个问题看起来那麽简单，而且还跟我们讨论过的Dijkstra演算法或最小生成树的问题非常相像。

事实上我们也可以像Dijkstra演算法一样，用贪婪演算法来解TSP。例如以任意城市为起点，接着不断选择距离最近的城市，直到去过所有的城市。这样执行时间缩短很多，但也可以想像得出的解不会永远正确。

下一回会写到所谓困难问题的意义，以及如何面对困难问题。