体系ガイド · 入門

貪欲法・分割統治・動的計画法を使い分ける

問題を小さくする方法と、選択の正しさを示す方法を分け、硬貨の例で貪欲法が失敗する条件まで確かめます。

この記事をロゲイアに質問する確認問題3問に進むこれまでの誤答を復習する

更新日

この記事の目次
  1. 答えの候補と、正しさの理由を分ける
  2. 貪欲法には、選択を確定してよい理由が要る
  3. 分割統治と動的計画法の違い
  4. 状態の数と、計算の前提を確かめる
  5. この記事をロゲイアに質問する理解を確かめる

答えの候補と、正しさの理由を分ける

アルゴリズムを作るときは、計算手順だけでなく、なぜその手順が正しい答えを残すかを考えます。目の前でよく見える選択を繰り返す方法、問題を独立な小問題へ分ける方法、重なった小問題の答えを再利用する方法は、それぞれ異なる条件で役立ちます。

同じ問題でも、入力の性質によって使える方法は変わります。全探索で小さな入力の正解を確かめた後、どこに無駄や再利用できる計算があるかを探すと、改良の理由が明確になります。先に手法名だけを決めて、問題を無理に当てはめる必要はありません。

貪欲法には、選択を確定してよい理由が要る

貪欲法は、その場の基準に沿って選択し、通常は過去の選択を戻さず進みます。例えば、硬貨をできるだけ少なく使う問題で、大きい硬貨から取る方法を考えられます。しかし、硬貨が1、3、4で金額が6なら、4、1、1の3枚より、3、3の2枚の方が少なくなります。大きいものから取る直感だけでは証明になりません。

ある問題で貪欲法を使うなら、その選択を含む最適解が存在することや、他の解の一部を交換しても悪化しないことなどを示します。小さい例で成功することと、すべての許された入力で成功することは別です。反例を探す作業も、手法の適用条件を理解するために役立ちます。

分割統治と動的計画法の違い

マージソートでは、配列を小さく分け、それぞれを整列し、結果を併合します。小問題を解いた結果から全体を作れることが設計の鍵です。動的計画法では、同じ状態の答えを何度も求める重複を見つけ、記録して再利用します。単に再帰を使っているかどうかで、両者を区別するわけではありません。

先ほどの硬貨問題なら、金額xを作る最小枚数をf(x)として、到達可能なx-cから硬貨cを1枚加える候補を比べます。f(0)=0を出発点とし、金額を小さい方から処理すれば、必要な小問題を先に解けます。作れない金額の扱いと、使ってよい硬貨の条件も、状態と遷移の定義に含めます。

状態の数と、計算の前提を確かめる

動的計画法は、あらゆる難しい問題を少ない時間で解く魔法ではありません。状態が増えすぎれば、時間もメモリも足りなくなります。硬貨問題で金額の上限をAとすると、金額ごとの表を作る仕事はAに依存します。入力に金額を何桁で表したかという尺度とは、区別して考える必要があります。

設計を説明するときは、状態や分割の意味、遷移や併合の規則、基底条件、正しさの理由、計算量をセットにします。「最適そうだから」「再帰にしたから」だけで終えず、小さな例を手で追い、境界値と反例を試しましょう。性能評価は、その正しさが確認できた後に進めます。

読了と問題の結果を、言語ごとにこのブラウザへ保存します。

コースの順番に沿って学ぶ

CS基礎を固める · STEP 10

学習コースから次を選ぶ