貪欲法とは

貪欲法（たんよくほう、英: Greedy algorithm）は、問題を解くためのアルゴリズムの一つで、その名の通り「貪欲に」解を求める方法です。ここでいう「貪欲」とは、その時点で最も良さそうな選択を繰り返し行い、最終的な解を得るという意味です。この方法は特に最適化問題において用いられることが多いです。

最適化問題とは、ある条件のもとで最も良い（例えば最もコストが低い、利益が高いなど）解を見つけ出す問題のことを指します。貪欲法は、その解を見つけるために、局所的な最適解を選びながら全体の解を構築していきます。

貪欲法の基本的な手順は以下の通りです。

1. 解を構成する要素の集合から、ある基準に基づいて最も良い要素を選ぶ。
2. 選んだ要素は解の一部とし、残りの要素の集合からまた最も良い要素を選ぶ。
3. 全ての要素が選ばれるか、あるいは問題の条件を満たす解が得られるまでこの選択を繰り返す。

貪欲法の利点は、アルゴリズムが単純で理解しやすく、実装も容易であることです。また、多くの場合で比較的高速に解を得ることができます。しかし、貪欲法が常に最適な解を導くわけではありません。あくまで局所的な最適解を選ぶため、全体としての最適解を見失う可能性があります。

例えば、おつりを出す問題を考えてみましょう。あなたが店員で、1000円の商品に対して5000円を受け取ったとします。このとき、おつりは4000円ですが、最も少ない枚数のお金でおつりを返すにはどうすれば良いでしょうか。日本の通貨では、最も額面が大きい2000円札を使っても、2枚で4000円を作ることができます。これが貪欲法による解です。しかし、もし2000円札がない場合は、1000円札4枚でおつりを返すことになります。

貪欲法は、このように局所的には最適な選択をしていくものの、全体としては必ずしも最適でない場合があります。それでも、多くの問題において貪欲法は有効なアプローチであり、特に計算資源が限られている場合や、完全な最適解を求めることが困難な場合に有用です。

実際のところ、貪欲法が最適解を導くかどうかは問題の性質によって異なります。いくつかの問題では、貪欲法が常に最適解を導くことが証明されています。そのような問題には、活動選択問題やハフマン符号化などがあります。一方で、旅行者問題（巡回セールスマン問題）のように、貪欲法では最適解を得ることが難しい問題も存在します。

要するに、貪欲法は問題解決の手法の一つであり、問題の性質によってその有効性が変わるため、使う場面を選ぶ必要があります。簡単な問題や、ある程度の近似解で十分な場合には非常に役立つアルゴリズムです。