您是否使用旅行推销员算法来解决问题？
Evi*_*ach 23 algorithm traveling-salesman np-hard
我在NP Completeness的背景下在大学里学习过TSP.我实际上从未遇到过适用于实际问题的情况.一些研究表明,它已被用来选择最便宜的移动钻头的路径,即在电路板上钻孔.这几乎是我所能找到的.
你在用它吗？TSA还有哪些其他实际应用？
我曾经被赋予了编写程序的任务,该程序用"波浪线"相当均匀地填充矩形区域 - 曲线不会自相交.我的第一次尝试是在矩形内生成随机点并尝试找到它们的游览(不一定是绝对最短的).不幸的是,这种方法效果不好,我放弃了.
我最终解决了这个问题:
我的成功方法与TSP无关,但对于好奇我会总结一下:
从单个线段开始.现在循环:如果一行"太长",则将其分成两行.随机移动每个点,但使点相互排斥.当可以取得很少进展时结束循环.有细节但希望你明白了.
当然,这会产生一个角度路径(这是可以接受的)但是很容易将角转变成平滑的弧形.
是的,我确实保留了代码.
- 你提出的路径看起来非常类似于希尔伯特曲线(http://en.wikipedia.org/wiki/Hilbert_curve).事实上,我怀疑Hilbert曲线是所有情况下的最佳解决方案. (3认同)
我从来没有亲自使用它,但除了钻孔电路板之外的另一个应用是如果你想去许多不同的地方,比如卖真空吸尘器.您可以使用问题的解决方案来确定最便宜的方式到处访问一次.
- 所以,如果你是一个旅行的真空推销员,你会说这很有用吗？ (6认同)
知道问题何时是NP-hard对于排除涉及解决该问题的解决方案是有用的.无论什么时候你看到TSP(或任何其他NP难问题)都会把它丑陋的头脑放在非常重要的问题上,你知道你正走在错误的道路上.你不仅知道它,而且知道原因,并且可以自信地告诉你的老板/队友/任何人.
据说http://en.wikipedia.org/wiki/CONCORDE表明:
协和已应用于基因定位问题,[1]蛋白质功能预测,[2]车辆路径,[3]位图图像转换为连续线图,[4]调度船舶运动进行地震勘测,[5]和研究组合优化问题的缩放特性.[6]
是的我在Geocaching应用程序中用它来进行路径规划.
它目前使用点之间的直线距离,但应该正确(当我绕过它时)使用道路来计算点之间的距离.
http://code.google.com/p/gpsturbo/
大多数情况下,您不希望使用解决NP-Complete/Hard问题的算法.你只需要一个"足够好"的算法.这些通常基于启发式并给出合理的近似值.
我有一个问题是Independent-Set(NP-Complete)的一个实例,但我发现了一个贪婪的算法,在绝大多数情况下都给出了相当不错的结果,并且运行时间很长.
和这个帖子中的其他人一样，我在大学里构建了一个 NP 完全问题的解决方案（这是一个朋友的业余项目）——一个调度程序。当我同意解决他的问题时，我不知道什么是 NP 完全性。后来我意识到我已经想出了一些相当好的启发法来解决问题 - 但当然真正的技巧是知道何时告诉用户没有解决方案并且他们过度限制了问题。
这是将我最终的理论课程和现实世界结合在一起的好方法。
同样，启发式和“足够接近”通常适用于现实世界的使用，其中由于寻找和实施理想解决方案的成本而优选接近最佳的解决方案。