我试图查明我编写的算法是否返回访问图中每个节点的最佳路径。我正在尝试遍历图表,就像您修剪草坪或用吸尘器打扫房屋或犁地一样。我找到了返回路径,但有没有办法检查它是否是最佳路径。有没有我可以用来检查它的 API 或在线服务?
我看过 Dijkstra 和 A* 算法以及 BFS 和 DFS,但我不确定如何验证我得到的路径是最有效的。
给定一个图,我如何找到访问所有节点的最快和最有效的路径?
谢谢
最佳答案
不幸的是,这是一个称为旅行商问题的 NP 困难问题。
因此没有已知的多项式时间解。遍历整个解决方案空间需要 !N 次迭代(其中 N 是节点数)。但是,有几种解决方案可以为您提供良好的解决方案,即使不是最好的。
我会研究模拟退火作为一种在所有节点之间获得短路径的方法。
关于c# - 检查最佳路径,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/18423523/