【Java】A*(A-star, エースター)アルゴリズムで迷路を探索する

2015/11/03 Tue [edit]

　A*(A-star, エースター)探索アルゴリズムとは簡単に言えばダイクストラ法に推定値を用いた最良優先探索アルゴリズムである。「推定値」というくらいなので正確さに欠けるときもあるが、通常は枝刈り（一部探索を打ち切ること）が行われるので、実行速度が速いという特徴がある。ヒューリスティクス探索と呼ばれることもある。そういう特徴からゲームなどに使われることも多い。敵AIがプレイヤーを追跡するのにも使える。

　以前、頂点と辺でのダイクストラ法を書いたが、比較してみると、ほとんどダイクストラ法と変わらない事がわかるだろう。実際「推定値」を使って比較している部分を「移動コスト」に書き換えればダイクストラ法そのものになる。

●A*(A-star)アルゴリズムで迷路探索

import java.util.PriorityQueue;
import java.util.Queue;

public class MazeShortestAstar {

    public static void main(String[] args) throws Exception {
        new MazeShortestAstar();
    }

    static final int INF = Integer.MAX_VALUE;    //INF値

    //４方向探索用
    static final int[] dx = { 0, 1, 0, -1};
    static final int[] dy = {-1, 0, 1,  0};
    static final char[] dir = {'u', 'r', 'd', 'l'};

    String path = "";    //移動経路(戻値用)

    //マンハッタン距離を求める
    static int getManhattanDistance(int x1, int y1, int x2, int y2) {
        return Math.abs(x1 - x2) + Math.abs(y1 - y2);
    }
    //チェビシェフ距離を求める
    static int getChevyshevDistance(int x1, int y1, int x2, int y2) {
        return Math.max(Math.abs(x1 - x2), Math.abs(y1 - y2));
    }

    public MazeShortestAstar() {

        int n = 10;    //↓方向
        int m = 10;    //→方向
        String[] maze = new String[]{
            "S..#...#..",
            ".#.#.#.#.#",
            "...#.#....",
            "##...#.##.",
            ".....#.#..",
            ".#####.#.#",
            ".......#..",
            "##.######.",
            "...#...#..",
            ".#...#...G",
        };

        int ans = astar(n, m, maze);
        System.out.println(ans);
        System.out.println(path);
    }

    //A*(A-star)探索アルゴリズム
    int astar(int n, int m, String[] maze) {
        int[][] grid = new int[n][m];    //移動コスト(距離)の記録
        int sx, sy, gx, gy;              //スタートとゴール位置
        sx = sy = gx = gy = 0;

        //迷路データのパース
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (maze[i].charAt(j) == '#') {
                    grid[i][j] = -1;       //壁
                } else if (maze[i].charAt(j) == 'S') {
                    grid[i][j] = 0;        //スタートは距離０
                    sy = i;
                    sx = j;
                } else if (maze[i].charAt(j) == 'G') {
                    grid[i][j] = INF;
                    gy = i;
                    gx = j;
                } else {
                    grid[i][j] = INF;
                }
            }
        }

        //A*(A-star) 探索
        Queue<Position> q = new PriorityQueue<Position>();

        Position p = new Position(sx, sy);
        p.estimate = getManhattanDistance(sx, sy, gx, gy);    //推定値
        q.add(p);

        while (!q.isEmpty()) {
            p = q.poll();
            if (p.cost > grid[p.y][p.x]) {
                continue;
            }
            if (p.y == gy && p.x == gx) {    //ゴールに到達
                path = p.path;        //移動経路(戻値用)
                break;
            }

            for (int i = 0; i < dx.length; i++) {
                int nx = p.x + dx[i];
                int ny = p.y + dy[i];
                if (nx < 0 || m <= nx || ny < 0 || n <= ny) {    //範囲外
                    continue;
                }
                if (grid[ny][nx] > grid[p.y][p.x] + 1) {
                    grid[ny][nx] = grid[p.y][p.x] + 1;
                    
                    Position p2 = new Position(nx, ny);
                    p2.cost = grid[ny][nx];        //移動コスト(スタートからの移動量)
                    p2.estimate = getManhattanDistance(nx, ny, gx, gy) + p2.cost;    //推定値
                    p2.path = p.path + dir[i];     //移動経路(移動方向の記録)
                    q.add(p2);
                }
            }
        }

        return grid[gy][gx];    //見つからないときは INF 値になる
    }

    //位置情報の構造体
    class Position implements Comparable<Position>{
        int x;               //座標
        int y;
        int cost;            //移動コスト(スタートからの移動量)
        int estimate;        //推定値(ゴールまでのマンハッタン距離＋移動コスト)
        String path = "";    //移動経路(移動方向の記録)

        //コンストラクタ
        public Position(int x, int y) {
            this.x = x;
            this.y = y;
        }

        //比較関数
        @Override
        public int compareTo(Position o) {
            return this.estimate - o.estimate;    //推定値で小さい順
        }
    }
}

24
rrddddllddrrdddrrurrdrrr

　ゴールに到達できなかったときは、戻値が INF 値(Integer.MAX_VALUE)になる。ダイクストラ法と同じように、コストに負の値は使えない（大小関係が崩れる、無限ループするなど）。今回は各位置への移動コストは１固定だが、迷路データによってコストを変えることもできる。例えば毒を受ける道はコスト２かかるなどという感じだ。その場合は迷路をパースする際に値を設定し、移動判定の部分「if (grid[ny][nx] > grid[p.y][p.x] + 1) {～}」の「+１」など、コストに関わる部分をそのコストに置き換えれば良い。

　今回は４方向の移動にしてるので、推定値は「ゴールまでのマンハッタン距離＋スタートからの移動量」にしている。８方向移動にするのなら、チェビシェフ距離の方が良いだろう。正確さを加えるために、推定値が同じときは、移動コストで比較するという推定値を２重にする方法もあるが、実際にやってみると、例えば障害物があまりない、広いフロアのような迷路データではダイクストラ法と同じ動作になってしまうため、４方に探索の手が伸ばされ、枝刈り効果がなくなる。実行速度と正確さのどちらかで使い分けた方が無難だろう。

　また、推定値に移動コストを足す理由を少し考えてみよう。例えばゴールまでの距離だけだと最短は円形（４方向の場合はひし形になるが）に広がるので、反対方向も同じになる。だからそこに辿り着くまでの移動コストが足されていれば、遠回りは最短候補から外れて枝刈りができるわけだ。つまり逆に遠回りが最短のときは効果が少ない。またこの推定値の意味を考えるなら「ここを通ってスタートからゴールへ行くには、たぶんN歩かかる」という値(N)と考えればわかりやすい。

　推定値の比較は位置情報の構造体（Position）に Comparable インタフェースを噛ませて、PriorityQueueで比較している。探索の優先順位などを変えたければここをいじるのが一番手っ取り早いだろう。冒頭にも書いたが、比較関数「compareTo()」の戻値「this.estimate - o.estimate」を「this.cost - o.cost」に書き換えればダイクストラ法となる。推定値は基本的に最短かそれ以下にしておかないと上手く動作できないが、探索の目的によって色々変えてみたり、条件で分岐させるのも良いかも知れない。とはいえ私も色々計算方法を試してみたが、この「ゴールまでの最短距離＋移動コスト」が平均的に効率が良いようだ。斜め移動を含む８方向での距離計算用に、チェビシェフ距離を求める「getChevyshevDistance()」をオマケとして付けてあるが、今回は使ってない。

　以下はデバッグ用に出力した各データをキャプチャしてみたものだ。「cost」はスタートからの移動量、「sequence」は探索した順序、「estimate」は計算された推定値、「count」は探索した回数、「path」はゴールまでの移動手順、色を付けてある「-1」は壁で、「X」は枝刈りされて未探索の場所だ。「Dijkstra」(ダイクストラ)は先に述べたように、比較関数を移動コストに変更しただけだ。動きの違いを見てみると、「A-Star」の方が大きく枝刈りされていて、探索回数が少なくなっている。実行速度を優先したい場合には有用だということがわかるだろう。

＞クリックで拡大

　この例では戻値はスタートからゴールまでの移動コストを返しているが、簡単な移動経路(移動方向の記録)もついでに返している（グローバル変数なのは手抜き(笑)）。本来ならリストで座標を返すべきかも知れないが、まぁ、ラーニング用コードなのでこれで十分だろう。この移動経路から座標を計算するか、リストなどに順次座標を追加していくように改造すれば、簡単に実現できる。

　また、今回のコードは幅優先探索をベースとした枝刈りアルゴリズムということになるが、深さ優先探索をベースとした「反復深化」という手法もある。一般的に深さ優先探索は幅優先探索よりメモリが少なくて済むので、携帯デバイスなどで使うときにはメリットがあるかも知れない。ゲームのようにリアルタイムで状況が変化するものは、正確さより実行速度を要する場合が多いので、ヒューリスティクス的なアルゴリズムは学習価値があるだろう。パフォーマンスが大きく改善される可能性もある。色々試してみると良いだろう。