旅行推销员问题
旅行推销员问题（通常称为TSP）是计算机科学和运筹学领域的一个经典算法问题。它的重点是优化。在这种情况下，更好的解决方案通常意味着一个更便宜、更短或更快的解决方案。TSP是一个数学问题。它最容易表达为一个描述一组节点位置的图。
旅行推销员问题是由爱尔兰数学家W.R.汉密尔顿和英国数学家托马斯-柯克曼在19世纪定义的。汉密尔顿的Icosian游戏是一个基于寻找汉密尔顿周期的娱乐难题。TSP的一般形式似乎是在20世纪30年代由数学家在维也纳和哈佛大学首先研究的，特别是卡尔-门格尔。Menger定义了这个问题，考虑了明显的蛮力算法，并观察到最近的邻居启发式的非最优性。
我们用信使问题来表示（因为在实践中这个问题应该由每个邮递员解决，反正也是由许多旅行者解决），任务是为已知对向距离的无穷多的点找到连接这些点的最短路线。当然，这个问题是可以通过有限的试验来解决的。而将试验次数推到给定点的排列组合次数以下的规则，则是未知的。首先应该从起点到最近的点，然后再到离此点最近的点，等等规则，在一般情况下，不能得出最短的路线。
普林斯顿大学的哈斯勒-惠特尼在不久后就提出了旅行推销员问题的名称。
William Rowan Hamilton
一个推销员想走访所有的城市，A、B、C、D，最好的办法是什么（机票最便宜，旅行时间最少）？
一个销售人员访问德国15个最大城市的最佳路线。所示路线是43,589,145,600条可能路线中最短的一条。
说明问题
旅行推销员问题描述了一个推销员必须在N个城市之间旅行。他并不关心旅行的顺序，只要他在旅途中每到一个城市一次，并在他最初的地方结束。每座城市都通过飞机、公路或铁路与其他邻近的城市或节点相连。每个城市之间的连接都有一个或多个权重（或成本）。成本描述了在图上穿越这条边的"难度"，可以用飞机票或火车票的成本来表示，也可以用边的长度或完成穿越所需的时间来表示。销售员既要把旅行成本，也要把他的旅行距离尽可能地降低。
旅行推销员问题是一大类"硬"优化问题的典型，多年来一直吸引着数学家和计算机科学家。最重要的是，它在科学和工程领域有应用。例如，在电路板的制造过程中，确定激光器钻数千个孔的最佳顺序是很重要的。这个问题的有效解决可以降低制造商的生产成本。
难度
一般来说，旅行推销员问题很难解决。如果有办法把这个问题分解成更小的组件问题，这些组件至少会和原来的问题一样复杂。这就是计算机科学家所说的NP-hard问题。
很多人都研究过这个问题。最简单（也是最昂贵的解决方案）是简单地尝试所有的可能性。问题是，对于N个城市，你有(N-1)种可能性。这意味着，对于只有10个城市，有超过18万种组合可供尝试（因为起始城市是确定的，所以在其余9个城市可以有换乘）。我们只计算一半，因为每条路线都有一条长度或成本相同的反向路线。9!/ 2 = 181 440
问题和答案
问：什么是旅行推销员问题？答：旅行推销员问题（TSP）是计算机科学和运筹学领域的一个经典算法问题。它的重点是优化，更好的解决方案往往意味着更便宜、更短或更快的解决方案。
问：TSP是如何表达的？
答：TSP最容易被表达为描述一组节点位置的图。
问：谁首先定义了TSP？
答：旅行推销员问题是由爱尔兰数学家W.R.Hamilton和英国数学家Thomas Kirkman在19世纪定义的。
问：在20世纪30年代，谁进一步研究了它？
答：在20世纪30年代，维也纳和哈佛的数学家卡尔-门格尔进一步研究了它。
问：哈斯勒-惠特尼不久后又介绍了什么？
答：普林斯顿大学的哈斯勒-惠特尼在其定义后不久就提出了 "旅行推销员问题 "这一名称。
问：在这种情况下，"更好的解决方案 "是什么意思？
答：在这种情况下，更好的解决方案通常意味着更便宜、更短或更快的解决方案。
问：门格尔在研究TSP时认为什么算法是明显的？
答:门格尔在研究TSP时认为明显的粗暴算法，并观察到使用近邻启发式并不总能得到最佳结果。
