旅行销售人员问题

销售人员需要访问一套城市来销售他们的货物。他们知道他们需要去的城市以及每个城市之间的距离。在销售人员中，销售人员应该曾经一旦访问每个城市，以便他们尽量减少他们的旅行时间，以便他们在他们的城市结束他们的旅程？

旅行商问题是计算机科学一个非常古老的问题，是的一个扩展哈密​​顿回路问题。它有重要的影响复杂性理论和p与np问题因为它是一个NP完整问题。这意味着在多项式时间中找不到解决此问题的解决方案（它需要超时时间来计算答案）。换句话说，随着顶点的数量线性增加，解决问题的计算时间是指数增长的。

以下图像是由特定距离的边缘连接的城市网络的简单示例。Origin City也标明。

城市网络

这是该网络的解决方案，它只有14个行驶的距离。推销员所需的任何其他路径将导致超过14的路径长度。

解决方案

旅行销售人员问题可以被建模为一个图形。具体而言，它是指向一个典型，加权图。每个城市作为一个顶点和城市之间的每个路径是一个优势。代替距离的，每个边缘具有与之相关联的权重。在这个模型中，旅行商问题的目标可以被定义为找到一个路径访问每个顶点，返回到原来的顶点，并最大限度地减少总重量。

为此，许多图形算法可以在此模型中使用。像搜索算法广度优先搜索（BFS）那深度首先搜索（DFS）， 和Dijkstra的最短路径算法然而，可以使用，但是，他们没有考虑到必须访问每个顶点的事实。

旅行销售人员问题（TSP），NP完全的问题，令人惊叹的复杂解决。那是因为贪婪的方法是如此的计算密集。解决这个问题的贪婪方法是尝试每一个可能的路径，并查看哪一个是最快的。尝试这个概念问题，看看你是否有掌握要解决的努力。

对于一个完全连接地图 $N$城市，旅行销售人员可以获得多少总路线？

显示答案

有（n-1）！销售人员可以采取的总路径。

以这种方式解决这个问题所需的计算变得太快，无法成为合理的解决方案。如果这张地图只有5个城市，那么 $4！$，或24个路径。但是，如果该地图的大小增加到20个城市，则会有 $1.22 \ CDOT 10 ^ {17}$道路！

贪婪的方法TSP会是这样的：

1. 找到所有可能的路径。
2. 找到每条路径的成本。
3. 选择具有最低成本的路径。

贪婪方法的另一个版本可能是：在算法中的每一步，选择最好的路径。该版本可能走快一点，但它不能保证找到最佳答案，或在所有的答案，因为它可能进入了死胡同。

对于NP难问题（NP的完全问题的一个子集），如TSP，精确解只能在一个合理的时间量来实现对小尺寸输入（有几个城市的地图）。否则，我们所能做的最好的办法是提供一启发式为了帮助问题以最佳方式向前移动。但是，这些方法不能被证明是最佳的，因为它们总是有某种缺点。

小输入大小

如上所述，在前一节，这个问题的贪婪方法具有复杂性 $在！）$。然而，也有一些减少这种计算时间的方法。

这持有KARP算法是最早的应用之一动态编程。它的复杂性远低于贪婪的方法 $为O（n ^ 2 2 ^ n）的$。基本上，这个算法说的是，沿着最佳路径的每个子路径本身是一个最优路径。所以，计算最佳路径是相同的计算许多较小的子路径并添加在一起。

启发式

启发式是排名在削减计算时间，整个算法的希望的算法可能采取的一种方式。他们往往是一些属性的权衡 - 如完整性，准确性，或精度 - 有利于速度。启发式旅行商问题也同样存在。

这个问题最简单的启发式是贪婪的启发式。这种启发式简单地说，在网络遍历的每个步骤中，选择最佳下一步。换句话说，始终选择您尚未访问过的最接近的城市。这种启发式似乎是一个很好的，因为它很简单直观，有时甚至在实践中使用，然而，有启发式被证明更有效。

Christofides算法是另一种启发。它产生至多1.5倍的最佳权重为TSP。该算法涉及到寻找最小的生成树对于网络。其次，它创造了一个奇怪的程度的城市匹配问题（这意味着他们有奇数个边缘来他们出的），计算欧拉径和转换回一个TSP路径。

即使通常不可能最佳地解决TSP问题，也存在TSP问题的情况能够如果某些条件成立来解决。

这公制TSP是满足这种条件的TSP的一个例子：与城市A到城市B的距离小于或等于与城市A到城市C的距离加上城市C到城市B的距离。或者，

$distance_ {AB} \当量distance_ {AC} + {distance_ CB}$

这是一个在现实世界中持有的条件，但它不能总是预期每个TSP问题都能持有。但是，通过这种不等式到位，近似的路径将不超过最佳路径的两倍。更好，我们可以将解决方案绑定到一个 $3/2$近似使用Christofide的算法。

这欧几里德TSP在TSP输入上有一个更严格的约束。它指出网络中的所有城市的边缘必须服从欧几里德距离。最新进展表明，使用欧几里德最小生成树近似算法降低了欧几里德TSP的运行时间，尽管他们也是NP难问题。但在实践中，仍在使用较简单的试探。

这P对NP问题是在现代计算机科学的主要问题之一。它询问是否其解决方案可以在多项式时间内通过计算机来验证也可以在多项式时间内通过计算机来解决所有问题。TSP，例如，不能在多项式时间内（至少这就是目前理论）来解决。然而，TSP可以当它表述这样的多项式时间来解决：给定图和的整数，x，决定是否有长度为x的路径或小于x。很容易看到给出了这个问题的建议答案，检查它是否小于或等于x很简单。

旅行销售人员问题，如其他问题的问题，对这场辩论非常重要。这是因为如果可以发现多项式时间解决方案，那么 $p = np.$。既然这样，大多数科学家认为， $P \ NE NP$。

旅行商问题有许多应用。最明显的是那些在运输空间。规划送货路线或飞行模式，例如，将从突破immensly受益这方面的问题，或在p与np问题。

然而，这个相同的逻辑可以应用到规划的许多方面也是如此。在机器人，例如，计划在其中钻洞在一块电路板上的顺序是一项复杂的任务，由于孔的数量之多，必须绘制。

然而，TSP的最佳和最重要的应用来自这一事实，即它是NP完整问题。这意味着它的实际应用程序金额适用于应用程序任何问题是np-cleante。因此，如果TSP存在显着突破，这意味着这些完全相同的突破可以应用于NP-Complete类中的任何问题。