第25章 単一始点最短路 3節 Bellman-Fordのアルゴリズム アルゴリズムイントロダクション Bellman-Fordのアルゴリズム Dijkstraのアルゴリズム 始点sから各頂点への最短路木を作成 動作時間は 前提として，各辺の重みが正であった． 実際は重みが負の閉路が無ければ最短路木は構成可能． 重みが負の辺があっても動くアルゴリズムがあ ればより一般的なグラフに適用可能． ⇒ Bellman-Fordのアルゴリズムの提案 Bellman-Fordのアルゴリズム 基本的にはDijkstraのアルゴリズムと同じ． 1 2 3 4 5 6 7 8 0 ∞ ∞ ∞ ∞ ∞ Bellman-Fordのアルゴリズム 基本的にはDijkstraのアルゴリズムと同じ． 0 1 2 3 4 5 6 7 8 ∞ ∞ ∞ ∞ 緩和は辞書順に行う ∞ Bellman-Fordのアルゴリズム 基本的にはDijkstraのアルゴリズムと同じ． 1 2 3 4 5 6 7 8 ∞ 緩和は辞書順に行う この図は(s,t)から初めて(t,w)まで見た状況 Bellman-Fordのアルゴリズム 基本的にはDijkstraのアルゴリズムと同じ． 1 2 3 4 5 6 7 8 ∞ 次々と確認していき，緩和をしていく． Bellman-Fordのアルゴリズム 基本的にはDijkstraのアルゴリズムと同じ． 1 2 3 4 5 6 7 8 次々と確認していき，緩和をしていく． Bellman-Fordのアルゴリズム 基本的にはDijkstraのアルゴリズムと同じ． 1 2 3 4 5 6 7 8 次々と確認していき，緩和をしていく． Bellman-Fordのアルゴリズム 基本的にはDijkstraのアルゴリズムと同じ． 1 2 3 4 5 6 7 8 次々と確認していき，緩和をしていく． Bellman-Fordのアルゴリズム 基本的にはDijkstraのアルゴリズムと同じ． 1 2 3 4 5 6 7 8 緩和されきった各節点の重みが，その隣接した 重みから計算されるものから適切か判断． Bellman-Fordのアルゴリズムの正当性 補題25.12 は始点sと重み関数 を持つグラフ で，sから到達可能な閉路が存在しないとき， が終了した時にはsから到達可能なす べての頂点vに対して が成り立つ． 証明 Bellman-Fordのアルゴリズムの正当性 系25.13 は始点sと重み関数 を持つグラフ とする．このとき， を適用した に対 し，各頂点 に対して， 証明 ⇒ 補題25.13より，自明 ⇐ i番目の緩和で となったとすると， に辺を伸ばす頂点 は 番目までの緩和で となり，それを繰り返すと から への 経路が存在する事が言える． Bellman-Fordのアルゴリズムの正当性 定理25.14 は始点sと重み関数 を持つグラフ に を適用したとき， 1) が から到達可能な不の重みの閉路を含んで いないとき，trueを返し，すべての に対して が成り立ち，先行点グラフ は を根 とする最短路木となる． 2) が から到達可能な不の重みの閉路を含んで いるとき，falseを返す． Bellman-Fordのアルゴリズムの正当性 定理25.14 証明はDijkstra法の時と同じ．trueを返すか，false を返すかを確認する． 1) 到達可能な閉路が存在しない場合． ループでfalseを返すことは 無いのでtrueを返す． 1 2 3 4 5 6 7 8 Bellman-Fordのアルゴリズムの正当性 定理25.14 2) 到達可能な負の重みの閉路 る場合．trueを返すとするなら， ここで， が存在す より， より， となり，矛盾． よってfalseを返す． 1 2 3 4 5 6 7 8 閉路の無い有向グラフでの単一始点最短路 これまでの手法は全て 閉路が無い状況では 時間かかっていた． 時間で可能 ⇒トポロジカルソートの利用 有向グラフの流れが分かれば，到達不可能な節 点，緩和すべき順番が分かる 結果的に走査が一回で済む． 閉路の無い有向グラフでの単一始点最短路 トポロジカルソートの利用 1 2 3 4 5 閉路の無い有向グラフでの単一始点最短路 トポロジカルソートの利用 1 2 3 4 5 閉路の無い有向グラフでの単一始点最短路 トポロジカルソートの利用 1 2 3 4 5 閉路の無い有向グラフでの単一始点最短路 トポロジカルソートの利用 1 2 3 4 5 頂点tから順番に走査を行う． 閉路の無い有向グラフでの単一始点最短路 トポロジカルソートの利用 1 2 3 4 5 頂点tから順番に走査を行う． 一周の走査で，最短路木が求まる． Bellman-Fordのアルゴリズムの正当性 補題25.15 は始点sと重み関数 を持ち閉路を 含まないならば， が終了した時に すべての に対して が成り立ち， 先行点グラフ は最短路木である． 証明 最短路 があるとして，トポロジカ ルソートの順に処理されるため，頭から順に緩和 が行われている．帰納的に となり，こ の事実より は最短路木． 閉路の無い有向グラフでの単一始点最短路 トポロジカルソートの利用 ジョブスケジューリング 確実に閉路が無い 水洗い 切断 クリティカルパスは最長の経路 下茹で 少量の変更で適用可能． 炒め 1 2 3 4 5 煮込み 盛り付け 線形計画法への応用 線形計画法とは…？ 線形の制約式が存在 目的関数の値を最大化させるベクトルを考える． 線形計画法への応用 線形計画法は 最適解を求めるもの シンプレックス法等でほぼ多項式時間で解ける 実行可能解があるか無いかだけを判断するなら このような問題を実行可能判定問題という． このうち，各行が一つずつ1と-1を含むもの(連立差分 制約式)は制約グラフで表現が可能である． 連立差分制約式 補題25.16 を連立差分制約式 の一つ の解としたとき，任意の定数 に対して も の解である． 証明 より明らか． タスクスケジューリング等で利用可能． 連立差分制約式 制約グラフ 連立差分制約式 において， の を 個の頂点と 個の辺を持つグラフの接続行列と して見る事ができる． 連立差分制約式 制約グラフ 各頂点に到達可能な事を保証するために，と から各頂点への枝を追加する． 連立差分制約式 定理25.17 連立差分制約式 が与えられたとき， を対応する制約グラフとする． が負の重みの閉 路を含まなければ， はこの連立制約式に対する実行可能解であり， 負の重みの閉路を含むときは 実行可能解は存在しない． 連立差分制約式 定理25.17 が負の重みの閉路を含まないとき， 任意の辺 において よって， と置く事で， 制約式を全て満たす． 連立差分制約式 定理25.17 が負の重みの閉路 を含むとき， 閉路を構成する制約式を考えると， ・・・矛盾 つまり，制約式は満たされない． つまり，実行可能解は存在しない．
© Copyright 2025 ExpyDoc
![シュレディンガー作用素 H に対して, [T,H]=](http://s3.expydoc.com/store/data/007399069_1-ac85ef6aa09ec69b7f8f9c0887e1ad3c-250x500.png)
