最短路 - 坂井・入江研究室 [東京大学情報

離散数学
09. 最短路
五島
DATE
:
離散数学
深さ優先以外の探索
離散数学
深さ優先以外の探索
 深さ優先探索：
 「visit した先にある」頂点を次に visit
 一般には，
 訪問済み頂点に隣接したどの頂点も次に訪問可能
深さ優先探索が選ぶ頂点:
当然こちらを先に
選ぶことも可能
離散数学
様々な探索戦略
 一般の優先度探索：
0
1
 目的に応じた判断基準で優先度
を決める
2
3
 深さ優先探索 (depth first search)
 開始点から遠い頂点を先に
深さ優先
4
0
1-1
5
 幅優先探索 (breadth first search)
 開始点に近い頂点を先に
2-1
1-2
2-2
2-3
幅優先
2-4
離散数学
探索の一般形
最前線: 訪問済みから1 hop
visit(s, G, visited) {
F = { s }; /* Frontier */
visited[s] = 1;
while (F  {}) {
u = F.delete_one();
for v  adjacents(u) {
if (visited[v] == 0) {
visited[v] = 1;
F.add(v);
}
}
ここでどのノードを選ぶか
}
（だけ）で探索順序が決まる
}
visited[v] = 1 
訪問済み
訪問済みから>1 hop
or
離散数学
様々な探索戦略の実現
 深さ優先探索
 F の中で最後に F に入ったものを選ぶ
 F をスタック (Last-In-First-Out; LIFO) にする
 コードでは，再帰呼び出しのコール・スタックで実現
 幅優先探索
 F の中で，開始点からの深さが最小のものを選ぶ
 F をキュー (First-In-First-Out: FIFO) にする
 一般の優先度探索
 目的に応じた判断基準で優先度を決定
 F を優先度付きキュー (priority queue) とする
離散数学
反復深化探索
 深さ制限つき深さ優先探索
 深さ優先探索を，開始点からの距離(再帰呼び出しを使うならその呼
び出しの深さ)に制限をつけて行う
 反復深化
 その深さ制限を徐々に増やしながら深さ優先探索を繰り返す
 メリット：
 深さ優先と同じメモリ量
 配列 visited を記憶しなくても，無限ループはしない
 幅優先に似た広く浅い探索
 浅い探索の結果を，「解の有望度」として，深い探索の順序制御
に用いることができる
離散数学
幅優先探索の性質
 幅優先探索によってたどられた辺(visited[v] = 1の実行を引きおこしたu 
v)の集合は，sから各頂点への最短路（最小の辺数で到達する道）を与え
る
 「重みなしグラフ(重み一律)の最短路の問題」
bfs_visit(s, G, visited) {
F = queue(s); /* C++ deque/list, Java : LinkedList */
visited[s] = 1;
while (not F.is_empty()) {
9
u = F.deq(); /* 前から出す */
for v  adjacents(u) {
if (visited[v] == 0) {
6
visited[v] = 1;
F.enq(v); /* 後ろに入れる */
}}}}
1
4
7
3
8
0
2
5
離散数学
最短路
離散数学
最短路の問題
 2点間を結ぶ最短の道を求める
 道の長さ:
 重みなしグラフ：含まれる辺の数，ホップ数
 重みつきグラフ：含まれる辺についた重みの和
1
3
4
3
2
3
3
1
7
4
離散数学
わかりやすい応用例 (1/2)
 渋滞考慮無しのカーナビ
 頂点：
交差点
辺：
2交差点を結ぶ一本道
 辺の重み：
その一本道を抜けるのにかかる時間
 渋滞無し  重みが時刻によらず一定
 2頂点間の最短路： 2つの交差点間を最も早く移動するドライブ・
ルート
 クイズ：
 一方通行，Uターン禁止，右折禁止などをどうモデル化する？
離散数学
わかりやすい応用例 (2/2)
 インターネットのルーティング
 頂点：
ネットワーク・ルータ
 辺：
ケーブル
 インターネットより下のレイヤ(2)で直接通信できるルータの対
 辺の重み：
パケットがそこを通ることに対するコスト
 ex) バンド幅の関数（バンド幅が大きければ小さい）
 2頂点間の最短路：パケットを配送する適切な道
離散数学
少し自明でない応用例 (1/2)
 時刻表を考慮した路線検索
 頂点 (t, A) ：時刻 t に駅 A にいるという「状態」
 辺：
 (t, A)  (u, B)：時刻 t に A駅を発車して時刻 u に B駅につく列車が
ある
 (t, A)  (u, A)：時刻 t から u まで A駅にとどまる
 辺の重み：かかる時間（上の例では u – t）
 (t, A) から (*, B) への最短路：時刻 t に A 駅にいる人が最早で B駅に
たどり着く経路
 一見グラフではないものが，しばしばグラフとして表現できる
離散数学
少し自明でない応用例 (2/2)
 編集距離
例
 数字間の類似度は，その絶対差
0 1 4 9
 3 と 4 の類似度は，|3 − 4| = 1
 ギャップ - と数字の類似度は 3
 数字列の類似度は，対応する数
字，ギャップ間の類似度の総和
 1234 と 124- の類似度は，
0 + 0 + 1 + 3 = 4．
 右の例の答え：
 01-49 と
 0263-
3
0
2
6
3
6
9
4
0
3
3
1
3
6
6
9
2
1
5
6
4
4
7
3
3
1
7
9
7
2
2
9
6
6
6
5
8
離散数学
アルゴリズム
1. 幅優先探索
 重みなしグラフのみ
2. Dijkstra （ダイクストラ）法（必修）
 幅優先探索とほぼ同じ考え方
 指定した一頂点から他の全頂点までの最短路を求める（一対全）
3. Floyd のアルゴリズム
 全ての頂点対間の最短路を求める（全体全）
離散数学
幅優先探索と最短路
 幅優先探索によって visit された頂点は，開始点からの最短路
 「重みなしグラフ（重み一律）の最短路の問題」
bfs_visit(s, G, visited) {
F = queue(s); /* C++ deque/list, Java : LinkedList */
visited[s] = 1;
while (not F.is_empty()) {
9
u = F.deq(); /* 前から出す */
for v  adjacents(u) {
if (visited[v] == 0) {
6
visited[v] = 1;
F.enq(v); /* 後ろに入れる */
}}}}
1
4
7
3
8
0
2
5
離散数学
Dijkstra 法
離散数学
Dijkstra 法の概要
 優先度つきグラフ探索の一種：
 これまでに見つかっている s * u の距離が最短の u を優先して visit
 あとはほぼ「一般的な探索方法」に従うだけ
 入力：重みつきグラフ G = A, E とその一頂点 s ( A)
 辺の重みは非負
 アルゴリズムは無向でも同様
 出力： D[i] (i  A) が，s から i への最短距離を与えるような配列
 最短路を与えるように変更するのは容易
離散数学
Dijkstra 法の概要
F
2
∞
12
10
∞
1
0
V
9
1 p
10
V : visited
U : unvisited
F : frontier
U
10
1
∞
11
q
∞
離散数学
Dijkstra 法：擬似コード
4
8
3
1
6
start
4
2
1
5
goal
Wu,v ：辺u  vの重み（距離）
dijkstra (s, G) {
V = {};
D = new int[n];
for (i = 0; i < n; i++) {
if (i == s) D[i] = 0;
else D[i] = ;
}
while (V  A) {
pick u  V that minimizes D;
V = V + { u };
for v  adjacents(u) {
d = D[u] + Wu,v ;
if (d < D[v]) D[v] = d;
}
}
}
離散数学
Dijkstra法の動き
 赤： S （意図：最短距離確定）
 緑：暫定最短距離 (startから赤だけを使う道の中での最短距離）
1
456
4
8
3
1
6
2
1
0
start
4
34
5
goal
789
離散数学
証明
F
2
∞
12
10
∞
1
0
V
9
1 p
10
V : visited
U : unvisited
F : frontier
U
10
1
∞
11
q
∞
離散数学
証明
 前半
 V 内の最短路は確定していると仮定
 すると，U 内の仮距離は，V 内の頂点のみを経由して到達できる最短
の長さ
 仮距離が最小の頂点 p  F を選んだとき，p までの最短路が V 内の頂
点のみからなることを言えば，p までの最短路を確定できる．
 p までの最短路が V 内の頂点のみからなる：
 U 内の頂点を経由して p に至る最短路があると仮定，
 その経路上，F 内の頂点を q とする．
 distance(s, p) > distance(s, q) + distance(p, q) ⋀ distance(p, q) ≥ 0
 distance(s, p) > distance(s, q) となり，矛盾．
離散数学
計算量
 基本
 while ループは常に n （頂点数）
回繰り返す
 ポイント
 集合 D の表現と操作（2行）
 単純アプローチ
 S ：配列 V[i] = 1 iff i  V;
 ：線形探索 O(n)
 全体の計算量 O(n2)
 密なグラフならこれ以上は難し
そう
dijkstra(s, G) {
V = {};
D = new int[n];
for (i = 0; i < n; i++) {
if (i == s) D[i] = 0;
else D[i] = ;
}
while (V  A) {
pick u  V that minimizes D;
V = V + { u };
for v  adjacents(u) {
d = D[u] + Wu,v ;
if (d < D[v]) D[v] = d;
}
}
}
離散数学
疎なグラフ用の Dijkstra 法
 集合 F をヒープで表現
 最小値の除去： O(log n)
 優先度の変更： O(log n)
 合計計算量
 O((n + m) log n)
 m  O(n) ならば O(n log n)
 現実の道路・鉄道・ネット
ワークetc.は?
dijkstra (s, G) {
F = priority_queue(V);
dijkstra(s, G) {
D = new int[n];
S = {};
for (i = 0; i < n; i++) {
D = new int[n];
if (i == s) D[i] = 0;
for (i = 0; i < n; i++) {
else D[i] = ;
if (i == s) D[i] = 0;
}
else D[i] = ;
while (F  {}) {
}
delete u  F that minimizes D;
while (S  V) {
pick u  V – S that minimizes D;
for v  adjacents(u) {
S = S + { u };
d = D[u] + Wu,v ;
for v  adjacents(u) {
if (d < D[v]) {
d = D[u] + Wu,v ;
D[v] = d;
if (d < D[v]) D[v] = d;
change priority of v in F to d;
}
}
}
}
}
}
}
離散数学
ヒープ
1
 二進木
0
1
3
2
2
 親 < 子（または，親 > 子）
0
0
1
1
 挿入，削除： O(log n)
3
1
2
2
1
3
2
2
離散数学
全対全最短距離
 方法 1： Dijkstra 法を各頂点を開始点として行う
 O(n3) または O(n (n + m) log n)
 方法 2： Floyd のアルゴリズム
 O(n3)
離散数学
Floyd のアルゴリズム
離散数学
Floyd のアルゴリズム
 概要：
 全対全最短距離
 O(n3)
 入出力：
 入力：辺重みつき有向グラフ G = V, E
 出力： D[i][j] が i から j への最短距離を与えるような 2次元配列 D
 仮定：
 Dijkstra 法と異なり，負の重みがあってもよい
 重みの和が負となる閉路がない
離散数学
Floyd のアルゴリズム
int D[−1 : n − 1][0 : n − 1][0 : n − 1];
 (*) のループの不変条件：
D[k][i][j] は，
floyd (graph G)
{
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
D[−1][i][j] = G.weight(i, j);
i から j への道で，
for (k = 1; k < n + 1; k++) // (*)
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
D[k][i][j] = min(D[k − 1][i][j] ,
D[k − 1][i][k] + D[k − 1][k][j];
0, 1, …, k のみを経由する
最短路の長さ
}
離散数学
考え方
 考え方：
 D[k − 1][i][j]： 0, 1, …, k − 1
のみを経由する i, j 間の最短距離から
 D[k ][i][j]： 0, 1, …, k − 1, k のみを経由する i, j 間の最短距離を求
める
 言い替え：
 D[k − 1][i][j]： 0, 1, …, k − 1 のみを経由する i, j 間の最短距離
が正しく分かっているとして，
さらに k も経由していいとしたら，どうすればいいか？
離散数学
k 回目のイタレーション
0, 1, …, k − 1 のみを経由する
i, j 間の最短距離
D[k − 1][i][j]
i
j
D[k − 1][i][k]
D[k − 1][k][j]
0, 1, …, k − 1 のみを経由する
i, k 間の最短距離
k
0, 1, …, k − 1 のみを経由する
k, j 間の最短距離
D[k][i][j] = min(D[k − 1][i][j], D[k − 1][i][k] + D[k − 1][k][j])
0, 1, …, k のみを経由する
i, j 間の最短距離
離散数学
k = 0 回目のイタレーション
どこも経由しない
i, j 間の最短距離
D[−1][i][j]
i
j
D[−1][i][0]
D[−1][0][j]
どこも経由しない
i, 0 間の最短距離
0
どこも経由しない
0, j 間の最短距離
D[0][i][j] = min(D[−1][i][j], D[−1][i][0] + D[−1][0][j])
0 のみを経由する
i, j 間の最短距離
離散数学
k = 1 回目のイタレーション
0 のみを経由する
i, j 間の最短距離
D[0][i][j]
i
j
D[0][i][1]
D[0][1][j]
0 のみを経由する
i, 1 間の最短距離
1
0 のみを経由する
1, j 間の最短距離
D[1][i][j] = min(D[0][i][j], D[0][i][1] + D[0][1][j])
0, 1 のみを経由する
i, j 間の最短距離
離散数学
動作例
0
1
1
2
1
0
1
0
1
1
0
2
3
3
1
0
1
3
1
0
3
0
1
0
1
1
2
0
1
0
2
3
4
3
1
2
3
0
1
2
3
0
0
1
2
3
1
4
0
1
2
1
2
3
4
0
1
0
3
1
2
3
0
D[k = 0]：0 を経由
2
3
0
1
0
0
1
2
0
1
2
0
1
1
D[k = 2]：0, 1, 2 を経由
3
0
1
2
3
0
0
1
2
3
1
3
0
1
2
1
2
3
4
0
1
2
2
3
0
1
0
3
1
2
3
0
3
1
2
3
0
D[k = −1]：初期化後
D[k = 1]：0, 1 を経由
D[k = 3]：0, 1, 2, 3 を経由
離散数学
Floyd のアルゴリズム
int D[n][n];
 D は2次元でよい
 単に3次元目を省略 →
floyd (graph G)
{
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
D[i][j] = G.weight(i, j);
for (k = 0; k < n; k++)
// (*)
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
D[i][j] = min(D[i][j] ,
D[i][k] + D[k][j];
 記憶量は O(n2) でよい
}
離散数学
一対一最短距離
離散数学
一対一最短距離？
 一対一最短距離：与えられた2点間の最短距離を求める
 Dijkstra 法（一対全）を使って全頂点までの距離をまず求め，
目的地までの最短距離を取り出す
 一対一だけを（一対全よりも）高速に計算する方法は知られていない
離散数学
探索問題
離散数学
抽象的（暗黙的）なグラフ
 データ構造として表せないようなグラフ
 ex) 巨大
 抽象的（暗黙的）なグラフ：
 隣接点の集合 adjacents(u) が計算できれば，「グラフ」と見ることが
可能
 ex) ゲームのグラフ
 頂点：ゲームの状態（盤面）
 u  v ：状態 u から状態 v へ「一手で」移ることが可能
離散数学
探索問題
 これまで述べた探索アルゴリズムは，抽象的なグラフに対しても適用可
能
 巨大な状態空間の中からある性質を持った「ゴール・解」の「探索」
  このような問題をしばしば「探索問題」と呼ぶ
離散数学
練習問題
 グラフ探索の考え方を使って，「8パズル」を解くプログラムを書いてみ
よ
2
3
4
7
1
5
8
1
2
3
4
5
6
7
8
グラフのノード数(の上界)は?
連結(どこからでもゴールできる)か?
最短(最小手数)でゴールするには?
6
ゴール
2
3
4
7
1
5
8
6
離散数学
探索問題の困難と戦略
 困難：探索空間が巨大（頂点数 n が大きい）
 すべてを探索するには時間がかかりすぎる
 メモリに収まりきらない（visited 配列すべてを記憶できない）
 目的：
 特定の頂点（ゴール，解）を見つけることで，
 全頂点を見る必要はない
 ゴールに早くたどり着く戦略（経験則，heuristics）が必要
離散数学
いくつかの経験則・戦略
 隣接頂点 adjacents(u) の順序付け
 答えに到達する可能性が高い頂点を先に探索
 頂点の「有望度」（例：解への近さ）を測る経験則が必要
 メモリの節約
 深さ優先探索で訪問済み頂点 (visited) を記憶しない
 同じ頂点を 2度訪問してしまう危険性？
● グラフが木で，あり得ない場合
● 許容される場合
 浅く広いグラフの場合になお有用（必要メモリ量 O(深さ)）
離散数学
挑戦しがいのある課題
 15パズル，ルービックキューブなど，状態空間が大きいパズルの解法
 ルービックキューブくらいなら課題2として良いかも

Download Report