Microsoft PowerPoint - H20第10回最短経路問題-掲示用.ppt

Transcription

1 プログラミング言語 I 第 10 回 最短経路問題 埼玉大学工学部電気電子システム工学科伊藤和人

2 最短経路問題とは 始点から終点へ行く経路が複数通りある場合に 最も短い経路を見つける問題 経路の短さの決め方によって様々な応用

3 最短経路問題の応用例 カーナビゲーション 現在地から目的地まで最短時間のルート 経路 = 道路 交差点において走る道路を変更してもよい 経路の短さ = 所要時間の短さ 鉄道乗り換え案内 始発駅から目的駅まで料金最低のルート 経路 = 路線 駅において路線を乗り換えてもよい 経路の短さ = 料金の安さ

4 問題の定式化 定式化 : 問題の意味が変化しないことに注意して 明確な形式に問題を整理すること 条件と解の性質を明確にする あいまいな点をなくす さらに 問題を解くプログラムが容易に作成できるような定式化を行うことが重要

5 グラフ プログラミングに適した問題定式化の道具としてよく用いられる 1 個以上の点 ( ノード ) と つの点を結ぶ枝からなる 点 枝 グラフの例

6 グラフ ( その ) 点を共有する枝の集合をパス (path 経路) という パスの始点と終点を定める 一般に始点と終点が同じパスは複数通り存在する (1 通りしか存在しない場合や 1つも存在しない場合あり ) 始点 終点 パス

7 グラフ ( その 3) 枝に重みを与える パスの重みは 枝重みの和とする 枝重み 5 始点 終点 パス : 重み 1 始点 終点が同じ複数通りのパスパスによって重みは異なる

8 最短経路問題の定式化 グラフによって問題を入力 ( 始点 終点 枝重み ) 重み最小のパスを見つける 鉄道乗り換え案内の場合 乗換駅を点 枝重みを料金とすればよい 横浜 60 円 80 円 渋谷新宿 160 円 160 円 品川東京上野 池袋 150 円 150 円 150 円 赤羽 160 円 90 円 150 円 160 円,750 円 大宮

9 最小値原理 始点 s から終点 t への最短経路上の点を v とすると パス p(s,v) とパス p(v,t) はともに最短経路である 始点 s s から v への最短経路 v v から t への最短経路 t 終点 s から t への最短経路 終点以外の最短経路を順次求めて 最終的に終点への最短経路を求める

10 問題の分類 枝重みが0または正の場合 枝重みが0 正 負で負ループがない場合 枝重みが0 正 負で負ループがある場合 ループ : 始点と終点が一致したパス負ループ : 枝重み和が負のループ 枝重みが 0 正 負で負ループがある場合 負ループ : 重み -

11 最短経路アルゴリズム 1 始点 始点 枝重みが 0 または正の場合を考える s s 6 6 d d a a b c b c 始点 s から他の点への最短経路を求める 始点 s から点 b への最短経路が 1 であると決定できるなぜか?

12 最短経路アルゴリズム 1( その ) 枝重みが 0 または正の場合 始点 s 6 6 d a b c 枝重みが 0 または正であるので 点 a, c, d を経由するどのパスも重みが 1 以上となるため aを経由パス重みは 以上 cを経由パス重みは3 以上 dを経由パス重みは6 以上

13 1 最短経路アルゴリズム 1( その 3) 次に経路が最短な点を求める始点 1 s 3 6 a d b c f e s 3 6 a d b c f e s 3 6 a d b c f e s 3 6 a d b c f e

14 最短経路アルゴリズム 1( その 4) アルゴリズムのポイント ダイクストラ法 最短経路長の定まった点から さらに枝 1 本で到達する点のうち 経路長最短の点は 最短経路と決定できる 最短経路長の決まっている点 s さらに枝 1 本で到達する点 経路長が最小 最短経路を決定できる点

15 C 言語によるグラフ表現 1 次元配列を用いる方法 枝が結ぶ 点 (i,j) i j 配列要素 e[i][j] が枝を表す e[i][j]=1: 枝あり e[i][j]=0: 枝なし i j と j i を区別しない場合 e[j][i] = e[i][j] とする

16 C 言語によるグラフ表現 1( 続き ) 枝 (i,j) の重み w[i][j] が記憶 i w[i][j] i j と j i を区別しない場合 w[j][i] = w[i][j] とする j

17 ダイクストラ法の実装 始点 s=0 とする int s, minlen, j, m, u[n], f[n]={0}; for( j=0 ; j<n ; j++ ) u[j] = 9999; s = 0; u[s] = 0; for( m=1 ; m<n ; m++ ){ f[s] = 1; for( j=0 ; j<n ; j++ ){ if( e[s][j]!= 1 ) continue; if( u[s]+w[s][j] < u[j] ) u[j]=u[s]+w[s][j]; } 十分大きな正数 枝 (s,j) が存在しない } minlen = 9999; for( j=0 ; j<n ; j++ ){ if( f[j] == 1 ) continue; if( u[j] < minlen ){ minlen = u[j]; s = j; } } 点 s は経路長が最短 点数 N 点 s は最短経路決定 点 j への経路長を更新 最短経路既定の点は除外

18 長さだけでなく経路を記録 始点 s=0 とする int s, minlen, j, m, u[n], f[n]={0}, prev[n]; for( j=0 ; j<n ; j++ ) u[j] = 9999; s = 0; u[s] = 0; 十分大きな正数 for( m=1 ; m<n ; m++ ){ f[s] = 1; 点 sは最短経路決定 for( j=0 ; j<n ; j++ ){ if( e[s][j]!= 1 ) continue; if( u[s]+w[s][j] < u[j] ){ u[j]=u[s]+w[s][j]; prev[j]=s; } /* jの直前はs */ } minlen = 9999; 点 jへの経路長を更新 for( j=0 ; j<n ; j++ ){ if( f[j] == 1 ) continue; if( u[j] < minlen ){ minlen = u[j]; s = j; } } } 点 sは経路長が最短 点数 N 枝 (s,j) が存在しない 最短経路既定の点は除外

19 ダイクストラ法の計算複雑度 経路長最短の点を 1 つ選び経路を決定 その点から1 本の枝で接続する点について経路長を調べなおす すべての点について経路が決定するまで繰り返す O( N )

20 プログラムの実行時間 秒 ノード数 N とプログラム実行時間の関係 N=8000 約 500M バイト N=7000 約 400M バイト 予想 N 1 つのノード当たり 4 本の枝の場合 PentiumIV.4GHz 51MB メモリ

21 プログラムの問題点 配列による枝表現はメモリを大量に必要とし かつ効率が悪い i j 枝の有無を表す 次元配列 e[i][j] の例 0 がほとんど

22 配列による枝表現の問題 枝の有無 (e[i][j]==1 か否か ) を調べる処理が必要 枝が無くても (e[i][j]=0) を記憶する必要があるためメモリを大量に消費し 速度低下 ( スラッシング ) 配列に代わる 不規則なデータを効率よく記録する方式が必要 リスト構造

23 リストの管理 リストの要素データ領域の他に 次の要素を指すポインタを備える 要素 ポインタ データ領域 次の要素を指す ポインタを用いて要素をつなげる = リスト

24 リストの実装 例 構造体によって データ領域と次要素へのポインタをまとめて管理する 要素の構造体型を宣言 typedef struct Edge { struct Edge *next; int i,j; // 点 1, 点 int w; // 枝重み } EDGE; 次要素へのポインタ データ領域 例 リストの先頭を指すポインタを宣言 EDGE *edge_top = NULL;

25 リストの実装 ( その ) リストの例 edge_top NULL 点 1 点 1 点 1 点 枝重み 点 枝重み 点 枝重み リストを順にたどる処理 3 本の枝を記録するリスト リストの末尾では next メンバは NULL EDGE *ep; for( ep=edge_top ; ep!= NULL ; ep=ep->next ){ /* リスト要素に対する処理 */ }

26 ダイクストラ法における枝リスト 最短経路が決まるたびに その点から枝 1 本でつながる点の経路長更新 最短経路長の決まっている点 新たに最短経路長の決まった点 各点に接続する枝リストがあると便利 s 経路長を更新する点

27 edge[0] ダイクストラ法のための枝リスト 各点に接続する枝のリスト 点 0 に接続する枝のリスト edge[1] 点 1 に接続する枝のリスト NULL 点 枝重み 点 枝重み 点 枝重み 点ごとに接続する枝数は変化 NULL 点 枝重み 点 枝重み 点 枝重み 点 枝重み edge[] 点 枝重み ダイクストラ法と組合わせる場合 メンバ 点 1 は不要

28 リストを用いたダイクストラ法 始点 s=0 とする int s, minlen, j, m, u[n], f[n]={0}; EDGE edge[n], *ep; /* 枝リストを設定する処理は省略 */ for( j=0 ; j<n ; j++ ) u[j] = 9999; s = 0; u[s] = 0; 十分大きな正数 for( m=1 ; m<n ; m++ ){ f[s] = 1; 点 sは最短経路決定 } for( ep=edge[s] ; ep!=null ; ep=ep->next ){ if( u[s]+ep->w < u[ep->j] ){ u[ep->j]=u[s]+ ep->w;} } minlen = 9999; for( j=0 ; j<n ; j++ ){ if( f[j] ) continue; if( u[j] < minlen ){ minlen = u[j]; s = j; } } 点 s は経路長が最短 点数 N s に接続する枝を順に調べる 点 ep->j への経路長を更新 最短経路既定の点は除外

29 秒 プログラムの実行時間 ノード数 N とプログラム実行時間の関係 N=8000 約 500M バイト N=7000 約 400M バイト 配列利用 リスト構造利用 N N=40000 約 1M バイト PentiumIV.4GHz 51MB メモリ

30 最短経路アルゴリズム 負の枝重みが存在する場合 始点 s 6 d a b c ダイクストラ法では最短経路を見つけられないなぜか? まだ最短経路の決まっていない点を経由した方が経路長が短くなるパスが存在するかもしれないため

31 Bellman 方程式 点 j の最短経路長を u j とするとき u j が満たす関係式 Bellman 方程式 u s = 0 u j = min i { } u + w j s i ij 最小値原理より 始点 s u i i w ij j u j

32 Bellman 方程式を解く Bellman 方程式の解 = 最短経路 漸化的に解く u[i] が更新されたら 枝 (i,j) が存在する点 j について u[j] を更新する すべての点 j について u[j] が変化しなくなったら 解が得られている Bellman-Ford 法

33 リストを用いた Bellman-Ford 法実装 始点 s=0 とする int s,update,minl,i,u[n], prev[n]; EDGE *edge_top, *ep; /* リストを正しく作成する必要あり ( ここでは省略 ) */ for( i=0 ; i<n ; i++ ) u[i] = 9999; s = 0; u[s] = 0; do { update = 0; for( ep=edge_top ; ep!= NULL ; ep=ep->next ){ if( u[ep->i]+ep->w < u[ep->j] ){ u[ep->j] = u[ep->i]+ ep->w; prev[ep->j] = ep->i; update = 1; } } } while ( update ); 十分大きな正数 経路を記録 経路長が短くなったら更新フラグを 1 に 経路長更新の場合再度繰り返し

34 do - while 文 条件が成り立つ間 文を実行 do 文 while( 式 ); 意味 : まず 1 回文を実行する 式が真の間 文を実行 文 式 False True 式 False True 文 do-while 文の実行の様子 while( 式 ) 文 ; の実行の様子

35 Bellman-Ford 法の計算複雑度 すべての枝を順に調査 経路長が更新されたら 再度調査実行 負ループがなければ最短経路を構成する枝数は N 未満 更新は高々 N-1 回 実行時間 O(NE)

36 負ループのある最短経路問題 最短経路は不定 負ループを繰り返すごとに経路長は減少 経路にループを含まない という制約を与えると意味のある問題として定式化される効率よく最短経路を求めるアルゴリズムは見つかっていない 負ループが存在する場合の最短経路問題は負ループが存在しない場合の問題とは性格が異なる

37 組み合わせ最適化問題 ある条件を満足する解候補のうち ある評価尺度が最適になる解を選ぶ問題 例 : 最短経路問題 条件 : 始点から終点への連続した枝集合 ( 経路 ) 評価尺度 : 枝重み和が小さい

38 組み合わせ最適化問題の困難さ 組み合わせ最適化問題を 3 つに分類 P: 多項式可解な問題 問題サイズの多項式オーダの手数で解が得られる 計算複雑度が多項式オーダの解法が存在 NP: 非決定的多項式可解な問題 都合良く選択肢を選ぶと 問題サイズの多項式オーダの手数で解が得られる P でも NP でもない問題 P や NP よりも難しい問題

39 問題の困難さ 組み合わせ最適化問題の分類とその関係 P 問題の例 P ソート ( 並べ替え ) 最短経路問題 NP オペレーションズ リサーチ 全組み合わせ問題

40 NP 問題 NP: 非決定的多項式可解な問題 都合良く選択肢を選ぶと 問題サイズの多項式オーダの手数で解が得られる 工学的に有用な問題が多数含まれる 負ループを含む最短経路問題 セールスマンの巡回問題 タスク スケジューリング問題など

41 セールスマンの巡回問題 問題の定義 N 個の都市を順に訪問するための旅費が最小になる訪問順を求めよ 都市間の旅費は非負 最短経路 ( 最小費用 ) を求める問題 一見すると最短経路問題として解けそう? すべての訪問順を列挙して最小費用の順路を求める方法しか知られていない O(N! )

42 NP 問題と P 問題 NP 問題の解には 今のところ非多項式オーダの手数が必要 多項式オーダの解法が存在しないことは証明されていない もしかするとNP=Pかもしれない NP 問題のどれか 1 つについて多項式オーダの解法が見つかれば NP=P すべての NP 問題が多項式オーダで解ける!

43 まとめ 問題定式化とグラフ 最短経路問題 効率よい解法 ダイクストラ法 Bellman-Ford 法 リスト構造 組み合わせ最適化問題とNP