c# - 检查最佳路径

Question

我试图找出我编写的算法是否返回访问图中每个节点的最佳路径。我正在尝试遍历图表，就像您修剪草坪或用真空吸尘器打扫房屋或犁地一样。我得到了一条回去的路，但有没有办法检查它是否是最佳的。是否有我可以用来检查的 API 或在线服务？

我查看了 Dijkstra 和 A* 算法以及 BFS 和 DFS，但我不确定如何验证我得到的路径是最有效的。

给定一个图表，我如何找到访问所有节点的最快和最有效的路径？

谢谢

score 2 · Accepted Answer

不幸的是，这在称为旅行商问题的 NP Hard 问题中。

因此没有已知的多项式时间解。遍历整个解决方案空间需要 !N 次迭代（其中 N 是节点数）。但是，有几种解决方案可以为您提供良好的解决方案，即使不是最好的。

我会研究模拟退火作为一种在所有节点之间获得短路径的方法。

1 回答 1