アルゴリズムイントロダクション 第24章 単一始点最短路問題 アルゴリズムイントロダクション　第24章 単一始点最短路問題 2009.6.21 Naoya Ito

第24章の構成 単一始点最短路問題とは 単一始点最短路問題の考え方 単一始点最短路問題を解く3つのアルゴリズム ベルマン･フォードのアルゴリズム トポロジカル･ソートによる解法 ダイクストラのアルゴリズム 線形計画問題を単一始点最短路問題とみなして解く (省略) 緩和操作と最短路の各性質の証明

単一始点最短路問題とは

単一始点最短路問題とは 前提: 重み付き有向グラフ 特定の開始頂点 s から任意の頂点 v までの最短路を求める問題 3 9 5 11 例: シカゴからボストンまでの最短経路 ※最短 ･･･ 重み最小 (経路本数最小ではない) 6 3 9 3 4 s 2 1 2 7 5 5 11 6

最短路重み δ(u, v) w(u, v) ･･･ u → v の重み δ(u, v) ･･･ u → v の最短路重み 6 3 9 3 4 s 2 1 2 7 5 5 11 6

単一始点最短路問題で得られる情報 (1) 始点 s から任意の頂点 v までの最短路重み δ(s, v) (2) 任意の頂点 v までの経路 6 3 9 各頂点内の数字が δ(s, v) 緑の辺の集合が最短路木 「始点から特定の頂点への経路や最短路重み」ではなく、「始点から各頂点へのそれ」を求めているという点に注意 3 4 s 2 1 2 7 5 5 11 6

派生問題 単一始点最短路問題 (1 to N) が解けると以下の問題も解ける 単一目的地最短路問題 (N to 1) 1 to N を N to 1 に変更すれば OK 単一点対最短路問題 (1 to 1) 単一始点最短路から自明 一見、1 to 1 なので単一始点最短路を求めるよりも良い方法がありそうだが、最悪の場合に漸近的に速く実行できる物は知られていない 全点対最短路問題 (N to N) これはもっと良い方法がある → 第25章

単一始点最短路問題の考え方

ざっくりとした解き方の説明 各頂点に始点 s からの重みの和を記録。最初は全部∞ 適当なアルゴリズムで各辺を調べて、頂点に記録している重みが最短路のそれになるよう調整 6 6 ∞ ∞ 3 9 3 3 4 4 2 1 2 7 2 1 2 7 5 5 ∞ ∞ 5 11 6 6

複数のアルゴリズム 前提条件により最適なアルゴリズムが変わる アルゴリズムの違い 負の重み、閉路のありなし (後述) 各辺を調べる(緩和する、後述) 回数、調べる順番に相違がある 当然、調べる回数/順番が多い方が、より汎用的な目的に使えるアルゴリズムになる

各アルゴリズムの前に知っておくべきこと 最短路の部分構造最適性 負の重みを持つ辺の扱い 閉路の扱い 最短路の表現 緩和 最短路と緩和の性質

各アルゴリズムの前に知っておくべきこと 最短路の部分構造最適性 負の重みを持つ辺の扱い 閉路の扱い 最短路の表現 緩和 最短路と緩和の性質

1. 最短路の部分構造最適性 最短路の部分経路は最短路 部分構造最適性 証明: 補題 24.1 動的計画法、貪欲アルゴリズムが適用できる可能性 ダイクストラ法は貪欲戦略を採っている

各アルゴリズムの前に知っておくべきこと 最短路の部分構造最適性 負の重みを持つ辺の扱い 閉路の扱い 最短路の表現 緩和 最短路と緩和の性質

2. 負の重みを持つ辺の扱い 全体として負の重みを持つ閉路、が問題 (閉路にならない) 負の重みの経路 その閉路を巡回すると最短路重みを無限に小さくできる s → v に至る経路上に負の重みの閉路が存在するなら δ(s, v) = -∞ とする ∴ 最短路は負の重みを持つ閉路を含まない (閉路にならない) 負の重みの経路 扱えるアルゴリズム/扱えないアルゴリズム 2 5 8 5 11 -∞ -3

各アルゴリズムの前に知っておくべきこと 最短路の部分構造最適性 負の重みを持つ辺の扱い 閉路の扱い 最短路の表現 緩和 最短路と緩和の性質

3. 閉路の扱い (前述通り) 最短路は負の重みを持つ閉路を含まない 正の重みを持つ閉路もまた含まない その閉路を取り除くと同一の始点と目的地を持つより小さな重みを持つ経路が生じるから 6 5 8 5 11 19 3

各アルゴリズムの前に知っておくべきこと 最短路の部分構造最適性 負の重みを持つ辺の扱い 閉路の扱い 最短路の表現 緩和 最短路と緩和の性質

4. 最短路の表現 頂点v に対して別の頂点か NIL を値とする先行点 π[v] π[v] = u ･･･ u → v が最短路 π[u] = x ･･･ x → u が最短路 π[x] = s ･･･ s → x が最短路 s → x → v → u が最短路 第22.2節の PRINT-PATH(G, s, v) で最短路を出力できる

各アルゴリズムの前に知っておくべきこと 最短路の部分構造最適性 負の重みを持つ辺の扱い 閉路の扱い 最短路の表現 緩和 最短路と緩和の性質

5. 緩和 (RELAX) #1 頂点に保存する重み ･･･ 最短路推定値 d[v] とする (最短路の重みの上界) 緩和 ※d[v] と δ(s, v) を混同しないこと 緩和 (u, v) に対する緩和操作 ･･･ u を経由することで v を改善できるなら d[v] およびπ[v] を更新する 緩和により d[v] が減少しπ[v] が更新される 緩和を適当な順序でグラフに施していくことで、最短路木を得る

一つ前の頂点 (先行点) から緩和するところがポイント 5. 緩和 (RELAX) #2 u v u v 2 2 5 9 5 7 RELAX(u, v, w) 一つ前の頂点 (先行点) から緩和するところがポイント u v u v 2 2 5 6 5 6 RELAX(u, v, w) 緩和の結果何も更新されないこともある

5. 緩和#3 擬似コード RELAX(u, v, w) if d[v] > d[u] + w(u, v) then d[v] ← d[u] + w(u, v) π[v] ← u

ついでに、初期化の擬似コード INITIALIZE-SINGLE-SOURCE(G, s) for 各頂点 v ∈ V[G] do d[v] ← ∞ π[v] ← NIL d[s] ← 0

各アルゴリズムの前に知っておくべきこと 最短路の部分構造最適性 負の重みを持つ辺の扱い 閉路の扱い 最短路の表現 緩和 最短路と緩和の性質

6. 最短路と緩和の性質 本章のアルゴリズムの正当性を証明するための、最短路と緩和に関する諸性質 三角不等式 上界性 無経路性 収束性 経路緩和性 先行点グラフの性質 本章の各アルゴリズムは、なぜそれで最短路木、最短路重みが得られるのかそれほど直感的ではないので、上記の諸条件から理詰めで正当性を考えると良い

6. 最短路と緩和の性質 三角不等式 上界性 無経路性 収束性 経路緩和性 先行点部分グラフの性質

三角不等式 任意の辺 (u, v) ∈ E に対して δ(s, v) ≦ δ(s, u) + w(s, v) が成立する w(s, v) s u v 5 2 5 7 δ(s, u) δ(s, v)

6. 最短路と緩和の性質 三角不等式 上界性 無経路性 収束性 経路緩和性 先行点部分グラフの性質

上界性 すべての v ∈ V に対して、d[v] ≧ δ(s, v) が成立する。ひとたび d[v] が値 δ(s, v) を取ると、その後は決して変化しない u v RELAX(u, v, w) u v 2 2 5 6 5 6 d[v] = δ(s, u)

6. 最短路と緩和の性質 三角不等式 上界性 無経路性 収束性 経路緩和性 先行点部分グラフの性質

無経路性 s u v 5 5 ∞ 頂点 s から v に至る経路がない場合、d[v] = δ(s, v) = ∞ が成立する 5 ∞ d[v] = δ(s, v) 初期化ですべての d[v] は ∞になっていて、d[v] が更新されるのは緩和操作時だけ。緩和操作は先行点から行われるが、孤立した頂点は先行点がないので∞から更新されることがない

6. 最短路と緩和の性質 三角不等式 上界性 無経路性 収束性 経路緩和性 先行点部分グラフの性質

収束性 ある u, v ∈ V に対して、s ～> u → v を G の最短路と仮定する。辺 (u, v) に対して緩和を実行する前に d[u] = δ(s, u) が成立した時点があったとすると緩和実行後は常に d[v] = δ(s, v) が成立する u v u v 2 2 5 9 5 7 RELAX(u, v, w) δ(s, v) δ(s, u)

6. 最短路と緩和の性質 三角不等式 上界性 無経路性 収束性 経路緩和性 先行点部分グラフの性質

経路緩和性 p = <v0, v1, ･･･, vk> が s = v0 から vk に至る最短路で、p の辺が (v0, v1), (v1, v2), ..., (vk-1, vk) の順序で緩和されたとき、d[vk] = δ(s, vk) が成立する。 この性質は他の任意の緩和操作とは無関係に成立する。たとえこれらの緩和操作の実行が p の緩和操作の実行とシャッフルされた順序で実行されたとしてもこの性質は成立する。

6. 最短路と緩和の性質 三角不等式 上界性 無経路性 収束性 経路緩和性 先行点部分グラフの性質

先行点部分グラフの性質 すべての v ∈ V に対して d[v] = δ(s, v) が成立するとき、先行点部分グラフは s を根とする最短路木である この性質から、すべての頂点を緩和で δ(s, v) にすることができれば目的を達成したことになる、と言える 先の経路緩和性から、定められた順序で緩和していけば d[vk] = δ(s, vk) が得られることは分かっている。よって 順番に緩和 → 全部の頂点が δ → 最短路ゲット というのがアルゴリズムの基本方針となる

3つのアルゴリズム ベルマン･フォードのアルゴリズム トポロジカル・ソート順序の緩和 ダイクストラのアルゴリズム O(VE) 負の重みOK、(負の重みは持たない) 閉路OK トポロジカル・ソート順序の緩和 Θ(V + E) 負の重み OK、閉路なし ダイクストラのアルゴリズム O(VlgV + E) or O((V+E)lgV) 負の重みなし

ベルマン･フォードの アルゴリズム

ベルマン・フォードのアルゴリズム 一般の単一始点最短路問題を解く BELLMAN-FORD(G, w, s) 負の重みを持つ辺を含んでも OK 負の重みを持つ閉路の存在をチェックすることができる BELLMAN-FORD(G, w, s) 負の重みを持つ閉路がない ･･･ 返値 TRUE d[v] と π[v] も想定通りに埋まる 負の重みを持つ閉路がある ･･･ 返値 FALSE

|V| - 1 回、すべての辺を緩和するとすべての v に対して d[v] = δ(s, v) になる ベルマン・フォードのアルゴリズムの方針 |V| - 1 回、すべての辺を緩和するとすべての v に対して d[v] = δ(s, v) になる すべての v に対して... → 先行点部分グラフの性質から、グラフは最短路木

ベルマン・フォードのアルゴリズムの動き ∞ ∞ ∞ ∞ 6 ∞ 7 ∞ 5 -2 6 -3 8 7 2 -4 7 9 5 -2 6 -3 8 |V| - 1 回ループし、ループ毎に各辺を緩和する 左はループ開始直前 -3 8 s 7 2 -4 7 ∞ ∞ 9 5 6 ∞ ループ1回目。始点 s 以外の頂点は d[v] = ∞ なので、始点 s の出辺だけ d が更新される (緑の辺は先行点の値) -2 6 -3 8 s 7 2 -4 7 7 ∞ 9

ベルマン・フォードのアルゴリズムの動き 6 4 7 2 2 4 7 2 5 -2 6 -3 8 7 2 -4 7 9 5 -2 6 -3 8 ループ2回目。1回目のループで d が減少した頂点からの出辺の緩和により2頂点が更新 -3 8 s 7 2 -4 7 7 2 9 5 2 4 -2 6 ループ3回目。2回目のループで d が減少した頂点からの出辺の緩和により更新 -3 8 s 7 2 -4 7 7 2 9

ベルマン・フォードのアルゴリズムの動き 2 4 7 -2 5 -2 6 -3 8 7 2 -4 7 6 ループ4回目 (最後)。3回目のループで d[v] が減少した頂点からの出辺の緩和により更新 ループを抜けた時点での d と π の値が最終的な値 -2 6 -3 8 s 7 2 -4 7 7 -2 6

擬似コード BELLMAN-FORD(G, w, s) INITIALIZE-SINGLE-SOURCE(G, s) for i ← 1 to |V[G]| - 1 do for 各辺(u, v) ∈ E[G] do RELAX(u, v, w) for 各辺 (u, v) ∈ E[G] do if d[v] > d[u] + w(u, v) then return FALSE return TRUE 各辺の緩和操作 負の重みを持つ閉路の存在確認 (あったら FALSE を返す) 正当性は補題 24.4

アルゴリズムの正当性 なぜこれで最短路木が得られるのか? 証明すべきこと ･･･ "|V| - 1 回繰り返した後、すべての頂点 v に対して d[v] = δ(s, v) になっている" これが分かれば先行点部分グラフの性質から最短路木が得られることが証明できる 経路緩和性で証明 (補題 24.2) 各辺はループ毎に必ず緩和される → 経路緩和性の順序に沿って緩和が行われたと考えることができる、という点がポイント s → v の経路 p = <v0, v1 ... vk> としたとき、経路 p は高々 |V| - 1 個の辺を持つ。∴ k ≦ |V| - 1 i = 1, 2 ... k に対して (vi-1, vi) は i 回目の繰り返しで緩和される辺のひとつ → 経路緩和性が成立する v0 = s, Vk = v であり経路緩和性から d[v] = d[vk] = δ(s, vk) = δ(s, v)

計算量 O(VE) 初期化 O(V) |V| - 1 のループ一回あたり O(E) → O(VE) 負の閉路発見の for ループの実行時間 O(E)

トポロジカル･ソート順 による緩和

トポロジカル・ソート順に緩和 閉路のない有効グラフ限定 閉路がないならトポロジカル･ソート順に緩和するのがベルマン･フォードより速い Θ(V + E)

方針 グラフをトポロジカル･ソートして頂点に線形順序を与える ソート順に頂点を選び、その頂点の出辺を緩和する 各頂点は一回だけ選択される

アルゴリズムの動き ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ 6 1 -2 5 2 7 -1 4 2 3 6 1 -2 5 2 7 -1 4 s -2 ∞ 5 2 ∞ 7 ∞ -1 ∞ ∞ 4 2 3 閉路のない有向グラフをトポロジカル・ソートする 6 1 s -2 ∞ 5 2 ∞ 7 ∞ -1 ∞ ∞ 4 2 3 左の頂点から順番に選択、選択された頂点の出辺を緩和する

アルゴリズムの動き 6 1 s ∞ 5 2 2 7 6 -1 -2 ∞ ∞ 4 2 3 6 1 s -2 ∞ 5 2 2 7 6 -1 6 4 4 2 3

アルゴリズムの動き 6 1 s ∞ 5 2 2 7 6 -1 -2 5 4 4 2 3 6 1 s -2 ∞ 5 2 2 7 6 -1 5 3 4 2 3

アルゴリズムの動き 6 1 s -2 ∞ 5 2 2 7 6 -1 5 3 4 2 3

擬似コード DAG-SHORTEST-PATHS(G, w, s) G の頂点をトポロジカル･ソートする INITIALIZE-SINGLE-SOURCE(G, s) for 各頂点 u (トポロジカル・ソート順に) do for 各頂点 v ∈ Adj[u] do RELAX(u, v, w)

アルゴリズムの正当性 なぜこれで最短路木が得られるのか? 証明すべきこと ･･･ "アルゴリズム終了時点で、すべての頂点 v に対して d[v] = δ(s, v) になっている" これが分かれば先行点部分グラフの性質から最短路木が得られることが証明できる 経路緩和性で証明 (補題 24.5) 頂点をトポロジカルソート順に処理して緩和するから、経路緩和性が成立する 詳細は教科書参照のこと

計算量 Θ(V + E) トポロジカル・ソート Θ (V + E) 初期化 O(V) for ループの繰り返し回数 |E|、ループ一回あたり Θ(1) ・・・Θ(E)

ダイクストラの アルゴリズム

ダイクストラのアルゴリズム 全ての辺の重みが非負であるグラフの単一始点最短路問題を高速に解く w(u, v) ≧ 0 ベルマン･フォードのアルゴリズムより高速に解ける

ダイクストラ法の方針 最小の最短路推定値を持つ頂点 u を選択し、u の出辺を緩和･･･を繰り返す 貪欲戦略 一度選択した頂点は二度と選択されない 始点 s からの最終的な最短路重みが既に決まっている頂点の集合 S を管理 u ∈ V - S u を選択 → u を S に追加 → u の出辺を緩和 u の選択に min 優先度付きキュー Q を用いる

ダイクストラのアルゴリズムの動き ∞ ∞ ∞ ∞ 10 ∞ 5 ∞ 1 10 2 3 9 4 6 7 5 2 1 Q = V - S にある 10 2 3 選択された u (最小の最短路推定値) 9 s 4 6 7 S にある 5 ∞ ∞ 2 10 1 ∞ 最初に選択された始点 s からの出辺が緩和される 始点 s は S に加えられる。次に選択されるのは、S にまだ入ってないもので最小の最短路推定値 (5) を持つ頂点 10 2 3 9 s 4 6 7 5 5 ∞ 2

ダイクストラのアルゴリズムの動き 8 14 5 7 8 13 5 7 1 同様に u からの出辺が緩和される そして Q から次の u を選ぶ 10 2 3 9 s 4 6 7 5 5 7 2 8 1 13 同様に繰り返す 10 2 3 9 s 4 6 7 5 5 7

ダイクストラのアルゴリズムの動き 8 9 5 7 8 9 5 7 1 緩和! 緩和!! 10 2 3 9 4 6 7 5 1 s 4 6 7 5 5 7 8 1 9 おつかれさまでした 最短路重み d, 最短路木 π がそれぞれ得られました 10 2 3 9 s 4 6 7 5 5 7

擬似コード DIJKSTRA(G, w, s) INITIALIZE-SINGLE-SOURCE(G, s) S ← φ Q ← V[G] while Q ≠ φ do u ← EXTRACT-MIN(Q) S ← S ∪ {u} for 各頂点 v ∈ Adj[u] do RELAX(u, v, w)

アルゴリズムの正当性 なぜこれで最短路木が得られるのか? 証明すべきこと ･･･ "停止した後、すべての頂点 v に対して d[v] = δ(s, v) になっている" これが分かれば先行点部分グラフの性質から最短路木が得られることが証明できる while ループの各繰り返しの開始直前に既に d[v] = δ(s, v) が各頂点 v ∈ S について成立している(定理 24.6)ことから証明できる 貪欲戦略に基づく選択が正しい

計算量 min 優先度付きキューの実現方法に依存 二分木ヒープ フィボナッチヒープ EXTRACT-MIN が |V| 回 DECREASE-KEY が |E| 回 二分木ヒープ EXTRACT-MIN, DECREASE-KEY 共に O(lg V) → ダイクストラ法 O((V+E) lg V) フィボナッチヒープ EXTRACT-MIN ･･･ O(lg V) ※ならし DECREASE-KEY ･･･ O(1) ※ならし → ダイクストラ法 O(VlogV + E)

線形計画問題への応用

線形計画問題とは 1次式の不等式で与えられる一組の制約の下で、線形の目的関数を最適化する問題 (例題) 2種類の容器 A, B を作るのに2台の機械 M1、M2 を使う 容器 A 1 個に M1 を 2 分、M2 を 4 分使う 容器 B 1 個に M1 を 8 分、M2 を 4 分使う 容器 A の利益は 29円、容器B の利益は 45円 利益を最大化するにはどのように計画すれば良いか?

続き (例題の解き方) A, B を1時間あたりそれぞれ x 個、y個作るとすると 2x + 8y ≦ 60 4x + 4y ≦ 40 という制約の下で 目的関数 f = 29x + 45y を最大化するような解 (xi, yi) を求めれば良い

幾何学的には･･･ ax + by = c a'x + b'y = c' 可能領域 O x 各制約を満たす領域 ･･･ 可能領域にある解のうち目的関数を最大化するものを選ぶ (最適解は必ず可能領域の頂点になるという性質を利用する → シンプレックス法)

一般の線形計画問題はシンプレックス法などで解く 線形計画と単一始点最短路問題 一般の線形計画問題はシンプレックス法などで解く ただしシンプレックス法は必ずしも多項式時間で動作しない 特別な場合において、他のアルゴリズムが使える 単一始点最短路問題に帰着させることができるケースがある 差分制約式系

差分制約式系 線形計画問題において、制約式が以下のような差分制約の場合 x1 - x2 ≦ 0 x1 - x5 ≦ -1

差分制約式系の線形計画行列 差分制約式系の制約式は、P280 のような行列に置き換えられる Ax ≦ b この m x n の線形計画行列Aを転置すると、n 個の頂点と m 個の辺を持つグラフ(隣接行列) に等しい この制約グラフの単一始点最短路を求めたとき、その最短路重みの値のベクトルが実行可能解 (可能領域にある解のひとつ) になる ベルマン・フォードのアルゴリズムが使える → 差分制約式系の線形計画問題は O(VE) すなわち多項式時間で解ける

まとめ 単一始点最短路問題を解くアルゴリズムについて学んだ ベルマン･フォードのアルゴリズム 閉路なし有向グラフ (トポロジカル･ソート) ダイクストラのアルゴリズム 各頂点の選択順序、緩和操作の回数がそれぞれ異なる。またそれにより汎用性/効率性が変わる 単一始点最短路問題は線形計画問題にも応用できる場合がある

参考文献 金谷健一, これなら分かる最適化数学‐基礎原理から計算手法まで, 共立出版, 2005