随机生成 TSP 解的算法
解决 TSP 问题的最常见启发式方法（特别是 Kernighan-Lin 启发式方法）需要进行随机生成的游览，并从此开始改进解决方案。然而，我想到的唯一方法是生成顶点的随机排列并检查它是否是解决方案。
对于问题的大型实例（例如 1000 个顶点），此过程可能需要一段时间。是否有另一种智能方法可以更快地生成 TSP 问题的随机游览？请注意，我正在寻找一次旅行，无论成本如何，而不是最佳解决方案。
提前致谢
The most common heuristics to solve the TSP problem (in particular the Kernighan–Lin heuristic) require to work on a randomly generated tour and to improve the solution starting from that. However, the only way I came up with to do that is to generate a random permutation of the vertices and to check if it is a solution or not.
For large instances of the problem (for example 1000 vertices) this process can take a while. Is there another smart way to generate a random tour for TSP problem faster?? Note that I'm looking for a tour, no matter the cost, and not an optimal solution.
Thanks in advance
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
如果您只是寻找任何游览，则可以使用广度优先搜索或深度优先搜索来生成路径，同时标记访问过的节点。
If you're just looking for any tour, you can use Breadth or Depth First Search to generate a path while marking the nodes visited.
您可以创建一个包含该问题的城市的数组，然后随机洗牌该数组（有一些方法可以做到这一点）。
生成的数组实际上是随机排列。
You could just create an array which contains ths problem's cities and then randomly shuffle that array (there are methods that could do this).
The resulting array is in fact a random permutation.
您想使用空间填充曲线。
You want to use a space-filling-curve.