動的計画法は黒魔術ではない
(qsantos.fr)- Advent of Code 2023 Day 12 のように特殊ケースが多い問題でも、同じ部分問題を繰り返し解く構造を見つければ 動的計画法 で扱える
- 核心は、再帰で問題を分割したうえで重複計算を メモ化 で減らし、必要な値を依存順に埋める反復計算へ移すことにある
- Fibonacci の例では、素朴な再帰は
f(1)を繰り返し評価するが、キャッシュを使えばf(0)からf(n)まで n + 1 個の値 だけ評価すればよい - Levenshtein 距離と Advent of Code Day 12 では、文字列長や規則インデックスのような 状態インデックス をキャッシュキーにして、再帰呼び出しを配列の充填へ置き換える過程を示している
- 動的計画法を身につけると、性能改善だけでなく、アルゴリズムの 中間状態と依存関係 が見えるようになり、メモリ最適化の余地も見つけやすくなる
名前は紛らわしいが、アイデアは単純
- “dynamic programming” という名前は、現代的な「プログラミングスタイル」や「動的型付け」のような意味と直接関係があるわけではない
- 核心は、問題をより小さな類似問題に分け、その結果を再利用するアルゴリズム設計の方法である
- 歴史的な意味での “programming” を基準にするとこの表現にも納得がいく、という編集注が添えられている
- 出発点は通常、再帰関数 のように問題を小問題へ分解する形である
- 同じ部分問題が何度も現れるなら、計算結果を保存して再利用する キャッシュ が自然に必要になる
Fibonacci で見るキャッシュと反復化
- Fibonacci 関数は
f(n) = f(n - 1) + f(n - 2)と定義され、素朴な再帰実装は同じ値を何度も計算する f(1)は最終結果に実際に加算される値なので、f(n)が大きくなるほど素朴な再帰の評価回数も急速に増える- 結果をキャッシュしたりメモ化したりすれば、すでに計算済みの
f(4)、f(3)、f(2)を再計算する必要はない - この方式では
f(0)からf(6)まで合計 7 個の値だけを評価し、一般には n + 1 回の評価 にまで減る - さらに一歩進めて、
f(0)、f(1)から必要な値を順に埋めていけば、再帰呼び出し自体が不要になるF[2] = F[1] + F[0]F[3] = F[2] + F[1]- 同じ方法で
F[6] = 8まで計算する
- Fibonacci では配列全体すら必要なく、直前の値とその前の値 の 2 つだけを保持すればよい
- この流れは、数学的定義から始めて反復実装へ移していく体系的な道筋を示している
編集距離の例へ広げる
- 2 つの文字列の編集距離とは、一方の文字列をもう一方へ変換するのに必要な最小編集回数のこと
- 許される編集の種類によって問題は変わる
- 文字の置換だけを許すなら Hamming distance
- 挿入と削除まで許すなら Levenshtein distance
- Levenshtein 距離は、2 つの文字列
A、Bの末尾文字を基準にしてより小さな問題へ分割できる- 末尾文字が同じなら、その 2 文字を無視して残りの文字列の距離を使う
- 末尾文字が異なるなら、置換・削除・挿入のうち最小コストを選ぶ
Aが空ならBのすべての文字を挿入しなければならないのでコストはbBが空ならAのすべての文字を削除しなければならないのでコストはa
- この定義をそのまま Python の再帰に移すと、長い文字列や差異の大きい文字列では非常に遅くなる
- Fibonacci が呼び出し木の各段階でおおむね 2 分岐に増えていたとすれば、この再帰は場合によって 3 分岐 に増える
- Python の
functools.cacheを付ければ、同じ部分文字列の組み合わせに対する計算結果を再利用できる - よりよい実装では新しい文字列を作り続けず、元の文字列
A、Bと部分文字列長a、bだけを渡す - 最後の段階では 2 次元の
cache配列を自前で作り、cache[a][b] = levenstein(A[:a], B[:b])となるよう順に埋めていく - 反復版は
aとbを 0 から文字列長まで走査し、すでに埋められた前の行と前の列の値を参照する
Advent of Code 2023 Day 12 への適用
- Advent of Code 2023年12月12日の問題 は、1 次元の nonogram を解く問題である
- 例の入力は
.??..??...?##. 1,1,3という形式で、?は.または#になりうる - ブルートフォースなアプローチは backtracking を使うが、疑問符が
n個あると 2^n 個の候補 を評価しなければならず、指数的に大きくなる - 同じ部分問題が繰り返される構造が現れる
..#..??...?##. (1),1,3.#...??...?##. (1),1,3- すでに処理した先頭部分を捨てると、それぞれ
.??...?##. 1,3、..??...?##. 1,3のようにほぼ同じ問題になる
- 基本的なバックトラッキング関数は
conditionsとrulesを受け取り、可能な配置数を計算する- 規則が残っていなければ、残りの条件に
#があるかを確認する - 条件が残っていなければ、規則が残っているかを確認する
- 現在の文字が
.または?なら 1 文字進めて計算する - 現在の文字が
#または?なら、次の規則サイズと区切り条件を確認したうえで次の状態へ進む
- 規則が残っていなければ、残りの条件に
- Python では
@cacheを付けるだけでメモ化を適用できる - 動的計画法に変えるには、文字列や規則を切り出して渡すのではなく、文字列オフセット
iと規則オフセットjを状態として使う - その後
cache[i][j]を自前で作り、インデックスを 逆順に埋める方式 で再帰を反復計算に置き換える - Rust 実装の例は記事中の Rust implementation リンクで示されている
キャッシュを自分で埋めると見えてくること
- Advent of Code Day 12 の動的計画法版は、メモ化版より遅く見えることがある
- この差は最適化されていない Python 実装による可能性がある
- キャッシュを自分で構築すると、実際にどの値が必要なのかがより明確に見えてくる
- Day 12 の問題では、動的計画法版を通じて 前の列だけが必要 であることがわかる
- したがって、2 次元配列を「前の列」と「現在の列」を表す 2 本の 1 次元配列に置き換えられる
練習に向いた問題と結論
- 動的計画法は簡単ではないが、ほとんどのプログラマにとって手の届かない技法というわけではない
- 問題を小問題へ分ける方法を理解すれば、多くの状況でメモ化だけでも素朴な実装より大きく改善できる
- さらに習熟すれば、アルゴリズムの一系統を理解し、トレードオフをよりよく把握し、追加の最適化も見つけやすくなる
- 練習対象として次の問題が挙げられている
- 実装後は ベンチマークとプロファイリング を忘れないこと
1件のコメント
Hacker Newsの意見
記事で、動的計画法のアルゴリズムは再帰をキャッシュする賢い方法にすぎない、と指摘している点がよかった。自分の経験では、まず再帰的な解法を見つけることが動的計画法の解法を見つける最良の出発点で、いったん見つかればメモ化は簡単で、大きな高速化をもたらし得る。
ボトムアップの動的計画法より速いこともある。実際に必要な解だけを計算するからだ。要点は、呼び出し木に部分問題が多くても構わないが、異なる部分問題の数は比較的少なくなければならないということ。一度しか必要にならない結果をキャッシュする理由はないし、元の問題を十分に少ない数の異なる部分問題へ分割するのが難しい。
実務上は末尾呼び出しの除去が常に適用されるわけではないので、そのやり方が正しいのだろうが、先により直感的な、トップダウンの再帰キャッシュという観点で学びたかったと思う。
例えばLeetCodeの「株を売買するのに最適なタイミング」シリーズを見ると、https://leetcode.com/problems/best-time-to-buy-and-sell-stoc... のような問題は、配列を埋める方法のほうがずっと自然ではないかと思う。再帰で解いたことはないし、自然な再帰解法があるのかもよく分からない。
上のリンクはIIIだが、初めて取り組む人には最初の問題 https://leetcode.com/problems/best-time-to-buy-and-sell-stoc... から始めると、動的計画法の入門としてよい。
「動的計画法」という名前の由来は、発明者であるRichard Bellmanにある。1950年にRANDで多段階意思決定プロセスに付ける名前を探していたが、当時の国防長官Wilsonは「研究」という言葉を病的に嫌っており、「数学」という言葉はなおさら避けるべきだったという。
BellmanはRAND内で、実際には数学をしているという事実をWilsonと空軍から隠すための名前を必要としていた。そこで、計画・意思決定・思考を扱うが、「planning」はさまざまな理由で適切ではなかったため「programming」を選び、多段階・時間変化の概念を含めるため、古典物理学で正確な意味を持つ「dynamic」を付けた。
「dynamic」は形容詞として否定的な意味で使いにくい点も気に入り、議員も反対しにくい名前だったため、dynamic programmingを自分の活動全体を表す名前として使ったという。
出典: https://alliance.seas.upenn.edu/~cis520/dynamic/2021/wiki/in...
この記事が、まず問題を再帰的に明らかにしたうえで、段階的にキャッシュを追加し、最後には必要な分だけキャッシュサイズを小さくしていくやり方が気に入った。
自分はよく、いきなり動的計画法の解法へ進もうとして行き詰まったり、動かすために無理な努力をしたりしてきた。今後は順番に段階を踏むよう、自分に強制しようと思う。
動的計画法の見事な応用の一つは、ヌクレオチド／タンパク質配列のペアワイズアラインメントだ。
https://en.wikipedia.org/wiki/Sequence_alignment
https://en.wikipedia.org/wiki/Needleman%E2%80%93Wunsch_algor...
https://en.wikipedia.org/wiki/Smith%E2%80%93Waterman_algorit...
とても優秀なアルゴリズムの教授がいて、UCLAで学んだ人だった。動的計画法の授業が素晴らしく、まず単純な解法が指数時間計算量になる問題から始め、問題をより小さな問題に分割して計算量を多項式レベルまで下げ、さらにメモ化を適用して線形まで落とした。
そのとき使っていた問題が何だったのか思い出せるといいのだが。
いずれも素朴な解法は非効率で、動的計画法によって大きく改善される代表的な例だ。
さらに多くの例は https://en.wikipedia.org/wiki/Dynamic_programming#Algorithms... を見るとよい。
「この2つの科目は一緒に履修しなければならない」のような特殊な制約を追加すると、普通の動的計画法よりずっと複雑で扱いにくくなると理解している。
元サイトがトラフィックに耐えられていないようなので、アーカイブリンクを残しておく。
https://web.archive.org/web/20240114111200/https://qsantos.f...
動的計画法のおかげで合法な囲碁局面数を計算でき、その値は171桁の数字だった。
素朴な方法では n×n の碁盤上のすべての可能な局面を見るため 3^(n^2) の時間がかかるが、動的計画法は実質的に1次元を取り除き、時間計算量を O(n^5 * 5.4^n)、空間計算量を O(n * 5.4^n) に減らす。
https://tromp.github.io/go/legal.html
https://tromp.github.io/go/gostate.pdf
「Dynamic Programming」という名前が不自然に見えることがあるのは、ここでの programming がプログラミング分野を意味していないからだ。この場合は線形計画法と同じように、最適化に近い意味である。
動的計画法は、離散時間の意思決定問題、つまり制約下で \sum_t u_t(a_t) を最大化する最適な順序 {a_t} を選ぶ問題を解く方法だと見なせる。価値関数 V* を V*(t) = max_{a_t}{ u_t(a_t) + V*(t-1) } と定義し、最適化問題の次元を大きく削減する方式である。
「動的計画法」と聞いたとき、単にメモ化だと考えるのは間違いなのだろうか？ 欠けている部分は、メモ化を使うために問題を賢く分割することかもしれない
動的計画法は体系的なメモ化に近い。だんだん大きな部分問題を解いて、全体問題の解に到達する。「帰納アルゴリズム」という言い方もある程度しっくりくる。典型的な動的計画法のアルゴリズムは、実質的に数学的帰納法の証明に似ているからだ。残念ながら、その用語はすでに別の意味で使われている
その後、再帰とメモ化にはオーバーヘッドがあることを見て、表を下から上へ構築し、再帰呼び出しを取り除けば動的計画法になる
第3段階が動的計画法の最も特徴的な部分だが、第2段階で止まっても動的計画法と呼ぶことはできると思う。ただし、可能な限り効率的というわけではない。別の言い方をすれば、メモ化はキャッシュであり、そのキャッシュを事前に埋める方法があるかを問うのが第3段階だ
一般に、部分問題が多く重なり、最適な部分問題が全体の最適解の一部にならなければならないなら、動的計画法の機会がある。メモ化だけが動的計画法だと言うのは、ハッシュテーブルだけが抽象データ型だと言うのに似ている
メモ化は基本的に、アルゴリズムを高速化するための戦略だ
今年のAdvent of Codeを終えるのは楽しかった。1日目、とくにパート2が例年よりはるかに難しかったのは明らかで、それについてはhttps://blog.singleton.io/posts/2024-01-02-advent-of-code-20...にも書いたが、現在の2022年の統計と現在の2023年の統計を比較するだけでは明確ではない。2022年のパズルは、人々が解く時間がさらに1年あったからだ
2023年1月14日時点の2022年の統計 https://web.archive.org/web/20230114172513/https://adventofc...を取ってみると、差はかなり大きかった。パート2完了の統計 https://blog.singleton.io/static/imgs-aoc23/completion.pngを描いてみると、1日目開始時の集団規模は似ていたが、2023年は15日目まで2022年より明らかに難しそうに見える
パート1を解いてパート2を解けなかった人の割合 https://blog.singleton.io/static/imgs-aoc23/ratios.pngも、2023年は多くの日でかなり高く、とくに5日目、10日目、12日目、そして22日目パート2が難しかったことを示唆している
ただし、5日目パート2がどれほど難しかったかには驚いた。諦めずに解きはしたが、何か明らかなことを見落として過度に複雑に解いたのではないかと思っていたので、もともと少し挑戦的な問題だったと分かって安心した
例として
two1nine、eightwothree、abcone2threexyz、xtwone3four、4nineeightseven2、zoneight234、7pqrstsixteenが与えられていたが、oneightのような重要な例が欠けていた。このような例がないと、値をどう置換すべきかを正確に見極めるのは難しい2022年には序盤の数日間、ほとんどの人が参加し続け、多くの日で継続率が80%を超え、ほぼ全員が2つのパートを解いた。一方、2023年の1日目は、パート1を解いた人のうちパート2まで解いた割合が76%にとどまり、3日目と5日目で多くの人が諦めた
興味深いことに、終盤の数日はそこまで低くないが、これは2023年のAdvent of Codeが2022年より新しいという点で説明できる。私の解釈では、この集団は難易度に関係なく、ある程度まではすべての挑戦を乗り越える人たちであり、他の多くの人たちは時間がかかりすぎると感じるとやめてしまうのだ