こんにちは。
今回は「ダイクストラ法」を扱います。
これで単純なグラフや迷路などは最短経路が求められるようになりました。
しかし、エッジも値を持つような、重みつきのグラフなどを対象にはできません。
そんなときに登場するのが「ダイクストラ法」です。
目次
ダイクストラ法とは
ダイクストラ法は、ノード間の距離が 1 ではなく自然数の "重み" を持つようなグラフについて最短経路を求めるアルゴリズムです。
幅優先探索の発展形とも言えるようなもののようです。
ちなみに「ダイクストラ」は人の名前で、オランダの計算科学者エドガー・ダイクストラさんが考案したことに由来するそうです。
(ダイクストラのスペルは Dijkstra らしいです。初見じゃ読めないですよね。)
重みつきグラフの最短経路と言われてもパッと出てこないですが、カーナビの経路案内や鉄道の乗り換え案内などが身近な例かと思います。
重みがどれも同じだった場合、幅優先探索よりも早くなるとかならないとか。
アルゴリズム
詳しい説明は数多ありますので、雰囲気だけ説明します。
全ノードの始点からの距離を暫定的に無限大にし、始点から始点までの距離を 0 に決定した盤面について、始点からの距離が最も近いノードを見つけ、そこまでの距離を始点からの距離として確定させます。
先程見つけたノードを中心に見て距離が一番近いノードを暫定のノードの中から見つけ、そこまでの距離が現在値よりも小さければ更新します (まだ暫定)。
この、始点からの距離が一番近いノードを見つけて確定、そこから一番近いノードを更新、という操作を全てのノードが確定されるまで繰り返します。
最終的に各ノードが持っている「始点からの距離」の値が、始点からの最短距離になります。
丁寧な説明は、例えばこちらなど。
実装
では実装に移りますが、基本的には前回つくった幅優先探索のプログラムを改変することでダイクストラ法を実装します。
ダイクストラ法の大枠は幅優先探索なので使い回せるかなと思ったのですが、冗長だったり非効率だったりする部分も出てくるかもしれません。
大きな違いとしては、
"重み" を管理する配列
weightsを追加した見たかどうかではなく確定したかどうかで判断したいため
isCheckedがisFixedになった (中身は同じ)queueの中から最短のものを探すためcurrentの取り出しがやや複雑になった"重み" を考慮しながら処理するようになった
といったところでしょうか。
グラフ
今回は下図のような重みつきグラフを対象にします。
重みつきグラフではエッジだけでなく重みも考えなければいけません。
単純には、重みの情報を持った配列を追加すれば良いでしょう。
int[][] edges = {{1, 2}, {0, 3, 5}, {0, 3, 4}, {1, 2, 4, 5}, {2, 3, 5}, {1, 3, 4}}; int[][] weights = {{0, 2, 4, 0, 0, 0}, {0, 0, 0, 2, 0, 7}, {0, 0, 0, 1, 4, 0}, {0, 0, 0, 0, 2, 4}, {0, 0, 0, 0, 0, 3}, {0, 0, 0, 0, 0, 0}};
edges はこれまでと同様、ノード i につながっているノードの番号を edges[i] に入れておきます。
weights はノード i とノード j をつなぐエッジに重み w があった場合、weights[i][j] = w となる二次元配列です。
これはいわゆる上三角行列の形になっていますが、下三角でも、上下どちらも埋めた行列でも問題ありません。
今回は幅優先探索のプログラムを再利用する形でつくっていったので edges と weights の両方を使っていますが、やり方によっては weights だけでもノード間のつながりを取得できます。
weights を取り出したとき、0 ならつながり無、0 より大きければつながり有ということになりますので、
for(int i = 0; i < weights[current].length; i ++){ int next = 10000; if(weights[current][i] > 0){ next = i; } else{ continue; } // 以下に処理が続く }
next の取得をこんな風にすれば良いと思います。
また、queue からは「暫定的に始点から最も近いノード」を取り出すので、幅・深さ優先探索のときのように単純に queue の端から取り出すだけではうまくいきません。
int minDist = 10000; int minNode = 10000; int index = 10000; for(int i = 0; i < queue.size(); i ++){ // queue 全体について int node = queue.get(i); // queue 内 i 番目のノードの番号を取得 if(dist[node] < minDist){ // そのノードが始点により近ければ // 更新 minDist = dist[node]; minNode = node; index = i; } } int current = minNode; isFixed[current] = true; queue.remove(index);
求めたいノードの番号とその始点からの距離を入れておく変数を用意します。(index は remove() の都合で必要)
queue 全体についてループを回し、queue 内 i 番目のノード node で dist[node] が minDist の現在地より小さければ、諸々の変数を更新します。
queue を見終えたところで current や isFixed[current] を更新し、queue から index 番目のノード minNode を消します。
あとはだいたい幅優先探索のコードと似ていますが、ところどころで "重み" を考慮した処理が出てきます。
というわけで、エッジと "重み"、始点、終点の情報を受け取って最短経路を出力する関数 dijkstra() はこんな形になりました。
void dijkstra(int[][] edges, int[][] weights, int start, int end){ int n = edges.length; boolean[] isFixed = new boolean[n]; for(int i = 0; i < n; i ++){ isFixed[i] = false; } isFixed[start] = true; IntList queue = new IntList(); queue.append(start); int[] dist = new int[n]; for(int i = 0; i < n; i ++){ dist[i] = 10000; } dist[start] = 0; int[] prev = new int[n]; for(int i = 0; i < n; i ++){ prev[i] = 10000; } while(queue.size() > 0){ int minCost = 10000; int minNode = 10000; int index = 10000; for(int i = 0; i < queue.size(); i ++){ int node = queue.get(i); if(dist[node] < minCost){ minCost = dist[node]; minNode = node; index = i; } } int current = minNode; isFixed[current] = true; queue.remove(index); if(dist[current] < minCost){ continue; } for(int i = 0; i < edges[current].length; i ++){ int next = edges[current][i]; if(isFixed[next] == true){ continue; } int newCost = dist[current] + weights[current][next]; if(newCost < dist[next]){ queue.append(next); dist[next] = newCost; prev[next] = current; } } } IntList route = new IntList(); int p = end; while(true){ route.append(p); if(p == start){ break; } p = int(prev[p]); } route.reverse(); println(route); }
はじめに挙げたような重みつきグラフで、ノード 0 からノード 5 までの最短経路を探してもらうと、
IntList size=4 [ 0, 1, 3, 5 ]
と出力されました。合っていそうです。
地図
続いて、迷路や地図のようなものを対象としてダイクストラ法で最短経路を求めます。
今回も先程書いたコードから、二次元配列にしたりベクトルを使ったりします。
ArrayList<PVector> dijkstra(int[][] map, int[][] weights, PVector start, PVector end){ int[] dx = {-1, 1, 0, 0}; int[] dy = {0, 0, -1, 1}; int nx = map.length; int ny = map[0].length; boolean[][] isFixed = new boolean[nx][ny]; for(int i = 0; i < nx; i ++){ for(int j = 0; j < ny; j ++){ isFixed[i][j] = false; } } isFixed[int(start.y)][int(start.x)] = true; ArrayList<PVector> queue = new ArrayList<PVector>(); queue.add(start); int[][] dist = new int[nx][ny]; for(int i = 0; i < nx; i ++){ for(int j = 0; j < ny; j ++){ dist[i][j] = 10000; } } dist[int(start.y)][int(start.x)] = 0; PVector[] prev = new PVector[nx*ny]; for(int i = 0; i < nx*ny; i ++){ prev[i] = new PVector(10000, 10000); } while(queue.size() > 0){ int minCost = 10000; PVector minNode = new PVector(10000, 10000); int index = 10000; for(int i = 0; i < queue.size(); i ++){ PVector node = queue.get(i); if(dist[int(node.y)][int(node.x)] < minCost){ minCost = dist[int(node.y)][int(node.x)]; minNode = node; index = i; } } PVector current = minNode; isFixed[int(current.y)][int(current.x)] = true; queue.remove(index); visited.add(current); if(dist[int(current.y)][int(current.x)] < minCost){ continue; } 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(isFixed[nexty][nextx] == true){ continue; } if(map[nexty][nextx] == 1){ continue; } int newCost = dist[int(current.y)][int(current.x)] + weights[nexty][nextx]; if(newCost < dist[nexty][nextx]){ queue.add(new PVector(nextx, nexty)); dist[nexty][nextx] = newCost; prev[nexty*ny+nextx] = current; } } } 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); } return(route); }
ここで、map や weights はcsvファイルでつくっておき、読み込んでおきます。
processingの備忘録 -迷路- - プログラミングの備忘録
processingの備忘録 -幅優先探索・深さ優先探索- - プログラミングの備忘録
processingの備忘録 -txt、csvの生成- - プログラミングの備忘録
processingの備忘録 -画像、テキストの読み込み- - プログラミングの備忘録
map を用意しましたが、壁の情報は weights に非常に大きな "重み" をつけておくことで表せると思います。
(井戸型ポテンシャルみたいな感じで、場合によっては漏れ出すこともあるかもしれませんが。)
まあ、ここでは幅優先探索のプログラムを再利用する形でつくったので、細かい改善は今後やっていけば良いかなと思っています。
実行してみると、重みなしの通常の地図は幅優先探索チックに探索してくれますし、
壁無しで weights だけを指定した場合も、山 (黒い、weights の値が大きい部分) を避けるような経路が示されることが見えると思います。
weights を noise() で指定してみると、
谷 (色の薄い、weights の値が小さい部分) を縫うような経路が出ます。
ちなみに、weights の設定は以下のような感じです。
float yoff = 0; for(int y = 0; y < n; y ++){ float xoff = 0; for(int x = 0; x < n; x ++){ terrain[x][y] = map(noise(xoff, yoff), 0, 1, 0, 10); xoff += 0.3; } yoff += 0.3; }
processingの備忘録 -3次元グラフ- - プログラミングの備忘録
まとめ
以上、processing にダイクストラ法を実装してみました。
これをさらに改良した (?) A*アルゴリズムというものもあるようですので、今度つくってみたいと思います。
その他、気になった探索法も触ってみるかもしれません。
最後まで読んでいただきありがとうございました。また次回。
