情報数理科学 Ⅶ/ 広域システム特論 Ⅴ/ 広域システム科学特殊講義 Ⅳ 算法の設計と解析 http://www.graco.c.u-tokyo.ac.jp/~kawamura/t/ad/ 平成 29 年 5 月 8 日河村彰星
Dynamic Programming 動的計画法とは 漸化式を使って値を順次記録しながら求める方法 問題 フィボナッチ数列の第 n 項を求める 1 n = 0 のとき f n = ቐ1 n = 1 のとき f n 1 + f n 2 他 そのまま再帰呼出しにすると f(n) { if (n が 0 か 1) return 1 else return f(n - 1) + f(n - 2) fi } f(1) f(2) f(0) f(3) 一回やった計算の結果は覚えておこう 同じ函数呼出しを何度もするせいで非効率 f(1) 1 f(4) f(1) f (2) f(0) 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] := 1 else table[i] := table[i - 1] + table[i - 2] fi end table[n] } 0 1 2 3 4 5 6 7 8 1 1 2 3 5 8 13 21 34 この表を左から右に順に埋めてゆく 時間計算量 O n 空間計算量 O n どうしてそれだけのことにゴツい名前が付いてるんですか? 軍の資金で研究させてもらうためになんか強そうな名前にしといた ( 大意 ) リチャード ベルマン (Richard Bellman, 1920~84) 実際の問題に適用するにはうまく 端から埋めていける ような漸化式を見つける必要がある 自伝 (1983) より
問題 入力 出力 重みつき活動の選択 開始 終了時刻と価値の指定された幾つかの活動 活動 j は時刻区間 s j, f j に行われ価値が v i 互に重ならない活動の集合のうち価値の和が最大のもの 終了時刻順 1 2 3 4 5 6 7 8 12 23 20 26 13 0 1 2 3 4 5 6 7 8 9 10 11 20 各活動の価値が 1 ならば終了時刻順に並べて貪慾法 ( 前回 ) でよいが 11 価値 16 時刻
最適値が満す漸化式 活動を終了時刻順に並べ替えておき活動 j と重ならない最後の活動 i < j( なければ 0) を p j とする 活動 1~j のみを使って得られる最大価値 OPT j は? 終了時刻順 1 2 3 4 5 6 7 8 12 23 20 13 26 0 1 2 3 4 5 6 7 8 9 10 11 20 11 16 下図の例では p 8 = 5 p 7 = 3 p 2 = 0 時刻
最適値が満す漸化式 活動を終了時刻順に並べ替えておき活動 j と重ならない最後の活動 i < j( なければ 0) を p j とする 活動 1~j のみを使って得られる最大価値 OPT j は? 活動 j を選ぶ場合 p j + 1 以降の活動は j と重なるので選べなくなる この活動 j で価値 v j が得られ更に活動 1~p j を使って最大価値を得る j を選ばない場合 活動 1~j 1 を使って最大価値を得る 纏めると OPT(j) = 0 j = 0 のとき max v j + OPT p j, OPT j 1 それ以外
OPT(j) を配列 M[j] に記録し 初めから順に計算 compute_opt(n, s 1, f 1, v 1, s n, f n, v n ) { 活動を f 1 f 2 f n となるように整列する ; p(1), p(2),, p(n) を計算する ; M 0 0; for j = 1,, n M j max v j + M p j, M j 1 ; } 最適値 ( 価値の和の最大値 ) はわかったがそれを達成する活動の集合そのものを求めるには? find_solution j { if j = 0 return. else if (v j + M p j > M[j 1]) return j find_solution p j. else return find_solution j 1. }
問題 入力 出力 有向グラフ V, E と各辺 e E の長さ l e 0 頂点 s V 負の辺長を許すと? ダイクストラ法ではダメだった 但し負閉路はないとする s から各頂点 v V への最短の路の長さ d v s 0 5 8 5 4 8 15 12 7 3 14 17 9 9 9 5 4 6 20 1 13 13 11 最短路長 d v = 25 v
負閉路 負閉路が (s から v への途上で辿り着ける所に ) あると -3 辺長の和が負である閉路 5-3 s W 最短路なし その負閉路を何度も通ることで路長を幾らでも下げられるから v 4-4 負閉路 W l W = l e < 0 e W 逆に負閉路がなければ閉路を含まない最短路が存在 ( 従って辺数 n 1 の ) 閉路があったらその部分を除けばよい ( 長さは増えない ) ので
最適値が満す漸化式 辺 i 本以内で s から v へ至る最短路の長さ OPT i, v は? OPT(i, v) = 0 min OPT i 1, v, min OPT i 1, u + l u,v u u,v E それ以外のとき 負閉路がないとすると d v = OPT n 1, v i = 0 かつ v = s のとき i = 0 かつ v s のとき 二次元の表を埋めてゆく動的計画法を使えばよい
shortest_paths (V, E, l, s) { for each v V M 0, v ; M 0, s 0; for i = 1,2,, n 1 for each v V M i, v M i 1, v ; for each u with u, v E M i, v min{m i, v, M i 1, u + l u,v }; } しかし実際には直前の列しか使っていないので (M i, v を求めるときに M i 1, ) shortest_paths V, E, l, s { for each v V M v ; d s 0; for i = 1,2, for each v V } for each u with u, v E M v min{m v, M u + l u,v }; if ( 今回 M の要素が一つも変らなかった ) 終了 ; 空間を節約 時間 Θ mn 空間 Θ n 2 (= 表の大きさ ) 時間 Θ mn 空間 Θ n 問 4.2
問題 入力 出力 背嚢問題 (knapsack problem) 価値と重さの指定された幾つかの品物と重み制限 W > 0 品物 i = 1,, n 価値が v i > 0 重さが w i > 0 重みの和が W 以下で価値の和が最大となる選び方 例 i v i w i 1 1 1 2 6 2 3 18 5 4 22 6 5 28 7 重さ制限 W = 11 品物 3 と 4 を選び価値 40 を得るのが最大 価値 v i の高い順に貪慾法 どれも 重さ w i の軽い順に貪慾法 ダメ 比 v i /w i の大きい順に貪慾法 問 4.1
動的計画法 ( 漸化式を立てよう ) 品物 1,, i を使って ( 重さ制限 W 以内で ) 得られる最大価値 OPT i OPT(i) = ቊ 0 max{opt i-1, v i + } i = 0 のとき それ以外 品物 i を選ばないとき 品物 i を選ぶとき うまく小さい入力に帰着できるようにする必要がある
最適値が満す漸化式 品物 1,, i のみを用いて重さの和 w 以内で実現できる最大の価値 OPT i, w は? 品物 i を選ぶ場合 i を選ばない場合 この品物 i でまず価値 v i が得られ更に品物 1~ i 1 を使って重さ w w i 以内で最大価値を得る 品物 1~ i 1 を使って最大価値を得る つまり 0 i = 0 のとき OPT(i, w) = ቐOPT(i 1, w) w i > w のとき max OPT i 1, w, v i + OPT i 1, w w i それ以外のとき OPT n, W が答
i v i w i 1 1 1 2 6 2 3 18 5 4 22 6 5 28 7 品物 1,, i のみを用いて重さの和 w 以内で実現できる最大の価値 OPT i, w 0 i = 0 のとき = ቐOPT(i 1, w) w i > w のとき max OPT i 1, w, v i + OPT i 1, w w i それ以外のとき 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 w 最適値を達成する品物の選び方を求めるには? 表を作り終えてからこのどちらが選ばれたか調べながら戻ればよい ( 次頁 ) i 5 0 1 6 7 7 18 22 28 29 34 35 40
i v i w i 1 1 1 2 6 2 3 18 5 4 22 6 5 28 7 品物 1,, i のみを用いて重さの和 w 以内で実現できる最大の価値 OPT i, w 0 i = 0 のとき = ቐOPT(i 1, w) w i > w のとき max OPT i 1, w, v i + OPT i 1, w w i それ以外のとき 0 1 2 3 4 5 6 7 8 9 10 11 w 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を選択 3 0 1 6 7 7 18 19 24 25 25 25 25 品物 4を選択 4 0 1 6 7 7 18 22 24 28 29 29 40 i 5 0 1 6 7 7 18 22 28 29 34 35 40
定理 入力長の多項式以内にはなってない この算法は時間量 Θ nw 空間量 Θ nw 表の寸法は n + 1 W + 1 = Θ nw であり各成分の計算に定数時間 このように 入力に現れる数 の多項式時間で終了する算法 言い換えればもし入力中の数が二進法ではなく羅列法 (n を 0 n と書く ) で表されていたら多項式時間であるような算法 を 擬多項式 (pseudo-polynomial) 時間の算法と呼ぶことがある 講義後半で 背嚢問題はNP 困難なので多項式時間算法はおそらく存在しないしかし 最適解との差が1% 以内の近似解を求める という問題なら多項式時間で解ける
問題 文字列 u = u 1 u m と v = v 1 v n の編集距離を求める 例 GACGGATTAG と GATCGGAATAG の距離は? 揃え方は色々あるが 文字列の違いの度合を測る尺度二つの文字列を 揃えて 比べる d "GACGGATTAG", "GATCGGAATAG" = 3 GAC-GGATTAG GATCGGAATAG GA-CGG-ATTAG GA-CGGATTAG 4 点 6 点 3 点 GATCGGAAT-AG GATCGGAATAG ( 一致 )0 点 ( 不一致 )1 点 ( 間隙 )2 点 として合計点の最小値 ( すべての揃え方のうちで ) 以下では一般化して文字 p と q を揃えた場合 α pq 点揃えずに間隙を作った場合 δ 点 とする
最適値が満す漸化式 文字列 u 1 u i と v 1 v j との距離 OPT i, j は? u 1 u i 1 v 1 v j 1 u i v j u 1 u i 1 u i u 1 u i v 1 v j v 1 v j 1 v j OPT(i, j) = jδ iδ min α ui v j + OPT i 1, j 1, δ + OPT i 1, j, δ + OPT(i, j 1) i = 0 のとき j = 0 のとき それ以外のとき OPT m, n が答 m n の表を作ることで時間 空間とも Θ mn で求まる ( 省略 )
今日の演習問題 問 4.1 問 4.2 問 4.3 問 4.4 問 4.5 背嚢問題がスライド中の三つの貪慾法では正しく答えられないような入力例をそれぞれ挙げよ 配布 の 2 番 配布 の 4 番 配布 の 5 番 配布 の 8 番 問 4.6 問 4.7 問 4.8 問 4.9 配布 の 11 番 配布 の 17 番 配布 の 19 番 配布 の 22 番 動的計画法の算法を説明するときは表の各マスで 何 を求めるのかを ( それを どう計算するか より前に ) 明記して下さい 今日の配布物は [KT] 第 6 章の章末問題です [KT] クラインバーグ タルドシュ著 ( 浅野 浅野 小野 平田訳 ) アルゴリズムデザイン 共立出版 ( 平成 20 年 )