答えの候補と、正しさの理由を分ける
アルゴリズムを作るときは、計算手順だけでなく、なぜその手順が正しい答えを残すかを考えます。目の前でよく見える選択を繰り返す方法、問題を独立な小問題へ分ける方法、重なった小問題の答えを再利用する方法は、それぞれ異なる条件で役立ちます。
同じ問題でも、入力の性質によって使える方法は変わります。全探索で小さな入力の正解を確かめた後、どこに無駄や再利用できる計算があるかを探すと、改良の理由が明確になります。先に手法名だけを決めて、問題を無理に当てはめる必要はありません。
貪欲法には、選択を確定してよい理由が要る
貪欲法は、その場の基準に沿って選択し、通常は過去の選択を戻さず進みます。例えば、硬貨をできるだけ少なく使う問題で、大きい硬貨から取る方法を考えられます。しかし、硬貨が1、3、4で金額が6なら、4、1、1の3枚より、3、3の2枚の方が少なくなります。大きいものから取る直感だけでは証明になりません。
ある問題で貪欲法を使うなら、その選択を含む最適解が存在することや、他の解の一部を交換しても悪化しないことなどを示します。小さい例で成功することと、すべての許された入力で成功することは別です。反例を探す作業も、手法の適用条件を理解するために役立ちます。
分割統治と動的計画法の違い
マージソートでは、配列を小さく分け、それぞれを整列し、結果を併合します。小問題を解いた結果から全体を作れることが設計の鍵です。動的計画法では、同じ状態の答えを何度も求める重複を見つけ、記録して再利用します。単に再帰を使っているかどうかで、両者を区別するわけではありません。
先ほどの硬貨問題なら、金額xを作る最小枚数をf(x)として、到達可能なx-cから硬貨cを1枚加える候補を比べます。f(0)=0を出発点とし、金額を小さい方から処理すれば、必要な小問題を先に解けます。作れない金額の扱いと、使ってよい硬貨の条件も、状態と遷移の定義に含めます。
状態の数と、計算の前提を確かめる
動的計画法は、あらゆる難しい問題を少ない時間で解く魔法ではありません。状態が増えすぎれば、時間もメモリも足りなくなります。硬貨問題で金額の上限をAとすると、金額ごとの表を作る仕事はAに依存します。入力に金額を何桁で表したかという尺度とは、区別して考える必要があります。
設計を説明するときは、状態や分割の意味、遷移や併合の規則、基底条件、正しさの理由、計算量をセットにします。「最適そうだから」「再帰にしたから」だけで終えず、小さな例を手で追い、境界値と反例を試しましょう。性能評価は、その正しさが確認できた後に進めます。