貪欲法
ウィキペディアから無料の百科事典
 |
貪欲法（どんよくほう、英: greedy algorithm）は、アルゴリズムの一種、欲張り法（よくばりほう）、グリーディ算法（グリーディさんぽう）ともいう。
概要
[編集]貪欲法は局所探索法と並んで近似アルゴリズムの最も基本的な考え方の一つである。
このアルゴリズムは問題の要素を複数の部分問題に分割し、それぞれを独立に評価を行い、評価値の高い順に取り込んでいくことで解を得るという方法である。動的計画法と異なり保持する状態は常に一つであり、一度選択した要素を再考する事は無い。このため得られる解は最適解であるという保証は無いが部分問題の解法と単純なソートのみでプログラムを実装することが可能であり、多くの問題に対して多項式時間での近似アルゴリズムとなる。
問題を複数に分割する方法は特に組合せ最適化問題と相性が良い。問題によっては厳密解（最適解）を得られたりするものや最低限の精度保証（近似度）が算出可能なものもある。このため、現在でもしばしば同問題の研究に用いられている。
厳密解（最適解）が求まる例
[編集]いくつかのアルゴリズムは貪欲法を基本戦略としているものの、厳密解が求まることが証明されている。
最適化問題で厳密解となるには、動的計画法同様、部分構造最適性（英: optimal substructure）、つまり、部分問題を解き、それを利用して最適化問題の厳密解が解けることが必要である。
厳密解（最適解）が求まらない例
[編集]以下にナップサック問題での適用例を示す。この問題の場合は各荷物ごとに分割して評価することで適用可能である。
- ナップサック問題の各荷物の評価値を決定する。（価値）÷（容積）という数字がよく使われる。
- 評価値の一番高い荷物を選ぶ。
- その荷物をナップサックに入れても最大容量を越えないならナップサックに入れる。
- 全ての荷物を評価値の順に選び上記の操作を繰り返す。
なお、この問題に関しては貪欲法では最適解を得られない。
擬似コード
[編集]以下の擬似コードでは荷物の数を n とし、荷物 i の容量と価値はそれぞれ w[i]、c[i] に格納されているとする。評価値は 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
