First Course in Combinatorial Optimization

Presentation on theme: "First Course in Combinatorial Optimization"— Presentation transcript:

1 First Course in Combinatorial Optimization
Oct. 29, 2007

2 2. Minimum-Weight Dipaths
2.1 No Negative-Weight Cycles Bellman-Ford Algorithm 2.2 All-Pairs Minimum-Weight Dipaths Floyd-Warshall Algorithm 2.3 Nonnegative Weights Dijkstra’s Algorithm 2.4 No Dicycles and Knapsack Programs

3 2. Minimum-Weight Dipaths
最短路問題 : 入力 : 有向グラフG, 枝のコスト関数c, 始点s, 終点t 出力 : 最短の(重み最小の)s-tパス パス：同じ節点を2度通らない枝の系列 -1 2 5 パスの重み 3 7 11 4 16 14 9 1

4 2.1 No Negative-Weight Cycles
最短路問題を高速に解く. 問題の入力に制限を加える. 　負の重みの閉路が存在しない 最短パス = 最短ウォーク 負閉路が存在 最短ウォーク問題は解を持たない 最短ウォーク問題を解けばよい 1 1 パス : 節点・辺の重複を許さない ウォーク : 節点・辺の重複を許す -5 -5

5 Minimum diwalks 最短ウォーク問題は高速に解ける(動的計画法). 本章では以下のような制限を設けた最短路問題を解く.
負の重みの閉路を持たない 負の重みの枝を持たない 閉路を持たない

6 Bellman-Ford Algorithm
入力 : 負閉路を持たない有向グラフG, 始点v. 出力 : vから他の全ての接点への最短路の重み. fk-1からfkを繰り返し求める. 最短路は最大でも|V|-2個の内点しか持たないので, が最短路の重みとなる. : 内点がk個以下である最短v-wパスの重み

7 Bellman-Ford Algorithm
: 内点がk個以下である最短v-wパスの重み

8 Example b d 3 2 6 1 a 5 6 7 4 e 8 2 c f

9 Example 2 b d 3 2 6 1 a 5 6 7 4 e 8 2 k=0 8 c f

10 Example 2 5 b d 3 2 6 1 a 5 6 7 4 e 8 2 k=1 7 8 c f 8

11 Example 2 5 b d 3 2 6 11 1 a 5 6 7 4 e 8 2 k=2 6 7 c f 7 8

12 Example 2 5 b d 3 2 6 11 1 a 5 6 7 4 e 8 2 k=3 6 c f 6 7

13 Example 2 5 b d 3 2 6 11 1 a 5 6 7 4 e 8 2 k=4 6 c f 6

14 Computation time |V|回の繰り返しそれぞれで．各枝についてfkが更新される．

15 Finding Negative-Weight Cycle
グラフが負閉路を含まない場合 : 最短路が含む内点は|V|-2個以下であるから， グラフが負閉路を含む場合は? グラフが始点sから到達可能な負閉路を含むならば， となる節点wが必ず存在する． 負閉路の検出に利用

16 proof. なるwが存在する．

17 2.2 All-Pairs Minimum-Weight Dipaths
出力 : 任意の2接点間の最短路の重み. fk-1からfkを繰り返し求める. （1つずつ節点を解放していく) 全ての節点を解放すれば最短路が求められるので、 　が最短路の重みとなる. 節点に1,2,･･･|V|の番号を付ける. 内点に1, …, kまでの節点だけを含む最短v-wパスの重み

18 Floyd-Warshall Algorithm
任意の全単射な写像 を選ぶ.

19 Computation time |V|回の繰り返し． 1回の繰り返しでO(|V|2)回の計算．

20 2.3 Nonnegative weights 入力 : 枝の重みが非負の有向グラフG, 始点v.
接点をP, Tの2つのクラスに分ける． Pは最短路がFixした節点．(Tはそれ以外) Tの接点を1つずつPに変えていく 節点が全てP : 　　　は最短v-wパスの重み : 内点が全てPである最短v-wパスの重み

21 Dijkstra’s Algorithm なるw*を選ぶ. なる全ての について,

22 Example b d 3 2 6 1 a 5 6 7 4 e 8 2 c f

23 Example 2 b d 3 2 6 1 a 5 6 7 4 e 8 2 8 c f

24 Example 2 5 b d 3 2 6 1 a 5 6 7 4 e 8 2 7 8 c f

25 Example 2 5 b d 3 2 6 11 1 a 5 6 7 4 e 8 2 6 7 c f 12

26 Example 2 5 b d 3 2 6 11 1 a 5 6 7 4 e 8 2 6 c f 6 12

27 Example 2 5 b d 3 2 6 11 1 a 5 6 7 4 e 8 2 6 c f 6

28 Example 2 5 b d 3 2 6 11 1 a 5 6 7 4 e 8 2 6 c f 6

29 Computation Time |V|回の繰り返し． 最小重みの節点を見つけるのにO(|V|)． f(v)の更新は合計で|E|回．

30 Correctness proof 前述のアルゴリズムで確かにv-wパスの最小重みが求められる事を示す. 2つの性質
が、各時点において成り立つ事を帰納法で示す.

31 Dijkstra’s Algorithm(再掲)
初期段階では なるw*を選ぶ. なる全ての について, は自明．

32 Induction ある時点で(a),(b)が成り立っていると仮定する． 現在のラベル : P,T, 次にTに変わる節点 : w*
次のラベル : P'=P+w*, T'=T-w* 次の(a')(b')が成り立つことを示す．

33 Induction P T v F1 k w*

34 Induction P' T' v j w w* w

35 2.4 No Dicycles and Knapsack Programs
閉路を持たない有向グラフ (DAG) 次のような全単射写像πを考える 1 2 3 4 5 右向きの枝しかない

36 No dicycles あるパスに含まれる接点をv1, ..., vmとすると、 : v-wパスの最小重み
　 : v-wパスの最小重み 節点wに対し， である全てのuについて f(u)がFixしていればf(w)も計算できる． という順に決定していけば良い．

37 Algorithm なるwについて, 各枝について1回f(w)の更新を行うので，

38 Example 5 2 2 3 3 2 1 ∞ 1 5 7 5 8 2 4 6 6 6

39 Kanpsack Problem

40 Example -11 空き : 25 空き : 6 空き : 0 -5 ・・・ -1 -1 -7

41 Example -11 空き : 25 空き : 0 -5 ・・・ -1 -1 -7

42 Conclusion 入力の制限 アルゴリズム 計算時間 負閉路なし Bellman-Ford 1始点 Floyd-Warshall 全点対
負の枝なし Dijkstra 閉路なし(DAG)