03-旅行商问题

9.2　旅行商问题

旅行商问题（traveling salesman problem）是最经典和最受关注的计算问题之一。推销商必须对地图上的所有城市只访问一次，行程结束时得返回起点城市。每个城市都与其他所有城市直接相连，推销商访问城市的顺序可以任意。请问推销商的行程的最短途径是什么？

旅行商问题可以被认为是一个图问题（参见第4章），城市就是顶点，城市之间的连接就是边。正如第4章所述，可能大家的第一直觉就是要查找最小生成树。不幸的是，旅行商问题的解决方案并没有这么简单。最小生成树是连通所有城市的最短路径，但它没有提供只访问一次所有城市的最短路径。

虽然看似简单，但没有算法能够快速求解城市数量任意的旅行商问题。“快速”是什么意思呢？它表示旅行商问题是所谓的 NP 困难问题（NP hard problem）。NP困难问题，即非确定性多项式时间复杂性难题（non-deterministic polynomial hard problem），是指求解此类问题不存在多项式时间内可完成的算法（花费的时间是输入数据量的多项式函数）。随着推销商要访问的城市数量不断增加，求解问题的难度将增长得异常迅速。求解20个城市要比求解10个城市困难得多。在合理的时间内，（在现有的最强知识条件下）不可能完全（最优）解出数百万计城市的旅行商问题。

注意 　旅行商问题的朴素解法（naive approach）的复杂度为O(n!)。原因将在9.2.2节讨论。不过在阅读9.2.2节之前，建议先看一下9.2.1节，因为朴素解法的实现能让其复杂度一目了然。