警告: 貪欲は愚か
本当に運が良ければ、再帰方程式や表などを何も考えない貪欲な (greedy)アルゴリズムで問題が解けてしまうことがあります。貪欲なアルゴリズムはバックトラッキングを使ったアルゴリズムと同じように決断を積み重ねることで解を作りますが、再帰的な小問題を解くことなく愚直に一度だけ決断を行います。このアプローチはとても自然に見えるかもしれませんが、上手く行くことはまずありません。貪欲なアルゴリズムによって解ける最適化問題はとても稀です。にもかかわらず、多くの学生はバックトラッキングや動的計画法を使って解くべき問題の多くに対して貪欲な戦略を最初にひらめきます。
例えば分かち書きの問題に対する貪欲なアルゴリズムとして、入力の文字列の接頭部分の単語で最短 (あるいは最長) のものを選び、それを最初の単語と決めつけ、入力の接尾部分に対して再帰的に同じことを行う、という処理が考えられます。あるいは最長増加部分列の問題に対する貪欲なアルゴリズムとして、入力配列から一番小さな要素を出力配列の先頭として選び、それよりも後ろの部分から最長増加部分列を再帰的に選ぶ、という処理が考えられます。こういったやり方が馬鹿げたハックに思えたなら、ご名答です。これらは正しい解法からかけ離れています。
というわけで、あなたは次の文章をタトゥーにして、腕の内側、対数とビッグオー表記の公式の隣にしっかりと刻んでおくべきです:
貪欲なアルゴリズムは絶対にダメだ！
線形計画法を使え！
え、絶対に？
そうだ、絶対だ！
え、絶対に？
...まず間違いなく絶対だ1。
貪欲な解法が非常に誘惑的であるにもかかわらず正しいことがほとんど無いために、私はアルゴリズムの講義における次のポリシーを提唱しています。アルゴリズムの正しさの証明を普通は求めないような講義であっても (というより、そのような講義であればなおのこと)、このポリシーをお勧めします2。
宿題や試験において貪欲なアルゴリズムを解答した場合、たとえアルゴリズムが正くても、正しさのきちんとした証明が無いならば点数を一切与えない。
さらに言えば、生徒が貪欲なアルゴリズムを提出しがちな問題は、動的計画法を使って解くのがベストなことがほとんどです。そこで私はアルゴリズムの講義を取った生徒に対して、次のアドバイスを必ずするようにしています:
貪欲 (greeDY) という単語を書いたとき、あるいは考えたときにさえ、あなたは無意識のうちに動的計画法 (DYnamic programming) を考えている。
解こうと思えば貪欲なアルゴリズムで解くことができる問題であっても、まずはバックトラッキングや動的計画法を使ったアルゴリズムを作った方が速く作れて生産的なことが普通です。「まず動くようにせよ。それから速くせよ」です。貪欲なアルゴリズムが特定の問題の対しては正しいことを示すテクニックについては次の章で見ます。