離散数学

離散数学 最短経路問題 落合秀也

その前に 前回の話 深さ優先探索アルゴリズム 開始点 から深さ優先探索を行うアルゴリズム S.pu() Wl S not mpty v := S.pop() I F[v] = l Tn, F[v] := tru For no u n A[v] S.pu(u) EnFor EnI EnWl (*) 厳密には初期化処理が必要だが省略している k 時間計算量 :O(n+m)

その前に 前回の話 深さ優先探索アルゴリズム 再帰呼び出しによる方法 深さ優先探索を行うアルゴリズム ( 再帰呼び出し版 ) Funton DFS(v) I F[v] = l Tn, F[v] := tru For no u n A[v] DFS(u) EnFor EnI EnFunton 頂点 から探索を行う場合 : DFS() を実行すれば良い 再帰呼び出しは 実際には 裏ではスタックを使って実行される

最短経路問題を考える ラベル付 ( 重み付 ) グラフ G=(V,E) が与えられたとき 頂点 から頂点 t への最短経路 -t を求めたい 辺のラベルの意味 : 地点間の道のり 地点間の移動時間 地点間の移動に要する燃料の量 状態の遷移で失う資金 最小コストでの移動経路を発見したい 9 = = = (*) 実際はコスト の道が存在する t

最短経路問題の解法 ダイクストラ法 すべての辺の重みが非負の場合に適用可能 貪欲法 (Gry Alortm) の一種 ベルマン フォード法 辺の重みに負があっても良いケースがある ( 有向グラフで 有向閉路の和が負でない場合 ) 動的計画法 (Dynm Prormmn) の一種 - 9 - t コストが 資金の支出の場合 マイナスは 収入を意味する

ダイクストラ法 (Dktr Alortm) 99 年 : Er Dktr によって考案された H 考え方 -- G(V,E) に対して 開始点 V から各頂点への最短経路を求める問題 いま すでに部分 H に関して 最短経路が導出されているとする からの距離が判明している H と接する v V-H に対し からの距離を考える その距離の最小値を与える v を H に追加する 赤字 : 判明している からの最短距離

ダイクストラ法 ( もう少し正確な定義 ) 用語の定義 : グラフ G(V,E) において u, v V, =(u,v) E とする 辺 =(u,v) の長さを l あるいは l (u,v) で表すとする 開始点を とする (u) で から u までの最短距離を表すとする prv(v) で から v への最短経路における v の直前の頂点を表す 挙動の定義 : V の部分集合 H を以下のように作成する 初期状態 : H = {}, ()=, (v)= (v ), prv(v)=null (v V) とする u H で辺 =(u, v) でつながっている v ( V-H) を考え (v) = mn =(u,v):u H { (u) + l } を計算する v V-H において 上記をさらに最小化する v を選定し その v を H に追加し その距離を (v) とおき その時の u を用いて prv(v)=u とす る H l (u,v) (u) (v) = mn {(u)+l } (u) (v) = mn {(u)+l } l (u,v) (v) または (v) のどちらか片方 を決定する

練習 以下のグラフに対し ダイクストラ法により 頂点 から各頂点への最短経路とその距離を求めよ

解答 : 頂点 最短経路 距離 9

ダイクストラ法の実現 : アルゴリズムの設計素直に上述の定義に従って考えると 準備するもの から u までの最小距離を格納する配列 : [u] 初期条件 : []=, (u に対して ) [u]= から v への最短経路で v の直前を格納する配列 : prv[v] 初期条件 : prv[v]=null 辺の長さを与える関数 : lnt(u,v) 最短経路が確定した頂点のリスト : H 初期条件 : H = {} (v) = mn =(u,v):u H { (u) + l } 方針 [v] を最小にする u H, v V-H の辺 (u,v) を見つける 見つかったら prv[v]=u, [v]= [v] とおき v を H に追加する 上記を H=V になるまで繰り返す

ダイクストラ法の実現 : アルゴリズムの設計工夫をしてみよう 最短経路が確定した頂点のリスト (H) を考え からの距離 (v) が最小になる v ( V-H) を H に追加していた ( そして これを H=V になるまで繰り返した ) 最短経路が確定していない頂点のリスト (Q) を考え からの距離 (v) を最小にする v( Q) を Q から削除する ( そして これを Q が空になるまで繰り返す ) 各 v( Q) において (v) の候補を常に計算できていれば Q から削除される段階で (v) が最小であれば そこから新たに (v) を計算をする必要はない

ダイクストラ法の実現 : 二つのアプローチ H Q その時点の周辺について計算最小値を与える頂点を取り込む最小値を与える頂点を除外する除外された周辺の頂点までの距離を計算する

練習 もう一つのダイキストラ法 (Q の中から最小値を与える頂点を取り除く方法 ) で 以下の頂点 から各頂点までの最短経路を求めよ

. []= と置く Q からは が取り出される に隣接する, の距離が計算される. Q から Q の中で最小の (u)= を与える が取り出される に隣接する, の距離が計算される

. Q から Q の中で最小の (u)= を与える が取り出される に隣接する, の距離が計算される. Q から Q の中で最小の (u)= を与える が取り出される に隣接する, の距離が計算される

. Q から Q の中で最小の (u)= を与える が取り出される に隣接する の距離が計算される. Q から Q の中で最小の (u)= を与える が取り出される に隣接する,, の距離が計算される

. Q から Q の中で最小の (u)= を与える が取り出される に隣接する の距離が計算される. Q から Q の中で最小の (u)= を与える が取り出される に隣接する の距離が計算される 9

9. Q から Q の中で最小の (u)=9 を与える が取り出される に隣接する の距離が計算される 9. Q から Q の中で最小の (u)= を与える が取り出される に隣接する の距離が計算される 9

. Q から Q の中で最小の (u)= を与える が取り出される に隣接する頂点はなし (Q の中で ). Q が空なので 終了 9 頂点 最短経路 距離 9 9

装置 Q Q の持つべきインタフェースを考察する 初期化時 : Q に V のすべてを投入する (v) : v V [u] 参照 Empty()? 実行時 : Q が空かどうかを判定する nky() Q から (u) を最小とする u を取り出す Q の内部を で整理する (Q がヒープの場合 ) Q

ダイクストラのアルゴリズム For v V [v] :=, prv[v] :=null Q.(v) EnFor [] := Wl Q not mpty u := Q.xtrtMn() For v n A[u] I [v] > [u] + lnt(u, v) Tn, [v] := [u] + lnt(u, v) prv[v]=u ( Q.nKy() -- t mplmntton o Q p ) EnI EnFor EnWl

ダイクストラ法 : 計算量の考察 Wl 文の内部は n 回実行される For 文の内部は nm 回実行される 実装によっては O(nm) となりえる Q にリストや配列を使う場合 Q.xtrtMn() に O(n) の時間を要する Q.xtrtMn() は n 回呼び出される O(n ) Wl Q not mpty u := Q.xtrtMn() For v n A[u] I [v] > [u] + lnt(u, v) Tn, [v] := [u] + lnt(u, v) prv[v]=u ( Q.nKy() ) EnI EnFor EnWl Q に 分ヒープを使う場合 Q.xtrtMn() に O(lo n) の時間を要する Q.xtrtMn() の呼び出しは n 回ある O(n lo n) [v] の更新に伴うヒープの組換え処理に O(lo n) の時間を要する [v] の更新は m 回発生する O(m lo n) O( (n+m) lo n )

装置 Q の実装 : リストを使った場合 Q.xtrtMn() ポインタ p を用意リストのすべての要素に対して 順に(u) を計算より小さい(u) が発見されたら p に u へのポインタを設定するすべての要素を確認したら p の先を リストから除外し その値を返す 開始 (u) = p

装置 Q の実装 : ヒープを使った場合 分ヒープ 親 子の関係になるように構成された 分木 根は最小となる Q.xtrtMn() 根を取り出し 再構成を行う 計算量 O(lo n) []= Q.nKy() []= の変化に合わせて再構成を行う 計算量 O(lo n) []= []= []= []=

ベルマン フォード法 Bllmn For Alortm 基本的な考え方 開始点 から への距離を とする 各頂点の開始点 からの距離は 辺の重みを加算しながら から拡散するように伝搬させる 各頂点では距離の最小値を採用する 上記を 頂点数 - 回行う

ベルマン フォード法 回目から + 回目への計算 ( 漸化式 ) を考える ここで は 拡散量 ( から伝搬した辺の数 ) に相当する 回目 ( 個の辺の伝搬を考えたとき ) における 頂点 から頂点 v までの最短距離を OPT(,v) とする このとき 以下が言える OPT(+, v) = mn u nr(v) {OPT(,u)+C uv } (*) ここで nr(v) は v の近隣頂点 ( 自分自身も含む ) の集合とするまた C uv は辺 (u,v) のコストとし 便宜上 C vv = とする 初期条件 (= のとき ) OPT(,)=, OPT(,v)= (v V, v )

OPT(+, v) = mn u nr(v) {OPT(,u)+C uv } の意味 OPT(,) OPT(,) C v C v v C v OPT(,v) OPT(,v) OPT(,)+C v OPT(,)+C v OPT(,)+C v OPT(,) C vv (=) OPT(+,v) は 上記で最小のものとする

練習 以下のグラフに対し ベルマンフォード法により 頂点 から各頂点までの最短距離を求めよ (*) ダイクストラ法との違いも考えてみよ

9 回目 回目

回目 回目

回目 回目

回目 回目 9

回目 9 回目 9

回目以降頂点最短距離 9 9

ベルマンフォードのアルゴリズム M[]= M[v]=, prv[v]=null (v V, v ) For =,, n- // n=ount(v) For =(u, v) n E I M[v] > M[u]+C M[v]=M[u]+C prv[v]=u EnI EnFor EnFor 時間計算量 : O(mn)

ベルマンフォード法の分散化 グラフ G(V,E) において 各頂点は 辺で接続するもう片方の頂点と通信を行うものとする u OPT(u) + Cuv このとき 各頂点 u から 頂点 v ( nr(u)) に向けて OPT(u)+Cuv を発信する 受信側の頂点 v では 受信した値の中 ( 他者からのものも含む ) で 最小のものを OPT(v) として選ぶ 開始点 の OPT() は に固定する という処理を行うと ベルマンフォード法を分散的に実装できる v

ベルマンフォード法の分散化 : 各頂点の動作 v v u u OPT(u) + C uv u OPT(u) OPT(u) + C uv v I OPT(v) > 受信結果 OPT(v) := 受信結果 EnI v u 頂点 u からの送信 ( 定期的に行う ) 頂点 v での受信と処理

今後の予定 月 日 : 休講 ( レポートで代替 ) 月 日 : 最小全域木 月 日 : 最大流問題 9