旅行销售人员问题
销售人员需要访问一套城市来销售他们的货物。他们知道他们需要去的城市以及每个城市之间的距离。在销售人员中，销售人员应该曾经一旦访问每个城市，以便他们尽量减少他们的旅行时间，以便他们在他们的城市结束他们的旅程？
旅行推销员问题是计算机科学中一个非常古老的问题，它是计算机科学的一个延伸哈密顿回路问题．它有重要的意义复杂性理论和p与np问题因为它是一个NP完整问题．这意味着在多项式时间中找不到解决此问题的解决方案（它需要超时时间来计算答案）。换句话说，随着顶点的数量线性增加，解决问题的计算时间是指数增长的。
以下图像是由特定距离的边缘连接的城市网络的简单示例。Origin City也标明。
网络的城市
这是该网络的解决方案，它只有14个行驶的距离。推销员所需的任何其他路径将导致超过14的路径长度。
解决方案
关系图
旅行销售人员问题可以被建模为一个图．具体来说，它是典型的有向加权图。每个城市都是一个顶点，城市之间的每条路径都是一条边。每条边都有一个与之相关的权值，而不是距离。在该模型中，旅行销售人员问题的目标可以定义为找到一条访问每个顶点、返回到原顶点并使总权重最小的路径。
为此，可以在该模型上使用许多图算法。这样的搜索算法广度优先搜索(BFS)那深度首先搜索（DFS）,Dijkstra的最短路径算法然而，可以使用，但是，他们没有考虑到必须访问每个顶点的事实。
复杂性
旅行销售人员问题（TSP），NP完全的问题，令人惊叹的复杂解决。那是因为贪婪的方法是如此的计算密集。解决这个问题的贪婪方法是尝试每一个可能的路径，并查看哪一个是最快的。尝试这个概念问题，看看你是否有掌握要解决的努力。
为一个完全连接的地图 城市，旅行销售人员可以获得多少总路线？
有（n-1）！销售人员可以采取的总路径。
以这种方式解决这个问题所需的计算变得太快，无法成为合理的解决方案。如果这张地图只有5个城市，那么 ，或24个路径。但是，如果该地图的大小增加到20个城市，则会有 道路！
TSP的贪婪方法是这样的:
- 找到所有可能的路径。
- 找到每条路径的成本。
- 选择具有最低成本的路径。
贪心方法的另一个版本可能是:在算法的每一步，选择可能的最佳路径。这个版本可能会快一点，但它不能保证找到最好的答案，或者根本没有答案，因为它可能会撞到死胡同。
解决方案
对于像TSP这样的np -困难问题(NP-Complete问题的子集)，精确的解决方案只能在合理的时间内对较小的输入规模(包含少数城市的地图)实施。否则，我们能做的最好的方法就是提供一个启发式为了帮助问题以最佳方式向前移动。但是，这些方法不能被证明是最佳的，因为它们总是有某种缺点。
小输入大小
如上所述，在前一节，这个问题的贪婪方法具有复杂性 ．然而，有一些方法可以减少这种计算时间。
这持有KARP算法是最早的应用之一动态编程．它的复杂性远低于贪婪的方法 ．基本上这个算法的意思是最优路径上的每一个子路径本身也是最优路径。因此，计算一条最优路径就相当于计算许多更小的子路径并将它们相加。
启发式
启发式是一种对算法中可能的下一步进行排序的方法，希望能减少整个算法的计算时间。它们通常是某些属性(如完整性、准确性或精确度)与速度之间的权衡。对于旅行销售人员问题也存在试探法。
这个问题最简单的启发式是贪婪的启发式。这种启发式简单地说，在网络遍历的每个步骤中，选择最佳下一步。换句话说，始终选择您尚未访问过的最接近的城市。这种启发式似乎是一个很好的，因为它很简单直观，有时甚至在实践中使用，然而，有启发式被证明更有效。
Christofides算法是另一个启发式。它产生的重量最多是TSP最佳重量的1.5倍。这个算法需要找到a最小的生成树的网络。接下来，它为奇数度的城市创建匹配(意味着它们有奇数条边从它们出来)，并计算欧拉径，并转换回TSP路径。
特种TSP
即使通常不可能最佳地解决TSP问题，也存在TSP问题的情况可以如果有一定条件，就可以解决。
这metric-TSP是满足这种条件的TSP的一个例子：与城市A到城市B的距离小于或等于与城市A到城市C的距离加上城市C到城市B的距离。或者，
这是一个在现实世界中持有的条件，但它不能总是预期每个TSP问题都能持有。但是，通过这种不等式到位，近似的路径将不超过最佳路径的两倍。更好，我们可以将解决方案绑定到一个 近似用Christofide的算法．
这euclidean-TSP在TSP输入上有一个更严格的约束。它指出网络中的所有城市的边缘必须服从欧几里德距离．最近的研究表明，使用欧几里得最小生成树的逼近算法减少了欧几里得- tsp的运行时间，尽管它们也具有np困难。但在实践中，仍然使用更简单的启发式方法。
对P和NP的重要性
这P与NP问题是现代计算机科学的主要问题之一。它要求计算机能否在多项式时间内验证其解的每个问题也能在多项式时间内解决。例如，TSP不能在多项式时间内解决(至少目前理论化是这样)。然而，TSP可以在多项式时间内得到求解:给定一个图和一个整数x，判断是否有一条长度为x或小于x的路径．很容易看到给出了这个问题的建议答案，检查它是否小于或等于x很简单。
旅行销售人员问题，如其他问题的问题，对这场辩论非常重要。这是因为如果可以发现多项式时间解决方案，那么 ．就目前情况来看，大多数科学家认为 ．
应用程序
旅行销售人员问题有很多应用。最明显的是在运输领域。例如，规划送货路线或飞行模式，将极大地受益于突破这个问题或在p与np问题．
然而，同样的逻辑也可以应用于规划的许多方面。例如，在机器人技术中，规划在电路板上钻孔的顺序是一项复杂的任务，因为必须绘制大量的孔。
然而，TSP的最佳和最重要的应用来自这一事实，即它是NP完整问题。这意味着它的实际应用程序金额适用于应用程序任何问题是np-cleante。因此，如果TSP存在显着突破，这意味着这些完全相同的突破可以应用于NP-Complete类中的任何问题。