旅行商的建设性启发法
假设我们有一个循环列表，代表旅行商问题的解决方案。该列表最初是空的。
如果允许用户输入一个城市及其坐标，可以使用什么启发法将这些坐标插入到已经存在的游览中？
一个示例使用最近邻启发式：它将新坐标插入到游览中已有的最近坐标之后。
还有哪些其他选项（如果可能，请使用伪代码）。
Say, we have a circular list representing a solution of the traveling salesman problem. This list is initially empty.
If the user is allowed to enter a city and it's coordinate one by one, what heuristics could be used to insert those coordinates into the already existing tour?
An example uses the nearest neighbor heuristic : it inserts the new coordinate after the nearest coordinate already in the tour.
What are some other options (pseudo-code if possible).
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
您可以使用多种构造启发法，例如首次拟合、首次拟合递减、最佳拟合、最佳拟合递减和最便宜插入。
这些构造启发法通常应用于装箱，但它们也可以转换为 TSP。 有关这些启发式方法的文档是
由于您一次只插入 1 个未分配的实体，因此所有这些基本上都会恢复为您所说的最近的实体邻居启发式（在联系上略有不同），但请注意，这不是他们通常所说的最近邻居。最近邻总是添加到行尾，即所有未分配实体的最近邻。
现在，您真正想要的是一个不错的解决方案，而不必重新启动整个构建启发式。这更难：欢迎来到重复规划和实时规划（和本文档） 。我正在研究一个用于 TSP 和进行实时规划的车辆路线的开源示例。
There are plenty of construction heuristics you can use, such as First Fit, First Fit Decreasing, Best Fit, Best Fit Decreasing and Cheapest Insertion.
Those constructions heuristics are applied on bin packing normally, but they can be converted to TSP too. Documentation about those heuristics is here.
Since you're only inserting 1 unassigned entity at at time, all of these basically revert to what you call nearest neighbor heuristic (with a slight variation on ties), but note that that is not what they usually call Nearest Neighbor. Nearest Neighbor always adds to the end of the line, the nearest neighbor of all unassigned entities.
Now, what you really want, is a decent solution, without having to restart your entire construction heuristics. That's harder: welcome to repeated planning and real-time planning (and this documentation). I am working on a open source example for TSP and vehicle routing that does real-time planning.
您当然可以概括您提到的想法：
定义
k'th_path（v）=包含max {k，not_visited城市}城市的路径的最小权重请注意，计算第k条路径为< code>O(|V|^k) [这个界限并不紧密]
特殊情况：
k=1你会得到最近的邻居，因为你建议。k=|V|，你会得到一个最佳解决方案[注意，计算起来会非常广泛]。You can of course generalize the idea you have mentioned:
Define
k'th_path(v) = minimum weight of a path including max{k,not_visited cities} citiesNote that calculating the k'th path is
O(|V|^k)[this bound is not tight]Special cases:
k=1you get the nearest neighbor, as you suggested.k=|V|you get an optimal solution [note it will be very expansive to calculate].没有其他启发式方法，因为 TSP 总是要找到最近的坐标。至少我不知道可以插入坐标并知道最近坐标的算法，但有很多算法可以找到好的游览。例如，Christofides 算法是一个很好的启发式算法，它仅适用于欧几里得空间，但它可以保证解决方案在最优解的 3/2 范围内。编码并不容易。尤其是 edmond Blossom V 算法适合专家技能。保证的重要性还不够高，因为您如何解释您的方法在某些罕见情况下可能会产生无意义的结果？
There are not other heuristic because TSP is always about to find the nearest coordinate. At least I don't know an algorithm that can insert a coordinate and knows the nearest coordinate but there are plenty algorithm to find a good tour. A good heuristic is for example the Christofides algorithm, it works only in euklidian space but it give you a guarantee of the solution to be within 3/2 of the optimum. It's not very easy to code. Especially the edmond blossom v algorithm is for an expert skill. The importance of a guarantee isn't high enough because how would you explain that your method can deliver non-sense in some rare situation?