1前書き

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

迷路は白黒のイメージであり、黒いピクセルは壁を表し、白いピクセルはパスを表します。 2つの白いピクセルは特別です。1つは迷路への入り口で、もう1つは出口です。

このような迷路を考えて、入り口から出口までの経路を見つけたいのです。


2迷路のモデリング

迷路は2次元整数配列と見なします。配列内の数値の意味は、次の規則のとおりです。

  • 0 – >道路

  • 1 – >壁

  • 2 – >迷路エントリ

  • 3 – >迷路出口

  • 4 – >入口から出口までのパスのセル部分

  • 迷路をグラフとしてモデル化します** 。入口と出口は2つの特別なノードです。

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

  • したがって、各ノードから4つの暗黙の辺を仮定し、与えられたノードをその左、右、上、下のノードにリンクします。

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

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

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

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


3再帰的バックトラッカー(DFS)


3.1. アルゴリズム

1つのかなり明白なアプローチはすべての可能な経路を探索することです。そして、それが存在すれば最終的に経路を見つけます。しかし、そのようなアプローチは指数関数的に複雑になり、うまく拡張できません。

  • ただし、妥当な時間内にパスを取得するために、訪問したノードをバックトラックしてマークすることで、上記のブルートフォースソリューションをカスタマイズすることは可能です。このアルゴリズムはhttps://en.wikipedia.org/wiki/Depth-first__search[Depth-first search]としても知られています。

このアルゴリズムは、次のように概説できます。

  1. 私たちが壁やすでに訪れたノードにいる場合、失敗を返します

  2. そうでなければ、私たちが出口ノードであれば、成功を返します

  3. そうでなければ、パスリストにノードを追加し、4つすべてに再帰的に移動

行き方。失敗が返された場合は、パスからノードを削除して失敗を返します。出口が見つかった場合、パスリストには固有のパスが含まれます

このアルゴリズムを図-1(a)に示す迷路に適用しましょう。ここでSは始点、Eは出口です。

ノードごとに、右、下、左、上の順に各方向に移動します。

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

1(d)に示すように、再び壁に突き当たり、最後に出口を見つけるためにこのプロセスを繰り返します。

リンク:/uploads/dfs-2-240×300.png[]リンク:/uploads/dfs-4-239×300-2.png[]


3.2. 実装

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

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

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. アルゴリズム

上記の再帰的アルゴリズムはパスを見つけますが、必ずしも最短パスとは限りません。最短パスを見つけるには、https://en.wikipedia.org/wiki/Breadth-first__search[Breadth-first search]として知られる別のグラフトラバースアプローチを使用できます。

DFSでは、1人の子供とそのすべての孫が最初に調査され、その後別の子供に移りました。

BFSでは、孫に移動する前に、すべての直接の子を探索します

これにより、親ノードから特定の距離にあるすべてのノードが同時に探索されます。

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

  1. 開始ノードをキューに追加します

  2. キューが空でない間に、ノードをポップし、以下を実行してください.

.壁にたどり着いた場合、またはノードにアクセス済みの場合は、次へ進んでください。

繰り返し
..出口ノードに到達したら、現在のノードから開始ノードまでバックトラックする

最短経路を見つける
..そうでなければ、4つの方向のすべての直近の隣人をキューに追加

  • ここで重要なことの1つは、ノードが自分の親、つまりキューに追加された場所から追跡する必要があることです。** 出口ノードに遭遇したときにパスを見つけるには重要です。

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

リンク:/uploads/bfs-1.gif[]


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 ** やDijkstraアルゴリズムのような、迷路を解くための他の方法を調べてください。

いつものように、完全なコードはhttps://github.com/eugenp/tutorials/tree/master/algorithms-miscellaneous-2[over on GitHub]で見つけることができます。