最短経路問題とは プログラミング言語 I 第 0 回 から終点へ行く経路が複数通りある場合に 最も短い経路を見つける問題 経路の短さの決め方によって様々な応用 最短経路問題 埼玉大学工学部電気電子システム工学科伊藤和人 最短経路問題の応用例 カーナビゲーション 現在地から目的地まで最短時間のルート 経路 = 道路 交差点において走る道路を変更してもよい 経路の短さ = 所要時間の短さ 鉄道乗り換え案内 始発駅から目的駅まで料金最低のルート 経路 = 路線 駅において路線を乗り換えてもよい 経路の短さ = 料金の安さ 問題の定式化 定式化 : 問題の意味が変化しないことに注意して 明確な形式に問題を整理すること 条件と解の性質を明確にする あいまいな点をなくす さらに 問題を解くプログラムが容易に作成できるような定式化を行うことが重要 グラフ プログラミングに適した問題定式化の道具としてよく用いられる 個以上の点 ( ノード ) と つの点を結ぶ枝からなる 点 枝 グラフ ( その ) 点を共有する枝の集合をパス (path 経路 ) という パスのと終点を定める 一般にと終点が同じパスは複数通り存在する ( 通りしか存在しない場合や つも存在しない場合あり ) 終点 グラフの例 パス
グラフ ( その ) 枝に重みを与える パスの重みは の和とする 9 終点 パス : 重み 終点が同じ複数通りのパスパスによって重みは異なる 横浜 最短経路問題の定式化 グラフによって問題を入力 ( 終点 ) 鉄道乗り換え案内の場合 乗換駅を点 を料金とすればよい 0 円 80 円 品川 重み最小のパスを見つける 渋谷 東京 新宿 上野 池袋 赤羽 0 円 0 円 0 円 0 円 0 円 90 円 0 円 0 円 0 円,70 円 大宮 最小値原理 から終点 t への最短経路上の点を v とすると パス p(,v) とパス p(v,t) はともに最短経路である から v への最短経路 v v から t への最短経路 から t への最短経路 t 終点 終点以外の最短経路を順次求めて 最終的に終点への最短経路を求める 問題の分類 が 0 または正の場合 が 0 正 負で負ループがない場合 が 0 正 負で負ループがある場合 ループ : と終点が一致したパス負ループ : 和が負のループ -8 0 が 0 正 負で負ループがある場合 負ループ : 重み - 最短経路アルゴリズム が 0 または正の場合を考える 0 a 0 a から他の点への最短経路を求める から点 への最短経路が であると決定できるなぜか? 最短経路アルゴリズム ( その ) が 0 または正の場合 0 a が 0 または正であるので 点 a,, を経由するどのパスも重みが 以上となるため aを経由パス重みは 以上 を経由パス重みは 以上 を経由パス重みは 以上
最短経路アルゴリズム ( その ) 次に経路が最短な点を求める 0 a e f 0 a e f 0 a e f 0 a e f 最短経路アルゴリズム ( その ) アルゴリズムのポイント 最短経路長の決まっている点 最短経路長の定まった点から さらに枝 本で到達する点のうち 経路長最短の点は 最短経路と決定できる 7 7 ダイクストラ法 さらに枝 本で到達する点 経路長が最小 最短経路を決定できる点 C 言語によるグラフ表現 次元配列を用いる方法 枝が結ぶ 点 (,) 配列要素 e[][] が枝を表す と を区別しない場合 e[][] = e[][] とする e[][]=: 枝あり e[][]=0: 枝なし C 言語によるグラフ表現 ( 続き ) 枝 (,) の重み w[][] が記憶 と を区別しない場合 w[][] = w[][] とする w[][] =0 とする ダイクストラ法の実装 nt, mnlen,, m, u[n], f[n]={0; for( =0 ; <N ; ++ ) u[] = 9999; = 0; u[] = 0; for( m= ; m<n ; m++ ){ f[] = ; 点 は最短経路決定 for( =0 ; <N ; ++ ){ f( e[][]!= ) ontnue; f( u[]+w[][] < u[] ) u[]=u[]+w[][]; mnlen = 9999; for( =0 ; <N ; ++ ){ f( f[] == ) ontnue; f( u[] < mnlen ){ mnlen = u[]; = ; 点 は経路長が最短 点数 N 十分大きな正数 枝 (,) が存在しない 点 への経路長を更新 最短経路既定の点は除外 =0 とする 長さだけでなく経路を記録 nt, mnlen,, m, u[n], f[n]={0, prev[n]; 点数 N for( =0 ; <N ; ++ ) u[] = 9999; = 0; u[] = 0; 十分大きな正数 for( m= ; m<n ; m++ ){ f[] = ; 点 は最短経路決定 for( =0 ; <N ; ++ ){ f( e[][]!= ) ontnue; 枝 (,) が存在しない f( u[]+w[][] < u[] ){ u[]=u[]+w[][]; prev[]=; /* の直前は */ mnlen = 9999; 点 への経路長を更新 for( =0 ; <N ; ++ ){ 最短経路既定の点は除外 f( f[] == ) ontnue; f( u[] < mnlen ){ mnlen = u[]; = ; 点 は経路長が最短
ダイクストラ法の計算複雑度 経路長最短の点を つ選び経路を決定 その点から 本の枝で接続する点について経路長を調べなおす すべての点について経路が決定するまで繰り返す O( N ) 秒 プログラムの実行時間 ノード数 Nとプログラム実行時間の関係 00.00 0.00.00 0.0 0.0 00 000 0000 00000 N N=8000 約 00M バイト N=7000 約 00M バイト 予想 つのノード当たり 本の枝の場合 PentumIV.GHz MB メモリ プログラムの問題点 配列による枝表現はメモリを大量に必要とし かつ効率が悪い 00000000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000 000000000000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000 000000000000000000000000000000000000000000000000000 000000000000000000000000000000000000000000000000000 000000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000 000000000000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000 000000000000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000 000000000000000000000000000000000000000000000000000 000000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000 000000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000 000000000000000000000000000000000000000000000000000 000000000000000000000000000000000000000000000000000 000000000000000000000000000000000000000000000000000 000000000000000000000000000000000000000000000000000 枝の有無を表す 次元配列 e[][] の例 0 がほとんど 配列による枝表現の問題 枝の有無 (e[][]== か否か ) を調べる処理が必要 枝が無くても (e[][]=0) を記憶する必要があるためメモリを大量に消費し 速度低下 ( スラッシング ) 配列に代わる 不規則なデータを効率よく記録する方式が必要 リスト構造 リストの管理 リストの要素データ領域の他に 次の要素を指すポインタを備えるポインタ次の要素を指す 要素 データ領域 ポインタを用いて要素をつなげる = リスト リストの実装 構造体によって データ領域と次要素へのポインタをまとめて管理する要素の構造体型を宣言例 typeef trut Ege { trut Ege *next; 次要素へのポインタ nt,; // 点, 点 nt w; // データ領域 EDGE; 例 リストの先頭を指すポインタを宣言 EDGE *ege_top = NULL;
リストの実装 ( その ) リストの例 ege_top リストを順にたどる処理 NULL 点 点 点 点 点 点 本の枝を記録するリスト リストの末尾では next メンバは NULL EDGE *ep; for( ep=ege_top ; ep!= NULL ; ep=ep->next ){ /* リスト要素に対する処理 */ ダイクストラ法における枝リスト 最短経路が決まるたびに その点から枝 本でつながる点の経路長更新 最短経路長の決まっている点 新たに最短経路長 の決まった点 7 各点に接続する枝リストがあると便利 7 経路長を更新する点 ege[0] ege[] ege[] ダイクストラ法のための枝リスト 各点に接続する枝のリスト 点 0 に接続する枝のリスト 点 に接続する枝のリスト NULL 0 0 0 点 点 点 点ごとに接続する枝数は変化 NULL 点 点 点 点 点 ダイクストラ法と組合わせる場合 メンバ 点 は不要 =0 とする リストを用いたダイクストラ法 nt, mnlen,, m, u[n], f[n]={0; 点数 N EDGE ege[n], *ep; /* 枝リストを設定する処理は省略 */ for( =0 ; <N ; ++ ) u[] = 9999; = 0; u[] = 0; 十分大きな正数 for( m= ; m<n ; m++ ){ f[] = ; 点 は最短経路決定 for( ep=ege[] ; ep!=null ; ep=ep->next ){ f( u[]+ep->w < u[ep->] ){ u[ep->]=u[]+ ep->w; mnlen = 9999; for( =0 ; <N ; ++ ){ f( f[] ) ontnue; f( u[] < mnlen ){ mnlen = u[]; = ; に接続する枝を順に調べる点 ep-> への経路長を更新 点 は経路長が最短 最短経路既定の点は除外 秒 プログラムの実行時間 ノード数 Nとプログラム実行時間の関係 00.00 0.00.00 0.0 0.0 00 000 0000 00000 N N=8000 約 00M バイト N=7000 約 00M バイト 配列利用 リスト構造利用 N=0000 約 M バイト PentumIV.GHz MB メモリ 最短経路アルゴリズム 負のが存在する場合 0 a - - 0 - ダイクストラ法では最短経路を見つけられないなぜか? まだ最短経路の決まっていない点を経由した方が経路長が短くなるパスが存在するかもしれないため
Bellman 方程式 点 の最短経路長を u とするとき u が満たす関係式 Bellman 方程式 u u = 0 = mn { u + w u w u 最小値原理より Bellman 方程式を解く Bellman 方程式の解 = 最短経路 漸化的に解く u[] が更新されたら 枝 (,) が存在する点 について u[] を更新する すべての点 についてu[] が変化しなくなったら 解が得られている Bellman-For 法 =0 とする リストを用いた Bellman-For 法実装 nt,upate,mnl,,u[n], prev[n]; EDGE *ege_top, *ep; /* リストを正しく作成する必要あり ( ここでは省略 ) */ for( =0 ; <N ; ++ ) u[] = 9999; 十分大きな正数 = 0; u[] = 0; o { upate = 0; for( ep=ege_top ; ep!= NULL ; ep=ep->next ){ f( u[ep->]+ep->w < u[ep->] ){ u[ep->] = u[ep->]+ ep->w; prev[ep->] = ep->; 経路を記録 upate = ; whle ( upate ); 経路長が短くなったら更新フラグを に 経路長更新の場合再度繰り返し o - whle 文 条件が成り立つ間 文を実行 o 文 whle( 式 ); 意味 : まず 回文を実行する 式が真の間 文を実行 文 式 True Fale o-whle 文の実行の様子 式 True 文 Fale whle( 式 ) 文 ; の実行の様子 Bellman-For 法の計算複雑度 すべての枝を順に調査 経路長が更新されたら 再度調査実行 負ループがなければ最短経路を構成する枝数は N 未満 更新は高々 N- 回 実行時間 O(NE) 負ループのある最短経路問題 最短経路は不定 負ループを繰り返すごとに経路長は減少 経路にループを含まない という制約を与えると意味のある問題として定式化される効率よく最短経路を求めるアルゴリズムは見つかっていない 負ループが存在する場合の最短経路問題は負ループが存在しない場合の問題とは性格が異なる
組み合わせ最適化問題 ある条件を満足する解候補のうち ある評価尺度が最適になる解を選ぶ問題 例 : 最短経路問題 条件 : から終点への連続した枝集合 ( 経路 ) 評価尺度 : 和が小さい 組み合わせ最適化問題の困難さ 組み合わせ最適化問題を つに分類 P: 多項式可解な問題 問題サイズの多項式オーダの手数で解が得られる 計算複雑度が多項式オーダの解法が存在 NP: 非決定的多項式可解な問題 都合良く選択肢を選ぶと 問題サイズの多項式オーダの手数で解が得られる P でも NP でもない問題 P や NP よりも難しい問題 問題の困難さ 組み合わせ最適化問題の分類とその関係 P 問題の例 P ソート ( 並べ替え ) 最短経路問題 NP オペレーションズ リサーチ 全組み合わせ問題 NP 問題 NP: 非決定的多項式可解な問題 都合良く選択肢を選ぶと 問題サイズの多項式オーダの手数で解が得られる 工学的に有用な問題が多数含まれる 負ループを含む最短経路問題 セールスマンの巡回問題 タスク スケジューリング問題など セールスマンの巡回問題 問題の定義 N 個の都市を順に訪問するための旅費が最小になる訪問順を求めよ 都市間の旅費は非負 最短経路 ( 最小費用 ) を求める問題 一見すると最短経路問題として解けそう? すべての訪問順を列挙して最小費用の順路を求める方法しか知られていない O(N! ) NP 問題と P 問題 NP 問題の解には 今のところ非多項式オーダの手数が必要 多項式オーダの解法が存在しないことは証明されていない もしかすると NP=P かもしれない NP 問題のどれか つについて多項式オーダの解法が見つかれば NP=P すべての NP 問題が多項式オーダで解ける!
まとめ 問題定式化とグラフ 最短経路問題 効率よい解法 ダイクストラ法 Bellman-For 法 リスト構造 組み合わせ最適化問題と NP