您是否使用旅行推销员算法来解决问题？

我在NP Completeness的背景下在大学里学习过TSP.我实际上从未遇到过适用于实际问题的情况.一些研究表明,它已被用来选择最便宜的移动钻头的路径,即在电路板上钻孔.这几乎是我所能找到的.

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

1> Hugh Allen..：

---

我曾经被赋予了编写程序的任务,该程序用"波浪线"相当均匀地填充矩形区域 - 曲线不会自相交.我的第一次尝试是在矩形内生成随机点并尝试找到它们的游览(不一定是绝对最短的).不幸的是,这种方法效果不好,我放弃了.

我最终解决了这个问题:

我的成功方法与TSP无关,但对于好奇我会总结一下:

从单个线段开始.现在循环:如果一行"太长",则将其分成两行.随机移动每个点,但使点相互排斥.当可以取得很少进展时结束循环.有细节但希望你明白了.

当然,这会产生一个角度路径(这是可以接受的)但是很容易将角转变成平滑的弧形.

是的,我确实保留了代码.

---

你提出的路径看起来非常类似于希尔伯特曲线(http://en.wikipedia.org/wiki/Hilbert_curve).事实上,我怀疑Hilbert曲线是所有情况下的最佳解决方案.

2> 108..：

---

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

---

所以,如果你是一个旅行的真空推销员,你会说这很有用吗？

3> jakber..：

---

知道问题何时是NP-hard对于排除涉及解决该问题的解决方案是有用的.无论什么时候你看到TSP(或任何其他NP难问题)都会把它丑陋的头脑放在非常重要的问题上,你知道你正走在错误的道路上.你不仅知道它,而且知道原因,并且可以自信地告诉你的老板/队友/任何人.

据说http://en.wikipedia.org/wiki/CONCORDE表明:

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

4> KPexEA..：

---

是的我在Geocaching应用程序中用它来进行路径规划.

它目前使用点之间的直线距离,但应该正确(当我绕过它时)使用道路来计算点之间的距离.

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

5> user21714..：

---

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

我有一个问题是Independent-Set(NP-Complete)的一个实例,但我发现了一个贪婪的算法,在绝大多数情况下都给出了相当不错的结果,并且运行时间很长.