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