比如说，我们有一个代表旅行商问题的解决方案的循环列表。此列表最初为空。
如果允许用户输入一个城市并且它的坐标是一一对应的，那么可以使用什么启发式方法将这些坐标插入到已经存在的游览中？
一个示例使用最近邻启发式：它将新坐标插入到旅行中已经存在的最近坐标之后。
还有哪些其他选项（如果可能，请使用伪代码）。
问问题
2881 次
3 回答
2
您可以使用许多构造启发式方法，例如首次拟合、递减递减、最佳拟合、递减最佳拟合和最便宜的插入。这些构造启发式通常应用于装箱，但它们也可以转换为 TSP。关于这些启发式的文档在这里。
由于您一次只插入 1 个未分配的实体，所有这些基本上都恢复为您所谓的最近邻启发式（关系略有变化），但请注意，这不是他们通常所说的最近邻。最近邻总是添加到行尾，即所有未分配实体的最近邻。
现在，您真正想要的是一个不错的解决方案，而无需重新启动整个构建启发式方法。这更难：欢迎重复规划和实时规划（以及本文档）。我正在开发一个用于实时规划的 TSP 和车辆路线的开源示例。
于 2012-01-07T17:50:07.063 回答
1
您当然可以概括您提到的想法：
定义k'th_path(v) = minimum weight of a path including max{k,not_visited cities} cities
注意计算第k个路径是O(|V|^k)[这个界限不紧]
特殊情况：
- 因为
k=1你得到最近的邻居，正如你所建议的。 - 因为
k=|V|你得到了一个最佳的解决方案[注意计算起来会非常广泛]。
于 2012-01-07T12:15:40.190 回答
0
没有其他启发式方法，因为 TSP 总是要找到最近的坐标。至少我不知道可以插入坐标并知道最近坐标的算法，但是有很多算法可以找到一个好的游览。一个很好的启发式算法是例如 Christofides 算法，它仅适用于欧克里德空间，但它可以保证解决方案在最优值的 3/2 范围内。编码不是很容易。特别是 edmond bloom v 算法是针对专家技能的。保证的重要性还不够高，因为您如何解释您的方法可以在某些罕见的情况下提供无意义？
于 2012-01-07T11:54:20.470 回答