情報数理科学Ⅶ/広域システム科学特殊講義Ⅳ 算法の設計と解析 動的計画法(2) http://www.graco.c.u-tokyo.ac.jp/~kawamura/t/ad/ 河村彰星 再掲 Dynamic Programming 動的計画法とは 漸化式を使って値を順次記録しながら 求める方法 問題 フィボナッチ数列の第 𝑛 項を求める 1 𝑛 = 0 のとき 𝑓𝑛 = ቐ1 𝑛 = 1 のとき 𝑓𝑛−1 + 𝑓𝑛−2 他 そのまま再帰呼出しにすると…… f(n) { if (n が 0 か 1) return 1 else return f(n - 1) + f(n - 2) fi } 同じ函数呼出しを何度もするせいで非効率 f(4) f(3) f(2) f(1) f(0) f (2) f(1) f(1) f(0) 1 1 1 末端は 1 1 1 fib(n) を計算するには再帰呼出しが fib(n) 回以上 一回やった計算の結果は覚えておこう 再掲 動的計画法 最終結果を求めるのに必要な値の「表」を作る • 表が埋まった≒問題が解けた • 表の既に埋めたマスの値は何度も使える f(n) { 何でそれだけのことに 長さ n + 1 の配列 table を用意 名前が付いてるの? for i in 0 .. n if (i が 0 か 1) 軍の資金で研究させてもらうために table[i] := 0 なんか強そうな名前にしといた else table[i] := table[i - 1] + table[i - 2] fi 0 1 2 3 4 5 6 7 8 end 1 1 2 3 5 8 13 21 34 table[n] } この表を左から右に順に埋めてゆく 時間計算量 O 𝑛 空間計算量 O 𝑛 リチャード・ベルマン (Richard Bellman, 1920~84) 実際の問題に適用するには うまく「端から埋めていける」ような漸化式を見つける必要がある 問題 背嚢問題(knapsack problem) 入力 価値と重さの指定された幾つかの品物と 重み制限 𝑊 > 0 品物 𝑖 = 1, … , 𝑛 価値が 𝑣𝑖 > 0 重さが 𝑤𝑖 > 0 出力 重みの和が 𝑊 以下で 例 𝑖 𝑣𝑖 価値の和が最大となる選び方 𝑤𝑖 1 1 1 2 6 2 3 18 5 4 22 6 5 28 7 重さ制限 𝑊 = 11 品物 3 と 4 を選び 価値 40 を得るのが最大 ダメな例 価値 𝑣𝑖 の高い順に貪慾法 重さ 𝑤𝑖 の軽い順に貪慾法 比 𝑣𝑖 /𝑤𝑖 の大きい順に貪慾法 問6.1 どれも正しくないことを示せ 動的計画法 (漸化式を立てよう) 品物 1, …, 𝑖 を使って(重さ制限 𝑊 以内で)得られる最大価値 𝑂𝑃𝑇 𝑖 𝑖 = 0 のとき 0 𝑂𝑃𝑇(𝑖) = ቊ max{𝑂𝑃𝑇 𝑖-1 , 𝑣𝑖 + 品物 𝑖 を 選ばないとき } それ以外 品物 𝑖 を 選ぶとき うまく部分問題に 帰着できるように する必要がある… 最適値が満す漸化式 品物 1, …, 𝑖 のみを用いて 重さの和 𝑤 以内で 実現できる最大の価値 𝑂𝑃𝑇 𝑖, 𝑤 は? 品物 𝑖 を選ぶ場合 この品物 𝑖 でまず価値 𝑣𝑖 が得られ 更に 品物 1~ 𝑖 − 1 を使って重さ 𝑤 − 𝑤𝑖 以内で 最大価値を得る 𝑖 を選ばない場合 品物 1~ 𝑖 − 1 を使って最大価値を得る つまり 𝑖 = 0 のとき 0 𝑤𝑖 > 𝑤 のとき 𝑂𝑃𝑇(𝑖, 𝑤) = ቐ𝑂𝑃𝑇(𝑖 − 1, 𝑤) max 𝑂𝑃𝑇 𝑖 − 1, 𝑤 , 𝑣𝑖 + 𝑂𝑃𝑇 𝑖 − 1, 𝑤 − 𝑤𝑖 それ以外のとき 𝑂𝑃𝑇 𝑛, 𝑊 が答 𝑖 𝑣𝑖 𝑤𝑖 1 1 1 2 6 2 3 18 5 4 22 6 5 28 7 𝑖 品物 1, …, 𝑖 のみを用いて 重さの和 𝑤 以内で 実現できる最大の価値 𝑂𝑃𝑇 𝑖, 𝑤 𝑖 = 0 のとき 0 𝑤𝑖 > 𝑤 のとき = ቐ𝑂𝑃𝑇(𝑖 − 1, 𝑤) max 𝑂𝑃𝑇 𝑖 − 1, 𝑤 , 𝑣𝑖 + 𝑂𝑃𝑇 𝑖 − 1, 𝑤 − 𝑤𝑖 それ以外のとき 𝑤 0 1 2 3 4 5 6 7 8 9 10 11 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 1 1 1 1 1 1 1 1 1 1 2 0 1 6 7 7 7 7 7 7 7 7 7 3 0 1 6 7 7 18 19 24 25 25 25 25 4 0 1 6 7 7 18 22 24 28 29 29 40 5 0 1 6 7 7 18 22 28 29 34 35 40 Knapsack(𝑣1 , … , 𝑣𝑛 , 𝑤1 , … , 𝑤𝑛 , 𝑊) { for 𝑤 = 0, … , 𝑊 最適値を達成する 𝑀 0, 𝑣 ≔ 0. 品物の選び方を求めるには? for 𝑖 = 1 to 𝑛 for 𝑤 = 0, … , 𝑊 表を作り終えてから if 𝑤𝑖 > 𝑤 このどちらが選ばれたか 𝑀 𝑖, 𝑤 ≔ 𝑀[𝑖 − 1, 𝑤]. 調べながら戻ればよい(次頁) else 𝑀 𝑖, 𝑤 ≔ max 𝑀 𝑖 − 1, 𝑤 , 𝑣𝑖 + 𝑀 𝑖 − 1, 𝑤 − 𝑤𝑖 . return 𝑀 𝑛, 𝑊 } 𝑖 𝑣𝑖 𝑤𝑖 1 1 1 2 6 2 3 18 5 4 22 6 5 28 7 𝑖 品物 1, …, 𝑖 のみを用いて 重さの和 𝑤 以内で 実現できる最大の価値 𝑂𝑃𝑇 𝑖, 𝑤 𝑖 = 0 のとき 0 𝑤𝑖 > 𝑤 のとき = ቐ𝑂𝑃𝑇(𝑖 − 1, 𝑤) max 𝑂𝑃𝑇 𝑖 − 1, 𝑤 , 𝑣𝑖 + 𝑂𝑃𝑇 𝑖 − 1, 𝑤 − 𝑤𝑖 それ以外のとき 𝑤 0 1 2 3 4 5 6 7 8 9 10 11 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 1 1 1 1 1 1 1 1 1 1 2 0 1 7 7 7 7 7 7 7 3 0 6 7 7 品物3を選択 1 6 7 7 18 19 25 25 4 0 1 6 7 7 18 24 25 25 品物4を選択 22 24 28 29 29 40 5 0 1 6 7 7 18 22 35 40 28 29 34 定理 この算法は 入力長の多項式 以内にはなってない 時間量 Θ 𝑛𝑊 空間量 Θ 𝑛𝑊 ∵ 表の寸法は 𝑛 + 1 × 𝑊 + 1 = Θ 𝑛𝑊 であり 各成分の計算に定数時間 このように「入力に現れる数」の多項式時間で終了する算法 言い換えれば もし入力中の数が二進法ではなく羅列法(𝑛 を 0𝑛 と書く)で 表されていたら多項式時間であるような算法 を 擬多項式(pseudo-polynomial)時間の算法と呼ぶことがある 再来週~ 背嚢問題はNP困難なので 多項式時間算法はおそらく存在しない しかし「最適解との差が1%以内の解を求める」という問題なら 多項式時間で解ける 問題 文字列 𝑢 = 𝑢1 … 𝑢𝑚 と 𝑣 = 𝑣1 … 𝑣𝑛 の編集距離を求める 文字列の違いの度合を測る尺度 二つの文字列を「揃えて」比べる 例 “GACGGATTAG” と “GATCGGAATAG” の距離は? 𝑑 "GACGGATTAG", "GATCGGAATAG" = 3 揃え方は色々あるが…… GAC-GGATTAG ○○△×○○○△○○○ GATCGGAATAG 4点 ○(一致)0点 △(不一致)1点 ×(間隙)2点 GA-CGG-ATTAG ○○×○○○×○○×○○ GATCGGAAT-AG 6点 GA-CGGATTAG ○○×○○○○△○○○ GATCGGAATAG 3点 として合計点の最小値(すべての揃え方のうちで) 以下では一般化して 文字 𝑝 と 𝑞 を揃えた場合 𝛼𝑝𝑞 点 揃えずに間隙を作った場合 𝛿 点 とする 最適値が満す漸化式 文字列 𝑢1 … 𝑢𝑖 と 𝑣1 … 𝑣𝑗 との距離 𝑂𝑃𝑇 𝑖, 𝑗 は? 𝑢1 … 𝑢𝑖−1 𝑢𝑖 𝑢1 … 𝑢𝑖−1 𝑣1 … 𝑣𝑗−1 𝑣𝑗 𝑣1 … 𝑣𝑗 𝑢𝑖 𝛼𝑢𝑖 𝑣𝑗 + 𝑂𝑃𝑇 𝑖 − 1, 𝑗 − 1 , min 𝑂𝑃𝑇 𝑚, 𝑛 が答 𝑣1 … 𝑣𝑗−1 𝑣𝑗 𝑖 = 0 のとき 𝑗 = 0 のとき 𝑗𝛿 𝑖𝛿 𝑂𝑃𝑇(𝑖, 𝑗) = 𝑢1 … 𝑢𝑖 𝛿 + 𝑂𝑃𝑇 𝑖 − 1, 𝑗 , 𝛿 + 𝑂𝑃𝑇(𝑖, 𝑗 − 1) それ以外のとき 定理 これに従った動的計画法で 時間量 Θ 𝑚𝑛 空間量 Θ 𝑚𝑛 ∵ 表の寸法 空間量を減らせるか? 各列の計算には直前の行しか使わないので 表全体ではなく 一行だけ記憶していればよい Θ 𝑚+𝑛 しかしそうすると最適の揃え方を復元できない 定理 次頁からの算法を使うと 分割統治法と組合せる 時間量 Θ 𝑚𝑛 空間量 Θ 𝑚 + 𝑛 ハーシュバーグ(Hirschberg)の算法 𝑂𝑃𝑇 𝑖, 𝑗 はこのグラフにおいて 頂点 0,0 から 𝑖, 𝑗 への最短距離 𝑓 𝑖, 𝑗 ε ε v1 v2 v3 v4 v5 v6 0-0 u1 𝛼𝑢𝑖𝑣𝑗 u2 u3 𝛿 𝛿 i-j m-n ハーシュバーグ(Hirschberg)の算法 各列の計算は Θ 𝑚 + 𝑛 空間で可能 j ε ε v1 v2 v3 v4 v5 v6 0-0 u1 u2 u3 i-j m-n ハーシュバーグ(Hirschberg)の算法 逆に考えて 𝑖, 𝑗 から 𝑚, 𝑛 への最短距離 𝑔 𝑖, 𝑗 も求まる ε ε u1 v1 v2 v3 v4 v5 v6 0-0 i-j 𝛿 𝛼𝑢𝑖+1 𝑣𝑗+1 𝛿 u2 u3 m-n ハーシュバーグ(Hirschberg)の算法 逆に考えて 𝑖, 𝑗 から 𝑚, 𝑛 への最短距離 𝑔 𝑖, 𝑗 も求まる (空間 Θ 𝑚 + 𝑛 で) j ε ε u1 v1 v2 v3 v4 v5 v6 0-0 i-j u2 u3 m-n ハーシュバーグ(Hirschberg)の算法 頂点 𝑖, 𝑗 を通る路の長さの最小値は 𝑓 𝑖, 𝑗 + 𝑔 𝑖, 𝑗 ε ε u1 v1 v2 v3 v4 v5 v6 0-0 i-j u2 u3 m-n ハーシュバーグ(Hirschberg)の算法 𝑓 𝑞, 𝑛 𝑞, 2 𝑛 2 + 𝑔 𝑞, u1 を最小にする 𝑞 を求めると を通る最短路が存在するので… n/2 ε ε 𝑛 2 v1 v2 v3 v4 v5 v6 0-0 i-j q u2 u3 m-n ハーシュバーグ(Hirschberg)の算法 𝑢𝑞 と 𝑣𝑛/2 を揃えることとし その前後の部分問題を再帰的に解く n/2 ε ε u1 v1 v2 v3 v4 v5 v6 0-0 i-j q u2 u3 m-n この算法の時間量 𝑇 𝑚, 𝑛 は…… 𝑛 𝑛 𝑇 𝑚, 𝑛 = 𝑇 𝑞, + 𝑇 𝑚 − 𝑞, + O 𝑚𝑛 2 2 𝑞 を求めるのに 再帰呼出し かかる時間 つまり或る定数 𝑐 について 𝑇 𝑚, 2 ≤ 𝑐𝑚 𝑇 2, 𝑛 ≤ 𝑐𝑛 𝑛 𝑛 𝑇 𝑚, 𝑛 ≤ 𝑇 𝑞, + 𝑇 𝑚 − 𝑞, + 𝑐𝑚𝑛 2 2 すると 𝑇 𝑚, 𝑛 ≤ 2𝑐𝑚𝑛 が成立つ ∵ 𝑚 + 𝑛 に関する帰納法 𝑛 𝑛 𝑇 𝑚, 𝑛 ≤ 𝑇 𝑞, + 𝑇 𝑚 − 𝑞, + 𝑐𝑚𝑛 2 2 ≤ 𝑐𝑞𝑛 + 𝑐 𝑚 − 𝑞 𝑛 + 𝑐𝑚𝑛 = 2𝑐𝑚𝑛 帰納法の仮定 採点が溜まっててすみません… 演習問題 ・[KT]第六章末問題(前回配布) ・ 問6.1 注意 動的計画法の算法を説明するときは 表の各マスで「何」を求めるのかを (それを「どう計算するか」よりも前に)明記して下さい [KT]クラインバーグ、タルドシュ著(浅野、浅野、小野、平田訳)『アルゴリズムデザ イン』共立出版(平成20年)
© Copyright 2025 ExpyDoc