講義資料 (5/25)

システム最適化特論
担当：平田健太郎
第7回（5/25）
１．グラフとネットワークにおける数理
・最短経路問題とダイクストラ法（2）
1
講義日程（予定）
4/13 １．グラフとネットワークにおける数理
・輸送問題とLP
4/20
・シンプレックス法（１）
4/27
・シンプレックス法（２）, 双対問題
5/7
・多項式時間アルゴリズム, 内点法（１）
5/11
・内点法（２）
5/18
・最短経路問題とダイクストラ法（１）
5/25
6/1
6/8
・最短経路問題とダイクストラ法（２）
・組合せ最適化（１）
・組合せ最適化（２）
2
ダイクストラ法のalgorithm
3
15
4
2
30
50
20
1
3
80
5
10
15
15
4
2
30
50
20
1
80
5
10
3
15
4
15
4
2
30
50
20
1
80
5
10
3
15
5
15
4
2
30
50
20
1
3
80
5
10
15
15
4
2
30
50
20
1
80
5
10
3
15
6
Dijkstra法の計算量
𝑆 の要素を1つずつ増やす： 𝑛 反復高々
n 個の 𝑑 𝑖 を比較
⇒ 𝑂 𝑛2
オーダー（最高次の次
数のみ係数は無視）
𝑆 から外に出るエッジについて 𝑑 𝑖
の更新高々𝑚 回の処理 ⇒ 𝑂 𝑚
(ループ内の処理に見えるが)
𝑛 𝑛−1
エッジの本数は最大でも 𝑚 =
2
(𝑛個のノードをすべて相互につなぐとき）
𝑚 < 𝑛2 より, 全体では 𝑂 𝑛2
ノード数： 𝑛, エッジ本数: 𝑚
7
初期化
ノード v を探す
(n 個の比較)
𝑂 𝑚 > 𝑂 𝑛 だから
全体では 𝑂 𝑚𝑛 ?
𝑂 𝑛
n 回のループ
𝑑 𝑗 の付け替え
終了判定
𝑂 𝑚
毎回処理するわけではないので,
𝑂 𝑚𝑛 の見積もりは正しくない.
都合何回あるかを考える.
8
4
2
5
1
3
4
2
5
1
3
4
2
∴ 𝑑 𝑗 の付け替えは各ノードに
入ってくる矢印の数だけ行われる.
（行われない場合もある.)
最大でも辺の総数だけ
5
1
3
4
2
5
1
3
9
10
ダイクストラ法のalgorithm （再掲）
11
 ダイクストラ法の正しさの証明
性質（事実）1
アルゴリズムの実行途中で 𝑑 𝑖 には常に「s から 𝑆 に含まれる節点の
みを経由して 𝑖 に至る最短路の長さ」が格納されている.
性質（事実）2
アルゴリズムの実行途中で 𝑖 ∈ 𝑆 ならば, 𝑑 𝑖 には常に「s から 𝑖 に至
る最短路の長さ」が格納されている.
これらが常に成り立つことを帰納法により示す．
∗ 「実行途中」は各反復終了時を指す.
12
初期状態
第1反復後
15
4
2
30
50
20
1
80
5
10
3
15
𝑑 𝑖 は「s から 𝑆 に含まれる節点のみを経由して 𝑖 に至る最短路の長さ」
𝑖 ∈ 𝑆 ならば, 𝑑 𝑖 は「s から 𝑖 に至る最短路の長さ」
第1反復後, 性質1, 2 は成り立つ
13
第 𝑘 反復後, 性質1, 2 が成り立つと仮定する.
第 𝑘 + 1 反復後, 性質1, 2 が成り立つか？
性質2
𝑖 ∈ 𝑆 ならば, 𝑑 𝑖 には「s から 𝑖 に至る最短路の長さ」が格納されている.
𝑑 𝑖 の更新は 𝑆 の要素に関してのみ行うので,第 𝑘 + 1 反復後, 性質2が
成り立つならば,
𝑆 の要素から 𝑑 𝑖 の値が最小であるものを選び, その要素 𝑣 を 𝑆 に
加える際に, 性質2が保存されなれけばならない.
性質2が成り立たない. ⇒ 𝑣 までの 𝑑 𝑣 よりも短い経路が存在する.
14
性質2が成り立たない. ⇒ 𝑣 までの 𝑑 𝑣 よりも短い経路が存在する.
第 𝑘 反復後, 性質1 は成り立っている. すなわち, 𝑑 𝑣 には「s から (𝑣を
加える前の) 𝑆 に含まれる節点のみを経由して 𝑖 に至る最短路の長さ」が
格納されている. したがって, 最短路が別にあるとすれば, (𝑣を加える前の)
𝑆 に含まれる節点以外を経由する.
𝑢
𝑣
𝑑 𝑣
𝑆
s
15
最短路が別にあるとすれば, (𝑣を加える前の) 𝑆 に含まれる節点以外を経由
する.
𝑢
𝑣
𝑑 𝑣
𝑆
s
最短路が最初に (𝑣を加える前の) 𝑆外に出る節点を𝑢 とする. 𝑢から𝑣への経路長
ℓは正. 𝑣 ≠ 𝑢 であり, 枝の長さは常に正
最短路長= 𝑑 𝑢 + ℓ < 𝑑 𝑣
𝑑 𝑢 <𝑑 𝑣
𝑆 の要素から 𝑑 𝑣 の値が最小である 𝑣 を選んだことに矛盾する.
「性質2が成り立たない」という仮定がおかしかった.
性質2は保存される.
16
第 𝑘 反復後, 性質1, 2 が成り立つと仮定する.
第 𝑘 + 1 反復後, 性質1, 2 が成り立つか？
性質1
𝑑 𝑖 には「s から 𝑆 に含まれる節点のみを経由して 𝑖 に至る最短路の長さ」
が格納されている.
第 𝑘 + 1 反復後, 性質1が成り立つならば, 𝑑 𝑖 の更新が性質1を保存する.
17
𝑆 に𝑣 を加えた後, 「 𝑆 に含まれる節点のみを経由する」経路は
i 𝑣 を経由する経路, (ii) 𝑣 を経由しない経路のどちらか.
(ii) が最短路を与えている場合, 変化なし
(i) は, (i-a) 途中で 𝑣 を経由する (𝑆 から出るのは 𝑣 以外の点)
(i−b) 最後に 𝑣 を経由する (𝑆 から出る直前の節点は 𝑣)
に分かれるが, (i−a) は最短路には, ならないので, (i−b)のみを
考えればよい.
18
補助結果1
𝑗 ∈ 𝑆 であれば, どの 𝑖 ∈ 𝑆 に対しても, 𝑑 𝑖 < 𝑑(𝑗)
第1反復後, 正しい
第𝑘反復後, 正しいと仮定
𝑆 から最小の 𝑑 𝑣 を探して𝑆 に加える. 以降 𝑆 内の 𝑑 ⋅ は更新しない.
𝑣 と接続している 𝑆 の節点 𝑗′ について 𝑑 𝑗′ = min 𝑑 𝑗′ , 𝑑 𝑣 + 𝑎𝑣𝑗
更新前, 𝑑 𝑗′ > 𝑑 𝑣 . 更新後, 𝑑 𝑗′ = 𝑑 𝑣 + 𝑎𝑣𝑗 > 𝑑 𝑣 .
𝑣 は 𝑆の要素であったから, もとの𝑆 の任意の要素𝑖 に対して 𝑑 𝑖 < 𝑑 𝑣 .
よって 𝑑 𝑖 < 𝑑 𝑗′ .
𝑣 と接続していない 𝑆 の節点 𝑗 ′′ については, 元から 𝑑 𝑖 < 𝑑 𝑗′′ .
よって第𝑘 + 1反復後も正しい.
19
𝑗 ∈ 𝑆 であれば, どの 𝑖 ∈ 𝑆 に対しても, 𝑑 𝑖 < 𝑑(𝑗)
補助結果2
𝑖
𝑗
𝑠
最短路上の節点については, 最適性の原理から 𝑠 に近い順に 𝑖, 𝑗とすると 𝑑 𝑖 < 𝑑(𝑗)
𝑆
𝑣
𝑗
𝑆
𝑆
𝑣
𝑖
この状況では 𝑑 𝑖 < 𝑑(𝑣)
k
𝑗
𝑆
𝑖
緑が最短路なら 𝑑 𝑖 > 𝑑(𝑣)
20
𝑆
𝑣
𝑗
𝑆
𝑆
𝑖
𝑣
k
𝑗
𝑆
𝑖
そもそも 𝑣 が加わったことで, 𝑖 への最短路が
変化するならば, 𝑖 への最短路は確定していなかった
ことになり, 𝑖 ∈ 𝑆 に矛盾.
21
𝑆 に新たに含まれるようになるのは 𝑣 だから, 「 𝑆 に含まれる節点のみを
経由したときの最短経路長」が変化するのは, 𝑣から1ステップで到達
できる点に限られる.
𝑣, 𝑗 ∈ 𝐸 かつ 𝑗 ∈ 𝑆 はこれにあたる.
𝑣 から1ステップで到達できる経路が, 新たに「 𝑆 に含まれる節点のみを経
由」する経路に加わる. これが 𝑣 を経由しない従来からの𝑆 に含まれる
節点のみを経由する最短経路より短ければ, 𝑑(𝑗) の値を更新すべき.
𝑑 𝑗 = min(𝑑 𝑗 , 𝑑 𝑣 + 𝑎𝑖𝑗 )
𝑣
𝑆
𝑆
𝑣
𝑗
𝑗
𝑆
𝑆
22

Download Report