Javaの迷路ソルバー

投稿日: 2019-10-19 2022-10-25
タグ: Algorithms

1. 序章

この記事では、Javaを使用して迷路をナビゲートするための可能な方法を探ります。

迷路を白黒の画像と見なします。黒いピクセルは壁を表し、白いピクセルはパスを表します。 2つの白いピクセルは特別で、1つは迷路への入り口で、もう1つは出口です。

このような迷路を踏まえて、入口から出口までの道を見つけたいと思います。

2. 迷路のモデリング

迷路は2D整数配列であると見なします。配列内の数値の意味は、次の規則に従います。

0->道路
1->壁
2->迷路エントリ
3->迷路出口
4->入口から出口までのパスのセル部分

迷路をグラフとしてモデル化します。入口と出口は2つの特別なノードであり、その間のパスが決定されます。

一般的なグラフには、ノードとエッジの2つのプロパティがあります。エッジはグラフの接続性を決定し、あるノードを別のノードにリンクします。

したがって、各ノードから4つの暗黙的なエッジを想定し、指定されたノードをその左、右、上、下のノードにリンクします。

メソッドシグネチャを定義しましょう：

public List<Coordinate> solve(Maze maze) {
}

メソッドへの入力は迷路で、これには2D配列が含まれ、命名規則は上記で定義されています。

メソッドの応答はノードのリストであり、これは入口ノードから出口ノードへのパスを形成します。

3. 再帰的バックトラッカー（DFS）

3.1. アルゴリズム

かなり明白なアプローチの1つは、考えられるすべてのパスを探索することです。これにより、パスが存在する場合は最終的にパスが見つかります。しかし、そのようなアプローチは指数関数的に複雑になり、うまく拡張できません。

ただし、訪問したノードをバックトラックしてマークすることにより、上記のブルートフォースソリューションをカスタマイズして、妥当な時間内にパスを取得することができます。このアルゴリズムは、深さ優先探索とも呼ばれます。

このアルゴリズムの概要は次のとおりです。

壁にいる場合、またはすでにアクセスしたノードにいる場合は、失敗を返します
それ以外の場合、出口ノードの場合は成功を返します
それ以外の場合は、パスリストにノードを追加し、4つの方向すべてに再帰的に移動します。失敗が返された場合は、パスからノードを削除して失敗を返します。出口が見つかった場合、パスリストには一意のパスが含まれます

このアルゴリズムを図1（a）に示す迷路に適用してみましょう。ここで、Sは開始点、Eは終了点です。

ノードごとに、右、下、左、上という順序で各方向をトラバースします。

1（b）では、パスを探索して壁にぶつかります。次に、壁以外の隣接ノードを持つノードが見つかるまでバックトラックし、1（c）に示すように別のパスを探索します。

1（d）に示すように、再び壁にぶつかり、プロセスを繰り返して、最終的に出口を見つけます。

3.2. 実装

Javaの実装を見てみましょう。

まず、4つの方向を定義する必要があります。これは座標で定義できます。これらの座標を任意の座標に追加すると、隣接する座標の1つが返されます。

private static int[][] DIRECTIONS 
  = { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };

また、2つの座標を追加するユーティリティメソッドも必要です。

private Coordinate getNextCoordinate(
  int row, int col, int i, int j) {
    return new Coordinate(row + i, col + j);
}

これで、メソッドシグネチャsolveを定義できます。ここでのロジックは単純です–入口から出口までのパスがある場合はパスを返し、そうでない場合は空のリストを返します。

public List<Coordinate> solve(Maze maze) {
    List<Coordinate> path = new ArrayList<>();
    if (
      explore(
        maze, 
        maze.getEntry().getX(),
        maze.getEntry().getY(),
        path
      )
      ) {
        return path;
    }
    return Collections.emptyList();
}

上記で参照したexploreメソッドを定義しましょう。パスがある場合は、引数pathに座標のリストを指定してtrueを返します。このメソッドには3つの主要なブロックがあります。

まず、無効なノードを破棄します。迷路の外側にあるノード、または壁の一部であるノード。その後、同じノードに何度もアクセスしないように、現在のノードにアクセス済みのマークを付けます。

最後に、出口が見つからない場合は、すべての方向に再帰的に移動します。

private boolean explore(
  Maze maze, int row, int col, List<Coordinate> path) {
    if (
      !maze.isValidLocation(row, col) 
      || maze.isWall(row, col) 
      || maze.isExplored(row, col)
    ) {
        return false;
    }

    path.add(new Coordinate(row, col));
    maze.setVisited(row, col, true);

    if (maze.isExit(row, col)) {
        return true;
    }

    for (int[] direction : DIRECTIONS) {
        Coordinate coordinate = getNextCoordinate(
          row, col, direction[0], direction[1]);
        if (
          explore(
            maze, 
            coordinate.getX(), 
            coordinate.getY(), 
            path
          )
        ) {
            return true;
        }
    }

    path.remove(path.size() - 1);
    return false;
}

このソリューションでは、迷路のサイズまでのスタックサイズを使用します。

4. バリアント–最短経路（BFS）

4.1. アルゴリズム

上記の再帰的アルゴリズムはパスを見つけますが、必ずしも最短パスであるとは限りません。最短経路を見つけるために、幅優先探索として知られる別のグラフトラバーサルアプローチを使用できます。

DFSでは、1人の子供とそのすべての孫が最初に調査されてから、別の子供に移りました。一方、BFSでは、孫に移動する前に、すべての直接の子供を探索します。これにより、親ノードから特定の距離にあるすべてのノードが同時に探索されるようになります。

アルゴリズムの概要は次のとおりです。

開始ノードをキューに追加します
キューが空でないときに、ノードをポップし、次の手順を実行します。
1. 壁に到達した場合、またはノードがすでにアクセスされている場合は、次の反復にスキップします
2. 出口ノードに到達した場合は、現在のノードから開始ノードまでバックトラックして最短経路を見つけます
3. それ以外の場合は、キュー内の4つの方向にあるすべての隣接ノードを追加します

ここで重要なことの1つは、ノードが親を追跡する必要があることです。それらがキューに追加された場所から。これは、出口ノードが検出されたらパスを見つけるために重要です。

次のアニメーションは、このアルゴリズムを使用して迷路を探索するときのすべてのステップを示しています。次のレベルに移動する前に、同じ距離にあるすべてのノードが最初に探索されることがわかります。

4.2. 実装

このアルゴリズムをJavaで実装してみましょう。前のセクションで定義したDIRECTIONS変数を再利用します。

まず、特定のノードからそのルートにバックトラックするユーティリティメソッドを定義しましょう。これは、出口が見つかるとパスをトレースするために使用されます。

private List<Coordinate> backtrackPath(
  Coordinate cur) {
    List<Coordinate> path = new ArrayList<>();
    Coordinate iter = cur;

    while (iter != null) {
        path.add(iter);
        iter = iter.parent;
    }

    return path;
}

コアメソッドsolveを定義しましょう。DFS実装で使用される3つのブロックを再利用します。ノードを検証し、訪問したノードにマークを付け、隣接するノードをトラバースします。

少し変更を加えます。再帰的トラバーサルの代わりに、FIFOデータ構造を使用してネイバーを追跡し、それらを反復処理します。

public List<Coordinate> solve(Maze maze) {
    LinkedList<Coordinate> nextToVisit 
      = new LinkedList<>();
    Coordinate start = maze.getEntry();
    nextToVisit.add(start);

    while (!nextToVisit.isEmpty()) {
        Coordinate cur = nextToVisit.remove();

        if (!maze.isValidLocation(cur.getX(), cur.getY()) 
          || maze.isExplored(cur.getX(), cur.getY())
        ) {
            continue;
        }

        if (maze.isWall(cur.getX(), cur.getY())) {
            maze.setVisited(cur.getX(), cur.getY(), true);
            continue;
        }

        if (maze.isExit(cur.getX(), cur.getY())) {
            return backtrackPath(cur);
        }

        for (int[] direction : DIRECTIONS) {
            Coordinate coordinate 
              = new Coordinate(
                cur.getX() + direction[0], 
                cur.getY() + direction[1], 
                cur
              );
            nextToVisit.add(coordinate);
            maze.setVisited(cur.getX(), cur.getY(), true);
        }
    }
    return Collections.emptyList();
}

5. 結論

このチュートリアルでは、迷路を解くための2つの主要なグラフアルゴリズムである深さ優先探索と幅優先探索について説明しました。また、BFSが入口から出口までの最短経路をどのように与えるかについても触れました。

さらに読むには、A *やダイクストラアルゴリズムなど、迷路を解くための他の方法を調べてください。

いつものように、完全なコードはGitHubのにあります。

getdocs

13036