読み方：どんよくほう

貪欲法【greedy algorithm】グリーディ法

概要

貪欲法とは、アルゴリズムの設計手法の一つで、問題を解く際に、各ステップで最も良く見える選択肢を局所的に選び続けることで最終的な解を導くもの。計算効率の高さから多くの問題で利用される。

基本的な考え方は、複雑な問題を一度にすべて解こうとせず、目の前の状況で最善と思われる選択を繰り返すというものである。将来の結果を見越した複雑な計算を行わず、その時点での最良の選択を積み重ねることで効率よく解を求める。単純なため実装が容易で、計算速度も速いという特徴がある。

例えば、500円、100円、50円、10円の硬貨を使って670円をできるだけ少ない枚数で支払うという問題を解く場合、貪欲法では「最も大きな額の硬貨から順に使えるだけ使う」という方針をとる。500円を1枚、100円を1枚、50円を1枚、10円を2枚と選んでいくことで合計5枚という最適な答えが得られる。日本の硬貨体系ではこの方針が常に最適解をもたらすが、硬貨の種類や額によっては貪欲法が最適解を与えない場合がある。

この手法の難点は、局所的な最良選択が必ずしも全体の最適解につながらない場合があることである。目の前の選択で近道を選んだ結果、後続のステップで行き詰まり、別の選択をした場合より悪い解に至ることがある。このような問題には動的計画法や全探索など別の手法が適している。

なお、貪欲法が有効に機能するためには、「貪欲選択性」と「最適部分構造」という性質が成立している必要がある。貪欲選択性とは、各段階での局所的な最適選択が全体としても最適解につながる性質であり、最適部分構造とは、問題の最適解が部分問題の最適解から構成される性質である。これらが満たされる場合に限り、貪欲法は正しい解を導くことが保証される。