breadth-first-search - 广度优先搜索的迷宫求解

Question

有人可以解释一下如何使用广度优先搜索来解决迷宫吗？我需要使用广度优先搜索来找到通过迷宫的最短路径，但是我很困惑。

这是我书中的伪代码:

void breadth_first_search(tree T) {
  queue!;
  node u, v;

  initialize(Q);
  v = root of T;
  visit v;
  enqueue(Q, v);

  while (!empty(Q)) {
    dequeue(Q, v);
    for (each child u of v) {
      visit u;
      enqueue(Q, u);
    }
  }
}

因此，如果我将迷宫存储在2D矩阵中，则“root”(即起点)是否将位于 maze[x][y]中？

Answer 1

简短的回答:是的

解释:

该伪代码将通过迷宫的路径表示为通往树的叶子的路径。迷宫中的每个 Blob 都是树上的一个节点，您可以从那里找到的每个新 Blob 都是该节点的一个子节点。

为了进行广度优先搜索，算法首先必须考虑通过长度为1，然后为长度2，依此类推的树的所有路径，直到到达末端为止，这将导致算法停止，因为末端没有子节点，结果在一个空的队列中。

该代码通过使用队列(Q)来跟踪需要访问的节点。它首先将迷宫的起点设置为树的根，进行访问(检查树是否为终点)，然后从队列中移除根，并对每个 child 重复该过程。通过这种方式，它将按后顺序访问节点，即root，(root的每个子节点)，(第一个子节点的每个子节点)，(第二个子节点的每个子节点)等，直到到达末尾。

编辑:就目前而言，该算法到达终点时可能不会因队列中后面的其他节点而终止。您将不得不自行终止的条件。