我最近做了一个项目，使用不同的寻路算法来解决给定的迷宫。我通过导入黑白迷宫图像，并使每个结点成为一个节点来做到这一点。我尝试使用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 *相关的开销不值得节省所探索的空间。但是，要获取更多数据，也许您应该查看以下内容：
在找到最短路径之前，每种算法平均探索迷宫的哪一部分？
迷宫中最短的路径有多长？
迷宫是如何产生的，上述问题的答案取决于所使用的算法吗？