グリーディアルゴリズム
定義
グリーディアルゴリズムは、その瞬間のみを考慮して最も良い選択をする方法だ。
説明
グリードアルゴリズムは、名前が示す通り、長期的な視点を持たずにその瞬間だけを考える。良いことには、常に最善を尽くそうとするが、大局を見たときにこれは賢明ではないかもしれない。次の例を見てみよう：
左の0から始まって右の1に到達するパスを見つける問題を想像してみよう。ただ見つけるだけではなく、最も少ないノードを経由するという条件で、最適解は 0-A-C-E-1(3) になるだろう。しかし、グリーディアルゴリズムは、その瞬間に最も遠くへ行ける道を選ぶ。そのため、この問題をグリーディアルゴリズムで解いた場合、解は 0-B-D-F-G-H-1(5) となり、最適解と比較して2回のコストが余分に発生する。最初の選択が0-Bでなかったり、D-FではなくD-Eを選んでいたら、もっと良い解を選べる可能性があった。
このように、グリーディアルゴリズムは、ほとんどのコンテキストで「良いアルゴリズム」というよりは「愚かな方法」の可能性が高い。しかし、アルゴリズムを動員するほど難しい問題の場合、上の例のように一目で済ませられるほど簡単ではないだろう。そのため、通常、グリーディアルゴリズムを使ってナイーブに解いた後、改良されたアルゴリズムを開発する。