gpt4 book ai didi

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

转载 作者:塔克拉玛干 更新时间:2023-11-03 02:59:02 28 4
gpt4 key购买 nike

解决 TSP 问题的最常见启发式方法(特别是 Kernighan–Lin 启发式方法)需要处理随机生成的路线并从中改进解决方案。然而,我想出的唯一方法是生成顶点的随机排列并检查它是否是一个解决方案。

对于大型问题实例(例如 1000 个顶点),此过程可能需要一段时间。有没有另一种聪明的方法可以更快地为 TSP 问题生成随机游览?请注意,我正在寻找一个不计成本的游览,而不是最佳解决方案。

提前致谢

最佳答案

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

关于随机生成 TSP 解决方案的算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/4138682/

28 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com