请问为什么BFS求迷宫最短路径的时候可以得到最优解呢？

Question

请问为什么BFS求迷宫最短路径的时候可以得到最优解呢？
请问为什么BFS求迷宫最短路径的时候可以得到最优解呢？
请问为什么BFS求迷宫最短路径的时候可以得到最优解呢？

Answer 1

BFS(Breadth-First Search)算法的具体实现就是：通过不断取得某个状态能够达到的所有状态并将其加入队列尾， 并且由于队列本身的特性先加入队列的状态总是先得到处理，这样就可以总是先将需要转移次数更少的状态进行处理。换句话说就是总是取得了这个状态的树中更接近根部的节点，又或者是总是让搜索树的广度得到尽可能增加。拿一个例子来说，有一个如图所示的迷宫，'#' 为墙壁，'.' 为道路，'S' 为起点，'G' 为终点，需要我们找出从起点到达终点的最短路径。