旅行商问题近似解——NP完全问题

旅行商问题

我们对于旅行商问题应该都不陌生，

我们从城市数较少的情况着手。假设只涉及两个城市，因此可供选择的路线有两条，

在这里插入图片描述

这两条路线相同还是不同 你可能认为这两条路线相同，难道从旧金山到马林的距离与从马林到旧金山的距离不同 吗？不一定。有些城市（如旧金山）有很多单行线，因此你无法按原路返回。你可能需要离开 原路行驶一两英里才能找到上高速的匝道。因此，这两条路线不一定相同

你可能心存疑惑：在旅行商问题中，必须从特定的城市出发吗？例如，假设我是旅行商。我 居住在旧金山，需要前往其他4个城市，因此我将从旧金山出发。

但有时候，不确定要从哪个城市出发。假设联邦快递将包裹从芝加哥发往湾区，包裹将通过 航运发送到联邦快递在湾区的50个集散点之一，再装上经过不同配送点的卡车。该通过航运发送 到哪个集散点呢？在这个例子中，起点就是未知的。因此，你需要通过计算为旅行商找出起点和 最佳路线。 在这两种情况下，运行时间是相同的。但出发城市未定时更容易处理，因此这里以这种情况为例。 涉及两个城市时，可能的路线有两条

• 1, 3个城市 现在假设再增加一个城市，可能的路线有多少条呢？ 如果从伯克利出发，就需前往另外两个城市

在这里插入图片描述

在这里插入图片描述

因此3个城市就有6条路线

• 我们再增加一个城市——弗里蒙特。现在假设从弗里蒙特出发。

List item

从弗里蒙特出发时，有6条可能的路线。这些路线与前面只有3个城市时计算的6条路线很像， 只是现在所有的路线都多了一个城市——弗里蒙特！这里有一个规律。假设有4个城市，你选择 一个出发城市——弗里蒙特后，还余下3个城市。而你知道，涉及3个城市时，可能的路线有6条。 从弗里蒙特出发时，有6条可能的路线，但还可以从其他任何一个城市出发。

可能的出发城市有4个，从每个城市出发时都有6条可能的路线，因此可能的路线有4 × 6 = 24条

涉及6个城市时，可能的路线有多少条呢？如果你说720条，那就对了。7个城市为5040条，8 个城市为40 320条

近似求解 对旅行商问题来说，什么样的近似算法不错呢？能找到较短路径的算法就算不错。在继续 往下阅读前，看看你能设计出这样的算法吗？ 我会采取这样的做法：随便选择出发城市，然后每次选择要去的下一个城市时，都选择还 没去的最近的城市。假设旅行商从马林出发

在这里插入图片描述

71英里也比较短了