21

我在大学时在 NP Completeness 的背景下学习了 TSP。我从来没有真正遇到过适用于实际问题的情况。一些研究表明，它已被用来选择最便宜的移动钻头的路径，即在电路板上打孔。这几乎是我能找到的所有东西。

你在用吗？TSA 还有哪些其他实际应用？

4

14 回答 14

8

我曾经被要求编写一个程序，用“曲线”（一条不会自相交的曲线）相当均匀地填充一个矩形区域。我的第一次尝试是在矩形内生成随机点并尝试找到它们的路径（不一定是绝对最短的）。不幸的是，这种方法效果不佳，我放弃了它。

我最终确实解决了这个问题：

替代文字

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

从单个线段开始。现在循环：如果一行“太长”，则将其一分为二。随机移动每个点，但使点相互排斥。当进展不大时结束循环。有细节，但希望你能明白。

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

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

于 2008-11-05T02:41:03.267 回答
7

知道问题何时是 NP-hard 有助于排除涉及解决该问题的解决方案。每当您看到 TSP（或任何其他 NP-hard 问题）为非平凡规模的问题抬起丑陋的头时，您就知道自己走错了路。你不仅知道，而且知道为什么，并且可以自信地告诉你的老板/队友/任何人。

话虽如此， http ://en.wikipedia.org/wiki/CONCORDE表明：

Concorde 已应用于基因映射问题、[1] 蛋白质功能预测、[2] 车辆路线、[3] 将位图图像转换为连续线图、[4] 为地震勘测调度船舶运动、[5] 和研究组合优化问题的缩放特性。[6]

于 2008-11-05T01:23:17.247 回答
7

是的，我在 Geocaching 应用程序中使用它来规划路线。

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

http://code.google.com/p/gpsturbo/

于 2008-11-05T02:10:56.073 回答
6

我从来没有亲自使用过它，但是除了钻孔电路板之外的另一个应用是如果你想去许多不同的地方，比如卖真空吸尘器。您可以使用问题的解决方案来决定最便宜的方式来访问任何地方一次。

于 2008-11-05T01:01:15.480 回答
5

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

我有一个问题是独立集（NP-Complete）的一个实例，但我发现了一种贪心算法，它在绝大多数情况下都给出了很好的结果，并且运行时间很有效。

于 2008-11-06T00:27:12.507 回答
4

TSP 是 NP 完全问题的hello world。在它的纯粹规范形式中，你不会经常在野外找到它（不包括像这样的演示），但是一个巨大的 NP 完全问题子集是相关的，甚至是基于 TSP 的，例如：

  • 车辆路线（包括供应卡车路线）
  • 航空公司/航班路线
  • 列车路线
  • 滑雪坡犁机走线

其中每一个都有额外的、特定于域的约束，这使得它们更难解决。所以TSP很好地介绍了NP完全问题，了解它们的本质。

于 2012-05-02T10:03:04.160 回答
3

许多类型的优化排序，例如拼车取货、UPS 包裹递送等，凡是节点遍历需求都可以用一维工作量来表示，例如时间或距离。

于 2008-11-05T02:21:22.573 回答
3

现实生活中很少有问题与你在数学课上学到的东西相匹配。问题被简化和抽象化，这样你就可以看到数学而不被细节分心。正如您所提到的，大型 TSP 的最佳现实示例实际上并不涉及任何旅行推销员：它涉及调度机器，这些机器具有执行与序列相关的设置时间的作业。这包括手臂在不同位置移动工具的机器，以及一些绘画应用（红色->橙色->黄色比红色->黄色->橙色更容易）。在X 射线晶体学中也有一些应用，您必须将一些晶体样品定向在几个不同的角度。

于 2008-11-06T01:01:30.487 回答
3

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

这是将我最终的理论课程和现实世界结合在一起的好方法。

同样，启发式和“足够接近”通常适用于现实世界中的使用，因为寻找和实施理想解决方案的成本，接近最优解决方案是首选。

于 2008-11-06T02:06:35.693 回答
2

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

https://www.mobicorp.com/

他们在纽约市附近安排有线电视安装人员和维修人员等问题。

于 2009-04-16T16:38:53.767 回答
2

因为对于具有 20-60 个节点的地图，人类通常可以比大多数算法更好地解决 TSP 问题，所以让计算机解决问题并不常见。当成本足够高时，让计算机比人类提高 1-2% 的成本是值得的。如果路线没有改变，那么可以证明花一些时间对其进行优化是合理的。这在集成电路设计中很常见。

当向您显示航空公司列表和每条航线的价格时，航空公司旅行网站使用 TSP 问题的专门版本。不同的是距离而不是距离，他们优化了成本，当然没有要求每个城市都访问一次！假设您想从 LGA 飞往 LAX。大约有 1/2 打直接路线，以及无数其他路线。它可能建议 LGA->ORD->LAX 或 LGA->DWF->LAX。可以手动定价路线的人类有时可以找到比旅游网站搜索的票价更低的票价。通常，人们不想要超过两个连接，但对于给定航班的连接数量没有上限。

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

于 2009-08-05T21:00:36.960 回答
1

在我的第一份工作中，我们构建了一个家庭护理调度应用程序。
我们用一些非线性时间约束和一个额外的非线性成本函数解决了 TSP 问题。
我们使用非最优求解器来解决问题。

于 2010-08-16T09:04:18.027 回答
0

谷歌地图（以及其他所有基于地图的路由软件）不会使用某种旅行推销员来解决行车路线吗？

于 2008-11-05T02:51:40.813 回答
0

据我所知，我还没有使用过 TSP，但我已经研究过一些自主机器人来穿越迷宫。所以我想知道 TSP 是否可以应用于迷宫解决。

于 2008-11-06T00:07:55.790 回答