algorithm - 随机生成 TSP 解决方案的算法

Question

解决 TSP 问题的最常见的启发式方法（特别是 Kernighan-Lin 启发式方法）需要处理随机生成的游览并从那里改进解决方案。但是，我想出的唯一方法是生成顶点的随机排列并检查它是否是一个解决方案。

对于问题的大型实例（例如 1000 个顶点），此过程可能需要一段时间。是否有另一种智能方法可以更快地为 TSP 问题生成随机游历？请注意，我正在寻找旅行，无论成本如何，而不是最佳解决方案。

提前致谢

Answer 1

如果您只是在寻找任何游览，您可以使用广度或深度优先搜索来生成路径，同时标记访问过的节点。

Answer 2

您可以只创建一个包含问题城市的数组，然后随机打乱该数组（有一些方法可以做到这一点）。结果数组实际上是一个随机排列。

Answer 3

您想使用空间填充曲线。