貪欲法
出典: フリー百科事典『ウィキペディア（Wikipedia）』
貪欲法（どんよくほう 英 greedy algorithm）とはアルゴリズムの一種、欲張り法（よくばりほう）、グリーディ算法（-さんぽう）ともいう。
[編集] 概要
貪欲法とは局所探索法と並んで近似アルゴリズムの最も基本的な考え方の一つである。
このアルゴリズムは問題の要素を複数に分割し、分割した要素をそれぞれ独立に評価を行い。評価値の高い順に問題に取り込んでいくことで解を得るという方法である。
単純なソートのみでプログラムを実装することが可能であるが、問題を複数に分割する方法は特に組合せ最適化問題と相性が良く、問題によっては最適解を得られたり、最低限の精度保証（近似度）が算出可能なものもある。このため、現在でもしばしば同問題の研究に用いられている。
[編集] 貪欲法の例
以下にナップサック問題での適用例を示す。この問題の場合は各荷物ごとに分割して評価することで適用可能である。
- ナップサック問題の各荷物の評価値を決定する。（価値）÷（容積）という数字がよく使われる。
- 評価値の一番高い荷物を選ぶ。
- その荷物をナップサックに入れても最大容量を越えないならナップサックに入れる。
- 全ての荷物を評価値の順に選び上記の操作を繰り返す。
なお、この問題に関しては貪欲法では最適解を得ることはできない。
[編集] 擬似コード
以下の擬似コードでは荷物の数を n とし、荷物 i の容量と価値はそれぞれ w[n]、c[n] に格納されているとする。評価値は e[i] ナップサックの現在の容量は W 最大容量は max に格納されており、返すコストを C とする。
for i := 1 .. n
e[i] := c[i] / w[i]
e[i] の値を降順にソートして、 c[i], w[i] をそれに合わせて並び替える。
C := 0; W := 0
for i := 1 .. n
if w[i] + W < max then
W := W + w[i]
C := C + c[i]
return C
