貪欲法

貪欲法（グリーディアルゴリズム）とは

貪欲法（どんよくほう、英: greedy algorithm）は、アルゴリズムの一種であり、欲張り法やグリーディ算法とも呼ばれます。このアルゴリズムは、問題解決の際に、その時点において最も良いと思われる選択を繰り返すことで、最終的な解を得ようとするアプローチです。局所探索法と並び、近似アルゴリズムの基本的な考え方の一つとして知られています。

貪欲法の概要

貪欲法は、問題を複数の部分問題に分割し、それぞれの部分問題を独立して評価します。そして、評価値の高い順に要素を取り込むことで、解を構成します。動的計画法とは異なり、貪欲法では常に一つの状態だけを保持し、一度選択した要素を後から再考することはありません。このため、貪欲法で得られる解は必ずしも最適解であるとは限りませんが、部分問題の解法と単純なソートのみでプログラムを実装できるため、多くの問題に対して多項式時間での近似アルゴリズムとして利用できます。

特に、組み合わせ最適化問題との相性が良く、問題によっては厳密解（最適解）が得られたり、最低限の精度保証（近似度）が算出可能な場合があります。そのため、現在でも様々な問題の研究に用いられています。

厳密解（最適解）が求まる例

いくつかのアルゴリズムは、貪欲法を基本戦略としており、厳密解が求まることが証明されています。以下にその例を挙げます。

ダイクストラ法: 最短経路問題を解くためのアルゴリズム。
プリム法: 最小全域木問題を解くためのアルゴリズム。
* クラスカル法: 同じく最小全域木問題を解くためのアルゴリズム。

これらの最適化問題で厳密解を得るためには、動的計画法と同様に、部分構造最適性（optimal substructure）が満たされている必要があります。つまり、部分問題の解を利用して、元の最適化問題の厳密解が解けることが必要です。

厳密解（最適解）が求まらない例

貪欲法では、必ずしも最適解が得られるわけではありません。その代表的な例としてナップサック問題があります。

ナップサック問題とは、ナップサックの容量制限の中で、できるだけ価値の高い荷物を詰め込む問題です。貪欲法を適用する場合、各荷物の評価値（例えば、価値÷容積）を計算し、評価値の高い順に荷物をナップサックに入れていきます。ただし、この方法では、必ずしも最も価値の高い荷物の組み合わせが得られるわけではありません。

具体的な手順は以下の通りです。

1. 各荷物の評価値（価値÷容積）を計算します。
2. 評価値の高い順に荷物を並べます。
3. ナップサックの容量制限を超えない限り、評価値の高い荷物から順にナップサックに入れます。

この方法で得られる解は、局所的には最適かもしれませんが、全体として最適な解である保証はありません。

擬似コード

ナップサック問題を例に、貪欲法の擬似コードを示します。ここでは、荷物の数をn、荷物iの容量をw[i]、価値をc[i]、評価値をe[i]、ナップサックの現在の容量をW、最大容量をmaxとしています。返すコストをCとします。


for i := 1 to n
e[i] := c[i] / w[i]

// e[i] の値を降順にソートし、c[i] と w[i] もそれに合わせて並び替える

C := 0; W := 0
for i := 1 to n
if w[i] + W < max then
W := W + w[i]
C := C + c[i]
return C


この擬似コードでは、まず各荷物の評価値を計算し、評価値の高い順にソートします。次に、ソートされた順番で、ナップサックに荷物を詰めていきます。ナップサックの容量制限を超えない限り、荷物の価値を合計し、最終的なコストを返します。

まとめ

貪欲法は、シンプルで実装が容易なアルゴリズムですが、必ずしも最適解が得られるとは限りません。そのため、問題に応じて、他のアルゴリズムと組み合わせて使用したり、厳密解が必要な場合は動的計画法などのより高度なアルゴリズムを検討する必要があります。しかし、その計算の速さから、多くの問題に対して近似解を求めるために有効なアプローチであることに変わりはありません。

もう一度検索