旅行推销员问题

旅行推销员问题描述了一个推销员必须在N个城市之间旅行。他并不关心旅行的顺序，只要他在旅途中每到一个城市一次，并在他最初的地方结束。每座城市都通过飞机、公路或铁路与其他邻近的城市或节点相连。每个城市之间的连接都有一个或多个权重（或成本）。成本描述了在图上穿越这条边的"难度"，可以用飞机票或火车票的成本来表示，也可以用边的长度或完成穿越所需的时间来表示。销售员既要把旅行成本，也要把他的旅行距离尽可能地降低。

旅行推销员问题是一大类"硬"优化问题的典型，多年来一直吸引着数学家和计算机科学家。最重要的是，它在科学和工程领域有应用。例如，在电路板的制造过程中，确定激光器钻数千个孔的最佳顺序是很重要的。这个问题的有效解决可以降低制造商的生产成本。

一般来说，旅行推销员问题很难解决。如果有办法把这个问题分解成更小的组件问题，这些组件至少会和原来的问题一样复杂。这就是计算机科学家所说的NP-hard问题。

很多人都研究过这个问题。最简单（也是最昂贵的解决方案）是简单地尝试所有的可能性。问题是，对于N个城市，你有(N-1)种可能性。这意味着，对于只有10个城市，有超过18万种组合可供尝试（因为起始城市是确定的，所以在其余9个城市可以有换乘）。我们只计算一半，因为每条路线都有一条长度或成本相同的反向路线。9!/ 2 = 181 440

• 使用分支和边界算法，可以找到问题的精确解决方案。目前可以为多达85,900个城市提供这种解决方案。
• 启发式方法使用一套指导规则来选择下一个节点。但是由于启发式方法的结果是近似的，所以它们并不总是能给出最优的解决方案，尽管高质量的可接受的启发式方法可以在完全粗暴地解决问题所需时间的一小部分内找到有用的解决方案。一个节点启发式的例子是对一个连接的节点"附近"有多少未访问的节点进行汇总。这可以鼓励销售员在转到图中的另一个自然簇之前，先访问一组相邻的节点簇。参见蒙特卡洛算法和拉斯维加斯算法