您是否使用过旅行商算法来解决问题？
我在大学时在 NP 完备性的背景下研究了 TSP。 我实际上从未遇到过将其应用于实际问题的情况。 一些研究表明，它已被用来选择最便宜的移动钻头的路径，即在电路板上打孔。 这几乎就是我能找到的全部了。
你在用它吗？ TSA 还有哪些其他实际应用？
I studied TSP in college in the context of NP Completeness. I have never actually had a situation where it would apply to a practical problem. A little bit of research shows that it has been used to pick the cheapest path to move a drill around, that is making holes in circuit boards. That is pretty much all I could find.
Are you using it? What other practical applications does the TSA have?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（14）
我曾经接到一个任务，编写一个程序，用“波形曲线”（一条不自相交的曲线）相当均匀地填充矩形区域。 我的第一次尝试是在矩形内生成随机点并尝试找到它们的游览（不一定是绝对最短的）。 不幸的是，这种方法效果不佳，我放弃了它。
我最终确实解决了问题：
我成功的方法与 TSP 无关，但出于好奇我总结一下：
从一条线段开始。 现在循环：如果一行“太长”，则将其分成两部分。 随机移动每个点，但使点彼此排斥。 当几乎没有进展时结束循环。 有一些细节，但希望您能明白。
当然，这会产生一条有角度的路径（这是可以接受的），但很容易将拐角变成平滑的弧线。
是的，我确实保留了代码。
I was once given the task of writing a program to fill a rectangular area fairly uniformly with a "squiggle" - a curved line which doesn't self-intersect. My first attempt was to generate random points within the rectangle and try to find a tour of them (not necessarily the absolute shortest). Unfortunately this approach just didn't work very well and I abandoned it.
I did solve the problem in the end though:
My successful method was not related to the TSP but for the curious I will summarize it:
Start with a single line segment. Now loop: if a line is "too long", divide it in two. Move each point a bit at random, but make points repel each other. End the loop when little progress can be made. There are details but hopefully you get the idea.
Of course this produces an angular path (which would have been acceptable) but it is easy to turn the corners into smooth arcs.
And yes I did keep the code.
了解问题何时是 NP 困难的对于排除涉及解决该问题的解决方案很有用。 每当你看到 TSP（或任何其他 NP 难题）因规模不小的问题而露出丑陋的头时，你知道你正走在错误的道路上。 您不仅知道，而且知道为什么，并且可以自信地告诉您的老板/队友/任何人。
话虽这么说http://en.wikipedia.org/wiki/CONCORDE表明：
Knowing when a problem is NP-hard is useful to exclude solutions involving solving that problem. Whenever you see TSP (or any other NP-hard problem) rear its ugly head for problems of non-trivial size you know you are heading down the wrong path. Not only do you know it, but you know why, and can confidently tell your boss/teammate/anyone.
That being said http://en.wikipedia.org/wiki/CONCORDE reveals that:
是的，我在地理藏宝应用程序中使用它来规划路线。
它目前使用点之间的直线距离，但应该正确地（当我解决它时）使用道路来计算点之间的距离。
http://code.google.com/p/gpsturbo/
Yes I use it in Geocaching application for route planning.
It currently uses a straight line distance between points but should correctly ( when I get around to it ) use roads to calc the distances between points.
http://code.google.com/p/gpsturbo/
我从未亲自使用过它，但除了钻孔电路板之外，另一个应用是如果您想去许多不同的地方，比如卖吸尘器。 您可以使用问题的解决方案来决定一次访问所有地方的最便宜的方式。
I've never personally used it, but another application besides drilling circuit boards is if you want to go to a number of different places, say to sell vacuums. You could use a solution of the problem to decide the cheapest way to visit everywhere exactly once.
大多数时候，您不想使用解决 NP 完全/困难问题的算法。 您只需要一个“足够好”的算法。 这些通常基于启发法并给出合理的近似值。
我遇到了一个独立集（NP-Complete）实例的问题，但我发现了一种贪心算法，它在绝大多数情况下都给出了相当好的结果，并且具有高效的运行时间。
Most of the time you don't want to use an algorithm that solves the NP-Complete/Hard problem. You just want an algorithm that is "good enough". These are usually based on heuristics and give reasonable approximations.
I had one problem that was an instance of Independent-Set (NP-Complete), but I found a greedy algorithm that gave pretty good results in the vast majority of cases, and had an efficient run-time.
TSP 是 NP 完全问题的hello world。 在它的纯粹规范形式中，您不会经常在野外找到它（不包括这样的演示），但是 NP 完全问题的一个巨大子集是相关的，甚至是基于 TSP 的，例如：
每一个都有额外的、特定领域的约束，这使得它们更难解决。
所以TSP是对NP完全问题的一个很好的介绍，可以理解它们的本质。
TSP is the hello world of NP complete problems. In it's pure canonical form, you won't find it in the wild often (demos like this one not included), but a huge subset of NP complete problems are related or even based on TSP, such as:
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.
和这个帖子中的其他人一样，我在大学里构建了一个 NP 完全问题的解决方案（这是一个朋友的业余项目）——一个调度程序。 当我同意解决他的问题时，我不知道什么是 NP 完全性。 后来我意识到我已经想出了一些相当好的启发法来解决问题 - 但当然真正的技巧是知道何时告诉用户没有解决方案并且他们过度限制了问题。
这是将我最终的理论课程和现实世界结合在一起的好方法。
同样，启发式和“足够接近”通常适用于现实世界的使用，其中由于寻找和实施理想解决方案的成本而优选接近最佳的解决方案。
As with others in this thread I built a solution to an NP complete problem in college (it was a side project for a friend) - a scheduling program. At the time that I agreed to work on his problem I did not know what NP complete was. I later realized I had come up with some fairly good heuristics for solving the problem - but of course the real trick was knowing when to tell the user that there was no solution and they had over-constrained the problem.
It was a great way to bring together my eventual theoretical classes and the real world.
Again, heuristics and "close enough" are generally fine for real world uses where near-optimal solutions are preferred because of the cost of finding and implementing the ideal solution.
多种类型的优化订购，例如拼车取货、UPS包裹递送等，其中节点遍历要求可以用一维的努力来表达，例如时间或距离。
Many types of optimized ordering, such as car pool pickup, UPS package delivery, etc. wherever the node traversal requirements can be expressed in one dimension of effort, such as time or distance.
现实生活中很少有问题能与你在数学课上学到的东西相匹配。 这些问题被简化和抽象，以便您可以看到数学，而不会被细节分散注意力。 正如您所提到的，大型 TSP 的最佳现实示例实际上并不涉及任何旅行推销员：它涉及调度需要执行作业的机器 序列-依赖的设置时间。 这包括手臂在不同位置移动工具的机器，以及一些涂漆应用（红色->橙色->黄色比红色->黄色->橙色更容易）。 x射线晶体学中也有一些应用您必须以几个不同的角度定向晶体样品。
Few problems in real-life match the stuff you learn in math class. The problems are simplified and abstracted so that you can see the math and not get distracted by details. The best real-life example of large TSPs, as you mentioned, doesn't actually involve any traveling salesman: it involves scheduling machines that have jobs to perform with sequence-dependent setup times. That includes machines where an arm moves a tool around different sites, and also some painting applications (red->orange->yellow is easier than red->yellow->orange). There are also some applications in x-ray crystallography where you have to orient some sample of a crystal at several different angles.
对于具有 20-60 个节点的地图，由于人类通常可以与大多数算法同等或更好地解决 TSP 问题，因此让计算机解决该问题并不常见。 当成本足够高时，让计算机比人类获得 1-2% 的改进是值得执行计算的成本的。 如果路线没有改变，那么就有理由花一些时间对其进行优化。 这在集成电路设计中很常见。
航空公司旅游网站在向您显示航空公司列表和每条航线的价格时，会使用 TSP 问题的专门版本。 不同之处不是距离，而是成本优化，当然没有要求每个城市都参观一次！ 假设您想从 LGA 飞往 LAX。 大约有 1/2 的直达路线，以及无数的其他路线。 可能建议LGA->ORD->LAX或LGA->DWF->LAX。 可以手动为路线定价的人类有时可以找到比旅行网站搜索的票价更低的票价。 通常，人们不希望有两个以上的转机，但给定航班的转机数量没有上限。
我用它来解决我的旅行推销员 iPhone 游戏的路线。 有趣的是，人们非常擅长解决最短路线问题，但不擅长解决最长路线问题。 最长和最短的路线具有相同的复杂性，但人们似乎经过训练能够找到最短的路线，通常比计算机更快更好。
Because humans can typically solve TSP problems on par or better than most algorithms for maps with 20-60 nodes, it's not very common to have a computer solve the problem. When the cost is high enough, having the computer get a 1-2% improvement over a human can be worth the cost of performing the calculation. If the route does not change, then one can justify spending some time optimizing it. This is common in integrated circuit design.
Airline travel websites use a specialized version of the TSP problem when the show you a list of airlines and the prices for each route. The difference is instead of distance, they optimize for cost, and certainly there is no requirement to visit each city once! Say you want to fly from LGA to LAX. There's about 1/2 dozen direct routes, and an infinite number of other routes. It may suggest LGA->ORD->LAX or LGA->DWF->LAX. Humans, who can manually price routes can sometimes find lower fares than the ones searched by the travel sites. Typically, people don't want more than two connections, but there isn't an upper limit to the number of connections for a given flight.
I've used it to solve routes for my Travelling Salesman iPhone Game. What's interesting is people are very good at solving the shortest route, but not at solving the longest route. The longest and shortest routes have the same complexity, but people seem trained to be able to find shortest routes, often faster and better than what a computer can do.
该公司基于改进的 TSP 算法。
https://www.mobicorp.com/
除了其他问题外，他们还为纽约市各地的有线电视安装人员和维修人员提供路线。
This company was based on an improved TSP algorithm.
https://www.mobicorp.com/
They route cable TV installers and repairmen around NYC among other problems.
在我的第一份工作中，我们构建了一个家庭护理调度应用程序。
我们通过一些非线性时间约束和额外的非线性成本函数解决了 TSP 问题。
我们使用非最优求解器来解决该问题。
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.
谷歌地图（以及所有其他基于地图的路由软件）不会使用某种旅行推销员来解决行车路线吗？
Wouldn't Google Maps (And every other Map based routing software) be using some kind of travelling salesman to solve driving directions?
据我所知，我还没有使用过 TSP，但我曾开发过一些能够穿越迷宫的自主机器人。 所以我想知道TSP是否可以应用于迷宫求解。
I have not used TSP as far as I know but I have worked on a number of autonomous robots to traverse a maze. So I wonder if TSP could be applied to maze solving.