こんにちは。
今回は「幅優先探索」と「深さ優先探索」を扱ってみます。
以前、迷路をつくったり、解いたり、迷路の形が雷の軌跡のモデルになるらしいと聞いて実際にやってみたりしました。
1つ目の記事で迷路を解く方法として、行き止まりを埋めていくもの (言わば穴埋め法？) を実装してみました。
そんなある種外道なやり方だけ取りあげて、有名な幅優先探索や深さ優先探索はノータッチでしたので今回やってみます。
はじめてのように書いていますが、改めて読んでみたら雷の軌跡の件で幅優先探索だけやっていたようです。
2年前にちょろっと触れたことなのですっかり忘れていました。
目次
はじめに
幅優先探索と深さ優先探索は、ともにグラフ理論においてある点から別の点への経路を探す方法です。
幅優先探索では、始点から同じ深さにあるノードを優先するため、同心円状に広がるように、全ての分岐を同時に試していきます。
最短経路を求められることでも有名かと思います。
一方、深さ優先探索では、始点から深いノードを優先するため、行けるところまでいった後に分岐点に返ってきます。
例えば、適当につくった "木" を今回つくったプログラムで探索してみると、探索する順番は以下のようになります。
「S」から始まり、それぞれ横方向と縦方向を意識した動きになっているのがわかるかと思います。
もちろん、エッジの無いところは到達できないので、探索しません。
実装
グラフの扱い方
プログラム上でのグラフは、あるノードがどのノードにつながっているかを配列の形で記述することで表現します。
先程挙げたような "木" で考えてみると、
int[][] edges = {{1, 2}, {0, 3, 4, 5}, {0, 6}, {1}, {1, 7}, {1}, {2}, {4}, {}};
ノード 0 につながっているものは edges[0] で得られ、ノード 1 と 2 につながっていることがわかります。
ノード 8 は何もつながっていないので、edges[8] は空の配列になっています。
幅優先探索
幅優先探索では、同じ深さにあるノードを優先して探索します。
始点をノード 0 としたとき、進む先はノード 1 か 2 です。
ノード 1 に注目すれば、進む先の候補はノード 3 か 4 か 5 になります。
幅優先なので次はノード 2 に注目して、候補はノード 6。
ノード 1 や 2 と同じ深さのものが無いのでさらに深くに進みノード 3 に注目して…と続けていきます。
ここから言えることは、進む先の候補を配列に入れていき、その先頭から取り出していけば次に探索すべきノードがわかる、ということです。
(この右から入れて左から出すような配列は「キュー (queue)」とよばれます。)
加えて、edges には親ノードの情報も入っているので探索済みであれば飛ばす、ということも必要です。
先程の説明なら、
始点をノード 0 としたとき、進む先はノード 1 か 2。
注目: 0 キュー: {1, 2}
ノード 1 に注目すれば、進む先の候補はノード 0 か 3 か 4 か 5。
注目: 1 キュー: {2, 0, 3, 4, 5}
幅優先なので次はノード 2 に注目して、候補はノード 6。
注目: 2 キュー: {0, 3, 4, 5, 6}
ノード 0 は探索済みのため飛ばす。
ノード 1 や 2 と同じ深さのものが無いのでさらに深くに進みノード 3 に注目して…
注目: 3 キュー: {4, 5, 6}
のようにキューが処理されていきます。
最終的には進む先の候補が無くなった、すなわちキューが空になったところで全てを探索し終えます。
終点を設定している場合は終点に到達した時点で終了となるでしょう。
グラフ
全範囲で探索を行い、各ノードが始点からどのくらい離れているかを計算するプログラムを書いてみます。
幅優先探索を行う関数を「breadth-first search」からとって bfs() とします。
ここで扱う配列は、
探索済みかを記録する
isChecked後に探索するノードを入れておく
queue始点からの距離を記録する
dist_list
です。
void bfs(int[][] edges, int start){ int n = edges.length; boolean[] isChecked = new boolean[n]; // 探索済みかどうかを記録する配列 for(int i = 0; i < n; i ++){ isChecked[i] = false; } isChecked[start] = true; IntList queue = new IntList(); // 後に探索する点を入れておく配列 queue.append(start); int[] dist_list = new int[n]; // 始点からの距離を入れておく配列 for(int i = 0; i < n; i ++){ dist_list[i] = 10000; } dist_list[start] = 0; // queue が無くなるまで繰り返す while(queue.size() > 0){ // 幅優先探索の処理が入る } println(dist_list);
始点ははじめから queue に入れておき、探索済み、距離 0 とします。
dist_list の初期値は 10000 としていますが、取り得ない値とすることで到達不可能なことや正しく処理されていることを確認するのにも役立ちます。
そして、queue が空になるまで探索を繰り返します。
// queue が無くなるまで繰り返す while(queue.size() > 0){ int current = queue.remove(0); // queue の最初の要素を取り出す // current の次を探索 for(int i = 0; i < edges[current].length; i ++){ int next = edges[current][i]; // 探索済みなら飛ばす if(isChecked[next] == true){ continue; } // 未探索なら… isChecked[next] = true; // 探索済みにする queue.append(next); // キューに加える dist_list[next] = dist_list[current] + 1; // 距離をそれまでの値+1にする } }
できた関数を setup() 等で呼び出して実行してみると、
[0] 0 [1] 1 [2] 1 [3] 2 [4] 2 [5] 2 [6] 2 [7] 3 [8] 10000
と出力され、手で数えてみても同じ結果になるので合っていそうです。
始点と終点を決めておき、その間の最短経路がどんなものかも気になるところです。
bfs() は終点も受け取るようにし、各ノードについてひとつ手前のノードを記録する配列 prev を追加します。
int[] prev = new int[n]; // 一歩前を記録する配列 for(int i = 0; i < n; i ++){ prev[i] = 10000; }
「未探索なら…」の部分に以下を追加して、一歩手前を保存しておきます。
prev[next] = current; // 一歩前を記録する
最後に prev を終点から遡っていき、始点まで戻れれば最短経路が求められます。
IntList route = new IntList(); int p = end; // 無限ループ while(true){ route.append(p); // スタートまできたら終了 if(p == start){ break; } p = int(prev[p]); } route.reverse(); // append() の都合上逆順にしないと始点→終点にならない println(route);
ノード 0 からノード 7 までの経路を出力させると、
IntList size=4 [ 0, 1, 4, 7 ]
となりました。合っていそうです。
迷路
幅優先探索を迷路に適用すれば、スタートからゴールまでの最短経路が求められます。
迷路も一応グラフのように考えることはできますが、ノード間のつながりをわざわざ配列に起こすのは面倒です。
過去に迷路をつくりましたが、出力形式は道と壁がそれぞれ 0 と 1 で表された二次元配列でしたので、それを活用できるとうれしいですよね。
迷路なら進む先の候補として上下左右の4通りが必ずあるので、「current の次を探索」の部分では edges[current] を考えるのではなく、current の上下左右を考えれば良いということになります。
道であれば queue に入れ、壁であれば飛ばす、というようにすれば問題なさそうです。
先程書いたコードから、二次元配列にしたりベクトルを使ったりして…
void bfs(int[][] maze, PVector start, PVector end){ // 進行方向4通り int[] dx = {-1, 1, 0, 0}; int[] dy = {0, 0, -1, 1}; // edge の長さを取得 int nx = maze.length; int ny = maze[0].length; boolean[][] isChecked = new boolean[nx][ny]; // 探索済みかどうかを記録する配列 for(int i = 0; i < nx; i ++){ for(int j = 0; j < ny; j ++){ isChecked[i][j] = false; } } isChecked[int(start.y)][int(start.x)] = true; ArrayList<PVector> stack = new ArrayList<PVector>(); // 次に探索する点を入れておく配列 stack.add(start); PVector[] prev = new PVector[nx*ny]; // 一歩前を記録する配列 for(int i = 0; i < nx*ny; i ++){ prev[i] = new PVector(10000, 10000); } // stack が無くなるまで繰り返す while(stack.size() > 0){ PVector current = stack.remove(stack.size()-1); // queue の最後の要素を取り出す // current の次を探索 for(int i = 0; i < 4; i ++){ int nextx = int(current.x) + dx[i]; int nexty = int(current.y) + dy[i]; // 配列の外なら飛ばす if(nextx < 0 || nx <= nextx || nexty < 0 || ny <= nexty){ continue; } // 探索済みなら飛ばす if(isChecked[nexty][nextx] == true){ continue; } // 壁なら飛ばす if(maze[nexty][nextx] == 1){ continue; } // 未探索なら… isChecked[nexty][nextx] = true; // 探索済みにする stack.add(new PVector(nextx, nexty)); // スタックに加える prev[nexty*ny+nextx] = new PVector(current.x, current.y); // 一歩前を記録する配列 } } // 最短経路を復元 ArrayList<PVector> route = new ArrayList<PVector>(); int x = int(end.x); int y = int(end.y); // 無限ループ while(true){ route.add(0, new PVector(x, y)); // スタートまできたら終了 if(x == start.x && y == start.y){ break; } int index = y*ny+x; x = int(prev[index].x); y = int(prev[index].y); } println(route); }
忘れていましたが、迷路は事前につくっておいてcsvファイルで入れてあります。
迷路の回で触れていますし、
processingの備忘録 -迷路- - プログラミングの備忘録
ファイルの扱いをまとめた記事もあります。
processingの備忘録 -txt、csvの生成- - プログラミングの備忘録
processingの備忘録 -画像、テキストの読み込み- - プログラミングの備忘録
実行すると結果が返ってきますが、迷路など対象が大きくなるとコンソールに出力されても何が何やらわかりません。
図示できるようにしましょう。
迷路のほぼ全域を探索してやっと経路が見つかっていますね。
地図
迷路と似ているかもしれませんが、少し通路が広いので障害物を避けるような動きが見えます。
幅優先探索の本領発揮というか、このようなものを対象にした方が幅優先探索で最短経路が求められるということがわかりやすいかもしれません。
深さ優先探索
深さ優先探索では、なるべく深くまで探索して分岐点まで戻ってきます。
始点をノード 0 としたとき、進む先はノード 1 か 2 です。
ノード 2 に注目すれば、進む先の候補はノード 6 になります。
深さ優先なので次はノード 6 に注目して、進む先の候補はなし。
行き止まりまで来たので最初の分岐点まで戻りノード 1 に注目して…と続けていきます。
実は、深さ優先探索では進む先の候補を配列に入れていき、その最後から取り出していけば次に探索すべきノードがわかる、ということになります。
(この右から入れて右から出すような配列は「スタック (stack)」とよばれます。)
つまり、幅優先探索のキューをスタックに変えるだけで深さ優先探索が実装できてしまいます。
先程の説明なら、
始点をノード 0 としたとき、進む先はノード 1 か 2。
注目: 0 スタック: {1, 2}
ノード 2 に注目すれば、進む先の候補はノード 6。
注目: 2 スタック: {1, 6}
深さ優先なので次はノード 6 に注目して、進む先の候補はなし。
注目: 6 スタック: {1}
行き止まりまで来たので最初の分岐点まで戻りノード 1 に注目して…
注目: 1 スタック: {3, 4, 5}
のようにスタックが処理されていきます。
コード自体は remove() の引数を 0 から queue.size()-1 に変えれば動くので省略します。
(実際はスタックなので queue を stack に変えるべきかもしれませんが。関数名も「depth-first search」から dfs() などにしても良いでしょう。)
迷路
dx や dy の並びを変えると黄色の及ぶ範囲が変わります。
何やらゴールまで一直線に向かっているような動きをしていますが、おそらく穴掘り法が深さ優先探索に似た動きをするからかと思います。
棒倒し法や壁伸ばし法だともっと黄色が広範囲になって迷っている感じがしました。
グラフは違いがわかりづらいし、地図に関しては自由度が高すぎて迷走しまくってたのでカットしました。
まとめ
以上、processing で幅優先探索と深さ優先探索を実装してみました。
他にも探索法は様々あるようですので、記事にしてみたいと思います。
最後まで読んでいただきありがとうございました。また次回。
