離散数学

Size: px

Start display at page:

Download "離散数学"

ゆりかもちやま
8 years ago
Views:

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

2 その前に前回の話深さ優先探索アルゴリズム開始点から深さ優先探索を行うアルゴリズム 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)

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

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

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

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

7 ダイクストラ法 ( もう少し正確な定義 ) 用語の定義 : グラフ 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) のどちらか片方を決定する

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

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

10 ダイクストラ法の実現 : アルゴリズムの設計素直に上述の定義に従って考えると準備するものから 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 になるまで繰り返す

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

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

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

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

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

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

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

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

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

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

21 ダイクストラのアルゴリズム 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

22 ダイクストラ法 : 計算量の考察 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 )

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

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

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

26 ベルマンフォード法回目から + 回目への計算 ( 漸化式 ) を考えるここでは拡散量 ( から伝搬した辺の数 ) に相当する回目 ( 個の辺の伝搬を考えたとき ) における頂点から頂点 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 )

27 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) は上記で最小のものとする

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

29 9 回目回目

30 回目回目

31 回目回目

32 回目回目 9

33 回目 9 回目 9

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

35 ベルマンフォードのアルゴリズム 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)

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

37 ベルマンフォード法の分散化 : 各頂点の動作 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 での受信と処理

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

離散数学

離散数学最小全域木と最大流問題落合秀也今日の内容最小全域木プリムのアルゴリズム最大流問題フォードファルカーソンのアルゴリズム今日の内容最小全域木プリムのアルゴリズム最大流問題フォードファルカーソンのアルゴリズム最小全域木を考える Minimum Spanning Tree Problem ラベル付 ( 重み付 ) グラフ G(V, E) が与えられたときラベルの和が最小となる全域木を作りたい