Sam*_*wal 3 algorithm maze graph path-finding graph-algorithm
我最近做了一个项目，使用不同的寻路算法解决给定的迷宫。我通过导入黑白迷宫图像，并使每个结点成为节点来做到这一点。我尝试使用 DFS、BFS、Dijkstra 和 A* 解决这个问题，但注意到令人惊讶的是 DFS 给了我最短的运行时间。我的问题是，在完美的迷宫（只有一个解决方案）上使用更高级的算法（例如 Dijkstra 或 A*）是否有意义？还是这些算法只在有多种解决方案的迷宫中才有意义？
我在网上研究了这个，发现很多人喜欢用 A* 来解决这类问题，但我不明白这有什么好处，至少对于一个完美的迷宫。
这是个有趣的问题。让我们探索它，看看为什么您可能会看到您所看到的内容。
在您提到的四种算法中 - BFS、DFS、Dijkstra's 和 A* - 其中三个（BFS、Dijkstra's 和 A*）旨在在有多个不同路径可用且您感兴趣的结构中找到最短路径在寻找最短的。从这个意义上说，运行 BFS、Dijkstra's 和 A* 在某种意义上都会产生成本开销，因为您要为不使用的东西付费。在这种情况下，特别是 Dijkstra 算法的性能应该不会比 BFS 好。采取任何步骤都将花费相同的金额，并且维护优先级队列或其他结构以找到边界中成本最低的节点的成本可能比标准队列的成本更高。从这个意义上说，我们可能可以排除 Dijkstra 作为这里最快算法的候选者。
这给我们留下了 BFS、A* 和 DFS。我们先来比较一下 BFS 和 DFS。DFS 的优点是理论上它很快（线性时间），并且运行 DFS 所涉及的内存访问模式（维护堆栈顶部并探测最近访问的位置附近的位置）与缓存配合得很好。BFS 的优点是一旦找到最短路径就会停止搜索，缺点是内存访问更加分散并且与缓存一起玩得不太好。
让我们在这里做一个快速的几何论证。BFS 通过探索越来越长的路径从起始位置向外扩展。从这个意义上说，你可以想象 BFS 搜索的区域会形成一些模糊地近似于以起始位置为中心的圆的东西。这个圆的半径将等于找到的最短路径的长度。从这个意义上说，如果没有障碍物，您会期望 BFS 在找到出口之前访问迷宫中总空间的某个恒定部分，并且存在障碍物时，它可能会探索大部分（如果不是全部）空间。DFS 在找到出口后立即停止，并且可能会沿途探索许多死胡同，因此同样很有可能探索大部分迷宫单元。
然后是 DFS 与 A*。这是一个更难分析先验。由于在 A* 中保持距离的相关开销，DFS 通常比 A* 算法快得多，但 A* 倾向于搜索更有可能让您到达目的地的方向。这可能取决于迷宫的形状。如果迷宫的建造方式有很多又长又曲折的通道，那么 A* 可能会做得更好，因为它会避免走错方向，直到绝对不得不走，DFS 可能会花费大量精力以错误的方式下降. 但是您必须查看这些因素之间的平衡才能确定。
还有一个问题，那就是迷宫本身是如何生成的。有许多不同的迷宫生成算法 - 例如，您可以使用 Kruskal 算法、DFS、Prim 算法或 Wilson 算法来生成迷宫。用 DFS 制作的迷宫往往有更少、更长的走廊，而 Kruskal 的算法和 Prim 的算法倾向于制作许多较短的走廊。在某些情况下，DFS 可能会比其他情况做得更好，而 A* 也可能做得更好或更差。所以也许 A* 和 DFS 之间的区别除了它们自己的实现细节之外还与迷宫形状有关。
所以总的来说，听到你的 DFS 是最快的迷宫解决算法，我并不感到惊讶，这主要是因为与其他算法相比，DFS 的简单性和良好的缓存局部性。它击败 A* 的事实可能是由于与 A* 相关的开销不值得在探索的空间中节省。但是要获得更多数据，也许您应该查看以下内容：
平均而言，每个算法在找到最短路径之前探索了迷宫的多少部分？
迷宫中最短的路径有多长？
迷宫是如何产生的，上述问题的答案是否取决于所使用的算法？