Ati*_*esh 4 algorithm maze breadth-first-search time-complexity depth-first-search
我知道我们可以使用DFS进行迷宫探索.但我认为我们也可以使用BFS进行迷宫探索.我在这里有点困惑,因为我读过的大部分书籍和文章都使用DFS来解决这个问题.我认为与BFS相比,DFS 的最佳案例时间复杂度会更好.但BFS和DFS的平均和最差 情况时间复杂度相同,这就是为什么我们更喜欢DFS而不是BFS.我是对的还是我有一些误解
pka*_*zak 12
到目前为止,没有人提到由DFS和给出的结果差异,我感到非常惊讶BFS.
这两种算法的主要区别在于BFS返回最短路径,而DFS只返回路径.
因此,如果您想获得最短路径使用BFS,否则请考虑其他优缺点(内存等)
它们具有相似的运行时间,但是由于访问单元的顺序,任何一个问题都可能在任何给定问题上大大优于另一个.
在空间使用方面,BFS平均会为树使用更多内存,但对于更一般的图形,在某些情况下,它可以使用更少的内存.
特别是对于迷宫(如果我们定义一个迷宫,因为只有一种方法从起点到达一个单元而没有回溯,这意味着它本质上是一棵树),BFS通常会使用更多的内存,因为我们需要保留多个路径内存同时,DFS只需要在任何给定时间跟踪单个路径.
对于更一般的网格,在记忆方面哪一个更好是不太明显的,特别是考虑到我们如何跟踪我们迄今为止访问过的细胞以防止重复访问细胞.
如果你不关心记忆,你可以选择.如果你对递归感到相当舒服,那么DFS应该更容易实现.
但是,如果您正在寻找通用网格中某个给定单元格的最短路径,请使用BFS(或A*),因为这样可以保证找到最短路径,而DFS则不会(在迷宫中仍然可以使用)其中只有一条通往任何给定单元的路径.