貪欲法と動的計画法の違いを徹底比較！特徴と使い分けをわかりやすく解説

この記事では、アルゴリズム設計における代表的な二つの手法、「貪欲法（グリーディ法）」と「動的計画法（DP）」の違いについて詳しく解説します。

貪欲法（グリーディ法）とは

貪欲法とは、解を部分的に積み上げながら一歩ずつ構築していくアルゴリズムの設計手法です。各ステップでは、その時点で最も明白かつ即座に利益が得られる選択肢を採用していきます。

• 局所的な最適値を選ぶことが、結果として問題全体の大域的な最適解につながるタイプの問題が、貪欲法に適しています。
• 貪欲法が常に最適解に到達する保証はありません。
• 問題の各段階において、その場での最良の選択（局所最適解）を行います。
• 過去の解や値に立ち戻って修正する必要がないため、メモリ使用量の面で非常に効率的です。
• 一般的に、動的計画法と比べて高速に動作します。
• 代表例：ダイクストラ法による最短経路アルゴリズム。計算量は O(E log V + V log V)。
• 解は前方方向へ一方向に計算され、以前の値や解を再訪したり書き換えたりすることはありません。

動的計画法（DP）とは

動的計画法とは、部分問題の計算結果を保存しておき、後で同じ計算が必要になったときに再計算を避けられるようにする最適化手法です。保存済みの結果を取り出すだけで済むため、時間計算量を指数関数オーダーから多項式オーダーへと大幅に削減できます。

• 例：再帰的な解法は、計算結果を記録する仕組みを加えることで、動的計画法として実装できます。
• 各ステップでの判断は、現在直面している問題と、すでに解いた部分問題の解を組み合わせて行われ、それらをもとに最適な値・解を導きます。
• 動的計画法で得られる解が最適解であることは理論的に保証されています。
• ここで選ばれるのは大域的な最適解です。過去に計算した状態の値を保存・参照するための漸化式（定式化）を用います。
• メモ化のためにDPテーブルが必要となるため、メモリ使用量（空間計算量）は増加します。
• 貪欲法と比較すると、処理速度は相対的に遅めです。
• 代表例：ベルマン・フォード法。計算量は O(VE)。
• 動的計画法は、最適解が得られた小さな問題から順に発展させていくボトムアップ方式、あるいはトップダウン方式（メモ化再帰）によって解を決定します。

貪欲法と動的計画法の比較まとめ

このように、貪欲法は「その場限りの最善を選んで高速に解を得る手法」、動的計画法は「部分問題の結果を再利用して厳密な最適解を導く手法」という違いがあります。問題が貪欲選択性質（グリーディ・チョイス・プロパティ）を満たすかどうかなど、問題の性質に応じて両者を使い分けることが重要です。