我在大学学习过TSP，涉及到NP完备性的概念。但我从未遇到过实际问题需要使用它。通过一些研究，发现它曾被用于寻找最便宜的路径，以便移动电路板钻头进行孔加工。这就是我所能找到的所有信息。
你是否正在使用它？TSA还有哪些其他实际应用呢？
14个回答
8
我曾经被赋予编写一个程序以相对均匀地用“squiggle”填充矩形区域的任务——这是一条不自交的曲线。我首次尝试的方法是在矩形内生成随机点并尝试找到它们的路径（不一定是绝对最短的）。不幸的是，这种方法并没有很好地工作，所以我放弃了它。
但最后我还是解决了这个问题：
我的成功方法与TSP无关，但为了让你好奇，我会总结一下：
从一个单一的线段开始。现在进行循环：如果一条线段“太长”，就将其分成两部分。使每个点稍微随机移动，但让点之间相互排斥。当不能取得更多进展时结束循环。这里有一些细节，但希望您能理解这个思路。
当然，这将产生一条角形路径（这是可以接受的），但很容易将拐角变成平滑的弧线。
是的，我保留了代码。
但最后我还是解决了这个问题：
我的成功方法与TSP无关，但为了让你好奇，我会总结一下：从一个单一的线段开始。现在进行循环：如果一条线段“太长”，就将其分成两部分。使每个点稍微随机移动，但让点之间相互排斥。当不能取得更多进展时结束循环。这里有一些细节，但希望您能理解这个思路。
当然，这将产生一条角形路径（这是可以接受的），但很容易将拐角变成平滑的弧线。
是的，我保留了代码。
- Hugh Allen
4
正如我所说，找到一些随机点的旅游路线。它效果不佳，我也没有保留代码（或图片）。我的第二次尝试（也是最终解决方案）与TSP无关。 - Hugh Allen
那么最终的解决方案是什么？你有代码吗？这很有趣。 - shoosh
3你设计的路径看起来非常类似于希尔伯特曲线（http://en.wikipedia.org/wiki/Hilbert_curve）。事实上，我怀疑在所有情况下，希尔伯特曲线都是最优解。 - John Feminella
@John Feminella：它也应该看起来随机和有机 - 而不是像希尔伯特曲线那样重复的几何图案。 - Hugh Allen
7
知道一个问题是否是NP难问题对于排除涉及解决该问题的解决方案非常有用。无论何时你看到TSP（或任何其他NP难问题）在规模较大的问题中出现，你就会“知道”你正在走向错误的道路。你不仅知道这一点，而且知道“为什么”，并且可以自信地告诉你的老板/队友/任何人。
话虽如此http://en.wikipedia.org/wiki/CONCORDE揭示了以下内容：
话虽如此http://en.wikipedia.org/wiki/CONCORDE揭示了以下内容：
Concorde已被应用于基因映射[1]、蛋白质功能预测[2]、车辆路径规划[3]、将位图图像转换为连续线绘画[4]、调度船只运动进行地震勘测[5]以及研究组合优化问题的缩放特性[6]。
- jakber
7
我在地理缓存应用程序中使用它进行路线规划。
目前它使用点之间的直线距离，但是当我有时间的时候，它应该会正确地（使用道路）计算点之间的距离。
- KPexEA
1
你可能想要查看空间填充曲线解决路径规划问题的方案... - Mitch Wheat
6
我个人从未使用过它，但除了钻孔电路板之外，另一个应用是如果你想去多个不同地方，比如销售吸尘器。你可以使用一种解决方案来决定访问每个地方的最便宜方式，确保每个地方只被访问一次。
- 108
1
6那么您的意思是，如果你是一个旅行推销吸尘器的人，这很有用？ - Dave L.
5
大多数情况下，您不希望使用解决NP完全/困难问题的算法。您只需要一种“足够好”的算法。这些算法通常基于启发式方法，并提供合理的近似结果。
我曾遇到一个独立集实例（NP-完全问题），但我找到了一种贪心算法，在绝大多数情况下都能给出相当不错的结果，并且具有高效的运行时间。
我曾遇到一个独立集实例（NP-完全问题），但我找到了一种贪心算法，在绝大多数情况下都能给出相当不错的结果，并且具有高效的运行时间。
- user21714
3
许多优化排序方式，例如拼车接送、UPS包裹投递等，只要节点遍历需求可以用一个维度的努力来表达，比如时间或距离。
- dongilmore
3
与此帖子中的其他人一样，我在大学时为一个朋友建立了一个解决NP完全问题的解决方案——一个调度程序。当我同意解决他的问题时，我并不知道什么是NP完全问题。后来我意识到，我想出了一些相当好的启发式算法来解决这个问题，但当然真正的诀窍是知道何时告诉用户没有解决方案并且他们已经过度约束了问题。
这是将我的理论课程和现实世界结合起来的绝佳方式。
再次强调，对于实际应用而言，启发式算法和“足够接近”的解决方案通常是可以接受的，因为找到和实施理想解决方案的成本很高。
这是将我的理论课程和现实世界结合起来的绝佳方式。
再次强调，对于实际应用而言，启发式算法和“足够接近”的解决方案通常是可以接受的，因为找到和实施理想解决方案的成本很高。
- Tim
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接