Microsoft PowerPoint - AG03-10black.ppt

Size: px

Start display at page:

Download "Microsoft PowerPoint - AG03-10black.ppt"

しまなかに
4 years ago
Views:

1 アルゴリズム論 ( 第回 )..5 櫻井彰人 lgorthm@soft.ae.keo.ac.jp きょうの講義概要グラフ () ( 復習 ) グラフのアルゴリズムフロイトの方法グラフ理論からの補足動的計画法 LS : 最長共通系列 - ナップザック問題 ( 次回 ) 5.5 クラスカルのアルゴリズムすべての地点を結ぶ無向グラフでコストが最小になるもの ( コスト最小の全域木 ) を求める ( 道路網電話網など ) 5.6 ダイクストラ法各辺に距離のついた有向グラフ上で任意の点間の最短経路を見つける 5.6 フロイトのアルゴリズム特定の出発の節を決めずすべての節間の最短距離を求めるすべての節に対してダイクストラ法を適用しても求まる» 計算量が O(n ) に a k (j) を a, a,..., a n と求める a k (j) = k 番以下の節だけを経由してから j へ至る最短経路の距離 (k 番目の節 : ピボット ) 例題ハワイのオアフ島の町をめぐる

2 例題の行列表現例題の実行 () はじめの行列の (j) 要素から j へ直接つながる辺のラベル ( 距離 ) の節だけを経由してよいときの行列の節を経由点に例題の実行 (-) 例題の実行 (-) との節を経由してよいときの行列の節を新しい経由点にとの節を経由してよいときの行列の節を新しい経由点に例題の実行 () 例題の実行 () の節を経由してよいときの行列の節を経由点にの節を経由してよいときの行列の節を新たな経由点に

3 例題の実行 (5) アルゴリズム 5. フロイトのアルゴリズム最終的な行列入力 : グラフの n 個の節間の距離を表わす n n 行列出力 : 各節間の最短距離を表わす行列内容 ()v = から n まで以下を繰り返す (.) w = から n まで以下を繰り返す» (..) dst(v,w) arc(v,w) フロイトのアルゴリズム () () u = から n まで以下を繰り返す (.) v = から n まで以下を繰り返す» (..) w = から n まで以下を繰り返す (...) dst(v,u) + dst(u,w) < dst(v,w) ならば dst(v,w) dst(v,u) + dst(u,w) dst(v,w): 節 v から節 w までの距離 arc(v,w): 節 v から節 w への直接つながった辺の距離 ( 入力行列の (v,w) 要素 ) フロイトのアルゴリズムの正当性アルゴリズム 5. においてピボットを通るすべての経路で dst(v,w) は節 v と節 w の最短距離 ( 証明は数学的帰納法 ) k 以下の節だけを中間の節とする v から w への経路 :k-path 命題 S(k): アルゴリズム 5. の () のループに関して u が k のループ終了のときに dst(v,w) は v から w への最短の k-path であるかまたは経路が存在せずに 5.7 グラフ理論からの補足 () 無向グラフが完全 (complete) グラフすべての節の間に辺がある n 個の節の完全グラフ : K n» 辺の数は n (= n(n-)/) 個グラフ理論からの補足 () 有向グラフが完全 (complete) グラフ自分自身を含めてすべての節を互いに結ぶ辺がある n 個の節の完全グラフ» n 個のアーク D K

4 グラフ理論からの補足 () 平面グラフ ( Planar Graph) どの辺も交差しないで平面上に書くことのできるグラフ» 辺と節の関係を変えないで平面グラフで表現できるものもある D D グラフ理論からの補足 () 非平面グラフの例 : K 5 と K, D E K 5 K, D E F グラフ理論からの補足 (5) クラトフスキー (Kuratowsk) の定理すべての非平面グラフは前に示したK 5 と K, のうちの少なくとも一つのコピーを含むグラフの平面性の応用平面グラフと同等なグラフは辺の交差をなくして表示したほうが分かりやすい集積回路の設計では平面にできるものは平面にしたほうが集積度を増すことができる動的計画法 (Dynamc Programmng) ellman 95; 有名な著書 Dynamc Programmng は 957. そこに Dynamc ndcates that we are nterested n processes» n whch tme plays a sgnfcant role, and» n whch the order of operatons may be crucal programmng は恐らく plannng/schedulng» In the frst place I was nterested n plannng, n decson makng, n thnkng. ut plannng, s not a good word for varous reasons. I decded therefore to use the word, programmng. (ellman 98 Eye of the hurrcane )» "Program" at that tme was a mltary term that referred not to the nstructon used by a computer to solve problems, whch were then called "codes," but rather to plans or proposed schedules for tranng, logstcal supply, or deployment of combat unts. (Professor George Dantzg: Lnear Programmng Founder Turns 8, SIM News, November 99, ) 例 : 最長共通部分系列問題最長共通部分系列問題 Longest common subsequence (LS) problem: 二つの系列 x[..m] と y[..n] が与えられた時, 双方に現れる部分系列の中で最長のものを見つけよ例 : x = { D }, y = { D } { } や { } は双方の部分列» ではそのような部分系列で最長のもの (LS) は? X = D Y = D 力ずくでは? 力ずく法 : x の部分系列を一つずつ作り, それが y の部分系列になっているかを調べる x の部分系列はいくつあるか? 力ずく法の計算量は? x の部分系列は m 個ある. その一つ一つを y の n 個の要素と照合する : O(n m ) x = { D } y = { D } D D D D

5 もっと賢くできないか? 実は良い方法がある : とりあえず, LS の長さだけを見つける問題を考える見つけ終わったときに, この解から LS の解を掘り出す方法を考える LS 問題には部分構造の最適性 (optmal substructure) がある部分構造の最適性 : 最適解が部分問題に対する最適解を含んでいること. 例えばから Z への最短路はその経由地から Y への最短路を含んでいる部分問題 : x と y の接頭辞 ( prefxes ) の LS 問題接頭辞 (prefx) x[..m] の接頭辞とは x[..j] ( j m). x = D y = D 全体の LS は x[..] と y[..], x[..] と y[..], x[..] と y[..5], 等の LS を含む LS 長を見つけよう j] を x[..] と y[..j] の LS とするそのとき x と y の LS の長さはどう表せるか? 定理 : j] =, j ] + max( j ],, j]) これはどんな意味か? f = or j =, f x[ ] = y[ j], otherwse LS の再帰解 f = or j =, j] = L L = j = から始める (x と y の空部分列 ) x[..] と y[..] は空列であるから, そのLSは空列 (.e.,] = ) 空列と他のどんな列とのLSは空列であるから, 全てのと j について :, j] = ] = LS の再帰解 L L j] =, j ] + f x[ ] = y[ j], L L j] を計算するにあたってつの場合がある : 場合 : x[]=y[j]: さらに一つの文字が一致, そこで x[..] と y[..j] のLSの長さは, x[.. ] と y[..j ] のLSの長さに加えたもの x = D y = D LS の再帰解 L j ] = L max( j ],, j ]) otherwse 場合 : x[]!= y[j] 二つの記号は一致しないので, 今持っている解は改善しない. すなわち, LS(x[..], y[..j]) の長さは以前と同じ (LS(x[.. ], y[..j]) の長さと LS(x[..], y[..j ]) の長さの最大値 ). なぜ, LS(x[.. ], y[..j ]) の長さではないのか? x[] LS(x[..], y[..])= x = D LS(x[..], y[..])= y = LS(x[..], y[..])= D LS(x[..], y[..])= y[]

6 LS の長さを求めるアルゴリズム LS-Length(x, y). m = length(x) // x の長さを求める. n = length(y) // y の長さを求める. for = to m ] = // y が空. for j = to n,j] = // x が空 5. for = to m // 全ての x[] につき 6. for j = to n // 全 y[j] 7. f ( x[] == y[j]) 8. j] = -,j-] + 9. else j] = max( -,j], j-] ). return c LS の例次の例に LS 長アルゴリズムを適用しよう : x = y = D x と y の LS は何か? LS(x, y) = x = y = D データはバージニア大 Davd Luebke 例 () j 5 y[j] D D 例 () x[] j 5 y[j] D x[] D x = ; m = x = y = D; n = y = 5 配列..5,..] の確保 for = to m ] = for j = to n,j] = 例 () j 5 y[j] D x[] f (x[] == y[j] ) j] = -,j-] + else j] = max( -,j], j-] ) D 例 () j 5 y[j] D x[] f (x[] == y[j] ) j] = -,j-] + else j] = max( -,j], j-] ) D

7 例 () j 5 y[j] D x[] f (x[] == y[j] ) j] = -,j-] + else j] = max( -,j], j-] ) D 例 (5) j 5 y[j] D x[] f (x[] == y[j] ) j] = -,j-] + else j] = max( -,j], j-] ) D 例 (6) j 5 y[j] D x[] f (x[] == y[j] ) j] = -,j-] + else j] = max( -,j], j-] ) D 例 (7) j 5 y[j] D x[] f (x[] == y[j] ) j] = -,j-] + else j] = max( -,j], j-] ) D 例 (8) j 5 y[j] D x[] D 例 () j 5 y[j] D x[] D f (x[] == y[j]) j] = -,j-] + else j] = max( -,j], j-] ) f (x[] == y[j] ) j] = -,j-] + else j] = max( -,j], j-] )

8 例 () j 5 y[j] D x[] D 例 () j 5 y[j] D x[] D f (x[] == y[j] ) j] = -,j-] + else j] = max( -,j], j-] ) f (x[] == y[j] ) j] = -,j-] + else j] = max( -,j], j-] ) 例 () j 5 y[j] D D 例 () j 5 y[j] D x[] x[] D f (x[] == y[j] ) j] = -,j-] + else j] = max( -,j], j-] ) f (x[] == y[j] ) j] = -,j-] + else j] = max( -,j], j-] ) 例 (5) j 5 y[j] D x[] f (x[] == y[j] ) j] = -,j-] + else j] = max( -,j], j-] ) D LS 長アルゴリズムの実行時間 LS 長アルゴリズムは配列 m,n] の各要素を一度だけ計算する従って実行時間は O(m*n) というのも各 j] の計算は一定時間だし, 要素数は m*n

9 LS そのものの見つけ方先ほどのアルゴリズムでは LS 長はわかったが LS そのものはわからない. しかしながらちょっとの工夫で LS 自体を求めることができる. 各 j] が依存するのは,j] と j ] とかまたは, j ] 各 j] についてどうやってそれを得たかがわかる : 例えば, ここでは j] =,j ] + = += LS そのものの見つけ方再帰的定義は, j ] + j] = max( j ],, j]) そこで m,n] から始めて戻ればよい f x[ ] = y[ j], otherwse j] = -, j-]+ ならばいつでも, x[] を記憶 ( なぜなら x[] は LS の一部分 ) = または j= (.e. すなわち端に辿り着いたとき ), 記憶した文字列を逆順に出力 LS の見つけ方 j 5 y[j] D x[] LS の見つけ方 () j 5 y[j] D x[] LS ( 逆順 ): LS ( 正順 ): ( 回文になったのは偶然 ) 動的計画法まとめ解が再帰的に部分問題の解を用いて表現できる ( 部分構造の最適性 optmal substructure がある ) ときに使える分割統治法 (dvde and conquer) とそっくりであるが, 部分解を何回も再利用することで効率向上分割統治は部分問題が共通でないときのアイデアすなわち動的計画法のアルゴリズムは部分問題の解を見つけるとそれを記憶し次に同じ部分問題が表れるとそれを使用する動的計画法 (dynamc programmng) が非常に有効となる問題群がある解が部分問題の解から再帰的に構成されるときこれら部分解を記憶し必要に応じて再利用する実行時間比較 ( 動的計画法 vs. 力ずく ): LS: O(m*n) vs. O(n * m ) - ナップザック問題 : O(W*n) vs. O( n )

Microsoft PowerPoint - ad11-09.pptx

Microsoft PowerPoint - ad11-09.pptx 無向グラフと有向グラフ無向グラフ G=(V, E) 頂点集合 V 頂点の対を表す枝の集合 E e=(u,v) 頂点 u, v は枝 e の端点 f c 0 a 1 e b d 有向グラフ G=(V, E) 頂点集合 V 頂点の順序対を表す枝の集合 E e=(u,v) 頂点 uは枝 eの始点頂点 vは枝 eの終点 f c 0 a 1 e b d グラフのデータ構造グラフ G=(V, E) を表現するデータ構造