[toc]
今回は、貪欲アルゴリズムについて、簡単に紹介していきます。
貪欲アルゴリズムとは
そもそも、アルゴリズムとは何かというと、「問題を解くためにどのようにすればよいか」を定式化したものです。
身近な例でいうと、電化製品を買った時などに説明書がついてくると思います。そこに書いてある製品を使うための手順もアルゴリズムであるといえます。
問題を解く方法（アルゴリズム）は多種多様に考えることができます。例えば、効率的に解ける方法や最適な解が求められる方法などです。その中でも、貪欲アルゴリズムについて説明していきます。
貪欲アルゴリズム
貪欲アルゴリズムとは、その時点で最善だと思うものを選んでいく手法です。
貪欲アルゴリズムを使う問題として、ナップサック問題が有名です。ナップサック問題を解きながら、貪欲アルゴリズムの動きを見ていきます。
ナップサック問題
ナップサック問題は、以下のようなナップサック(リュック)に荷物を詰めるという状況でにナップサックに詰めるサイズの上限が決まっているとき、価値を最大にできる荷物の組合せを求める問題です。
貪欲アルゴリズムにしたがって、その時点での最善だと思うものを選んでいきたいのですが、ここでいう最善とはサイズができるだけ小さくて、価値が高いものだとします。
この問題を愚直に解こうと思うと、荷物のすべての組合せを考えることになります。荷物が4個のときは、それぞれの荷物を入れる場合と入れない場合の2通り考えて、その選択が4回あるので、2^4通りあることになります。
このように、全通りを試すとなると、荷物の数をnとして、増やしていくと、組合せの総数が2^n通りになり爆発的に増えていくことがわかります。ここで、全通り試すことなく答えを求めたときに用いられるアルゴリズムの1つが貪欲アルゴリズムです。
貪欲アルゴリズムの実行例
- リュックに何も入っていない状況からスタートします。
- 1番目に効率が良いのは、お弁当なのでリュックに入れます。
- 2番目に効率が良いのは、ノートなのですが、リュックの残りサイズが1であるため、入れることはできません。
- 3番目に効率が良いのは、筆箱なのですが、リュックの残りサイズが1であるため、入れることはできません。
- 4番目に効率が良いのは、水筒なのですが、リュックの残りサイズが1であるため、入れることはできません。
- リュックに入れる荷物の候補がないので、終了します。
貪欲アルゴリズムの結果、お弁当がリュックに入り、総価値は240になりました。
このように貪欲アルゴリズムでは、全通り(16通り)試すことなく、少ない工程で終了しました。
一方で、全体のことは考えずに今の時点で最善なものを選んでいくことになるため、貪欲アルゴリズムでいつでも厳密な答えが得られるとは限りません。実際、この例ではノートと筆箱を選ぶことで総価値が245になり、この答えが厳密な答えとなります。
近似アルゴリズム
ここで、厳密な答えでないにしても、貪欲アルゴリズムでは、総価値が厳密な値に近い値になるような荷物の組合せを求めることができました。
このように、厳密な答えは求められなかったとしても、近い値を求めるアルゴリズムを近似アルゴリズムといいます。
貪欲アルゴリズムは近似アルゴリズムの一つです。近似アルゴリズムで求めた解を近似解といいます。
近似アルゴリズムでは、最悪でも厳密解と「これぐらい」は近いということが保証されていて、この「これぐらい」を「近似比」といって、近似比が1に近いほど、良いアルゴリズムであるといえます。
一方で、近似比が保証されていないアルゴリズムをヒューリスティックといいます。
実際にはヒューリスティックのほうが厳密解に近い値になる場合もありますが、保証されていないため、入力によってはとんでもない値を出力してしまうということもあるため、使う際は注意が必要です。
まとめ
- 貪欲アルゴリズムは全通りを試すより、効率的に近似解を求めることができる。
- 問題によっては、貪欲アルゴリズムでいつでも厳密解が得られる場合もある。
