8

幅優先探索を使用して迷路を解く方法を誰か説明してもらえますか? 迷路を通る最短経路を見つけるために幅優先探索を使用する必要がありますが、私はとても混乱しています。

これは私の本からの擬似コードです:

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 マトリックスに格納された迷路がある場合、「ルート」(つまり開始点) は になりmaze[x][y]ますか?

4

2 に答える 2

13

これが完全な BFS Maze ソルバーです。見つかった場合は、終点までの完全な最短パスを返します。迷路配列においてarr：0未踏空間を表し、5は壁空間、9はゴール空間である。-1スペースは、訪問された後に でマークされます。

import java.util.*;

public class Maze {

  public static int[][] arr = new int[][] {
            {0,0,0,0,0,0,0,0,0},
            {5,5,5,0,0,0,0,0,0},
            {0,0,0,5,0,0,0,0,0},
            {0,0,0,0,0,0,0,0,0},
            {0,0,0,0,0,0,0,0,0},
            {0,0,0,0,0,0,0,0,0},
            {0,0,0,0,0,0,0,0,0},
            {0,0,0,0,0,0,0,0,0},
            {0,0,0,0,0,0,0,0,9},
    };

  private static class Point {
        int x;
        int y;
        Point parent;

        public Point(int x, int y, Point parent) {
            this.x = x;
            this.y = y;
            this.parent = parent;
        }

        public Point getParent() {
            return this.parent;
        }

        public String toString() {
            return "x = " + x + " y = " + y;
        }
  }

  public static Queue<Point> q = new LinkedList<Point>();

    public static Point getPathBFS(int x, int y) {

        q.add(new Point(x,y, null));

        while(!q.isEmpty()) {
            Point p = q.remove();

            if (arr[p.x][p.y] == 9) {
                System.out.println("Exit is reached!");
                return p;
            }

            if(isFree(p.x+1,p.y)) {
                arr[p.x][p.y] = -1;
                Point nextP = new Point(p.x+1,p.y, p);
                q.add(nextP);
            }

            if(isFree(p.x-1,p.y)) {
                arr[p.x][p.y] = -1;
                Point nextP = new Point(p.x-1,p.y, p);
                q.add(nextP);
            }

            if(isFree(p.x,p.y+1)) {
                arr[p.x][p.y] = -1;
                Point nextP = new Point(p.x,p.y+1, p);
                q.add(nextP);
            }

             if(isFree(p.x,p.y-1)) {
                arr[p.x][p.y] = -1;
                Point nextP = new Point(p.x,p.y-1, p);
                q.add(nextP);
            }

        }
        return null;
    }


    public static boolean isFree(int x, int y) {
        if((x >= 0 && x < arr.length) && (y >= 0 && y < arr[x].length) && (arr[x][y] == 0 || arr[x][y] == 9)) {
            return true;
        }
        return false;
    }

    public static void main(String[] args) {

        Point p = getPathBFS(0,0);

         for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                System.out.print(arr[i][j]);
            }
            System.out.println();
        }

        while(p.getParent() != null) {
            System.out.println(p);
            p = p.getParent();
        }

    }

}
于 2014-11-13T11:07:40.190 に答える
6

短い答え: はい

説明：

その疑似コードは、迷路を通る経路を木の葉への経路として表しています。迷路の各スポットはツリー上のノードであり、そこから移動できる各新しいスポットはそのノードの子です。

幅優先探索を行うために、アルゴリズムは最初に長さ 1 のツリーを通るすべてのパスを考慮し、次に長さ 2 というように最後に到達するまで考慮する必要があります。これにより、最後に子がないためアルゴリズムが停止し、その結果、空のキューに。

コードは、キュー (Q) を使用して、アクセスする必要があるノードを追跡します。最初に迷路の開始点をツリーのルートに設定し、そこにアクセスして (終了かどうかを確認)、キューからルートを削除し、子ごとにプロセスを繰り返します。このようにして、最後に到達するまで、ポストオーダー、つまりルート、(ルートの各子)、(最初の子の各子)、(2 番目の子の各子) などのノードにアクセスします。

編集: 現状では、キュー内の他のノードが原因で、最後に到達したときにアルゴリズムが終了しない場合があります。解約の条件は自分で書く必要があります。

于 2013-05-03T20:32:11.207 に答える