和本主题中的其他人一样，我在大学期间为NP完全问题构建了一个解决方案（这是为朋友做的旁边的项目）-一个调度程序。当我同意解决他的问题时，我并不知道NP完全是什么。后来我意识到我想出了一些相当不错的启发式算法来解决这个问题 - 但当然，真正的诀窍是知道何时告诉用户没有解决方案，并且他们已经过度限制了问题。

这是将我最终的理论课程与现实世界结合起来的一种绝佳方式。

再次强调，对于寻找并实施理想解决方案成本高昂的真实世界应用而言，启发式和"足够接近"通常是可以接受的。

我曾被分配写一个程序，用“squiggle”（不自交的曲线）相对均匀地填充一个矩形区域。我的第一次尝试是在矩形区域内生成随机点，并尝试找到它们的游览路径（不一定是绝对最短的）。不幸的是，这种方法并没有很好地工作，我放弃了它。

但我最终解决了这个问题：

将此翻译成中文：

我的成功方法与TSP无关，但出于好奇，我将对其进行概述：

从一条线段开始。现在循环：如果一条线段“太长”，就将其分成两部分。每个点随机移动一点，但要让点相互排斥。当进展不大时，结束循环。还有一些细节，但希望你能理解这个想法。

当然，这会产生一个角形路径（这是可以接受的），但很容易将拐角变成平滑的弧线。

是的，我确实保留了那段代码。

知道一个问题是 NP-hard 有助于排除涉及解决该问题的解决方案。每当您看到TSP（或任何其他 NP-hard 问题）在非平凡规模的问题中出现，您就会知道您正在走向错误的道路。您不仅知道它，而且知道为什么，可以自信地告诉您的老板/队友/任何人。

话虽如此，http://en.wikipedia.org/wiki/CONCORDE 显示：

Concorde has been applied to problems of gene mapping,[1] protein function prediction,[2] vehicle routing,[3] conversion of bitmap images to continuous line drawings,[4] scheduling ship movements for seismic surveys,[5] and in studying the scaling properties of combinatorial optimization problems.[6]

是的，我在地理藏宝应用程序中使用它进行路线规划。

目前它使用两点之间的直线距离，但应该正确地（当我有时间时）使用道路来计算两点之间的距离。

http://code.google.com/p/gpsturbo/ 的翻译是：

我个人从未使用过它，但除了钻孔电路板外，另一个应用是如果您想去许多不同的地方，比如销售吸尘器。 您可以使用问题的解决方案来决定以最便宜的方式访问每个地方一次。 我从未亲自使用过它，但除了钻孔电路板之外，另一个应用是，如果您想前往许多不同的地方，比如销售吸尘器。 您可以使用问题的解决方案来确定一次性访问所有地方的最便宜方式。

大多数情况下，您不希望使用解决NP-Complete/Hard问题的算法。您只需要一个足够好的算法。这些通常基于启发式算法，并给出合理的近似值。

我遇到了一個獨立集問題（NP完全問題），但我發現了一個貪心算法，在絕大多數情況下給出了相當不錯的結果，並且運行時間高效。

TSP是NP难问题中的“hello world”。在其纯规范形式中，你不会经常在自然界中发现它（不包括像这样的演示），但许多NP完全问题都与TSP有关或基于TSP，例如：

• Vehicle routing (includes supply truck routing)
• Airline/Flight routing
• Train routing
• Ski slope plow machine routing

Each of these has extra, domain specific constraints, which make them harder to solve. So TSP is a good introduction to NP complete problems, to understand their nature.

许多类型的优化订单，例如拼车接送、UPS包裹送货等，只要节点遍历要求可以用一维努力（如时间或距离）来表达。

现实生活中很少有问题与数学课上学到的东西相符。这些问题被简化和抽象化，以便您可以看到数学而不会被细节分散注意力。正如您提到的，最好的大型TSP的现实生活例子实际上并没有涉及任何旅行推销员：它涉及安排需要执行作业的机器，其中包括具有序列相关设置时间的机器。其中包括一个手臂将工具移动到不同的站点的机器，还包括一些涂漆应用程序（红色->橙色->黄色比红色->黄色->橙色更容易）。在X射线晶体学中也有一些应用程序，您必须将晶体样品定向到几个不同的角度。

因为人类通常能够在具有20-60个节点的地图上与大多数算法并驾齐驱或更好地解决TSP问题，因此很少让计算机解决问题。当成本足够高时，计算机比人类提高1-2%的价值可能超过执行计算的成本。如果路线不变，则可以证明花费一些时间对其进行优化。这在集成电路设计中很常见。

航空公司的旅游网站在显示航班列表及每条路线价格时，使用了特殊版本的TSP问题。其不同之处在于，该版本是以成本为优化目标，而不是距离，并且当然也没有访问每个城市的要求！比如您要从LGA飞往LAX，可能有大约半打直达航线和无限多的其他路线可供选择。系统可能会建议LGA->ORD->LAX或LGA->DWF->LAX的路线。人工手动定价的能力比网络旅游网站搜到的低价航班要强，而人们通常不想超过两次连接，但对于一个给定航班的连接数量并没有上限。

我已经用它来解决我的旅行推销员iPhone游戏的路线问题。有趣的是，人们非常擅长解决最短路径，但不擅长解决最长路径。最长和最短路径具有相同的复杂性，但人们似乎受过训练，能够比计算机更快更好地找到最短路径。

该公司基于改进后的TSP算法。

https://www.mobicorp.com/ 的中文翻译为：https://www.mobicorp.com/。

他们会安排有线电视安装人员和修理工在纽约市周围安排工作，同时面临着其他的问题。

On my first job we built a home care scheduling application.
We solved the TSP problem with some non linear time constraints and with an additional non linear cost function.
We used a non optimal solver to solve the problem.

难道不是谷歌地图（和所有其他基于地图的路线规划软件）都在使用一种旅行商问题算法来解决行车方向吗？

我据我所知还没有使用TSP，但我已经开发过许多自主机器人来穿越迷宫。所以我想知道TSP是否可以用于解决迷宫问题。