アルゴリズムクイックリファレンス 第2版

■

363

11

章

 

新たな分類の

アルゴリズム

これまでの章では、一般的な問題を解くアルゴリズムについて説明してきた。読

者は、これまでのプログラミング経験において、こういう普通のカテゴリのどれに

も当てはまらない問題に直面してきたはずだ。本章では、そのような課題に挑戦す

るアルゴリズムの

4

つのアプローチについて述べる。

本章のもう

1

つの相違点は、ランダム性と確率とに焦点を絞っていることだ。こ

れまでの章でも、それらをアルゴリズムの平均時の振る舞いの分析に用いてきた。

本章では、ランダム性がアルゴリズムの本質的部分を占める。実際、本章で述べる

確率的アルゴリズムは、決定的アルゴリズムの代わりとして興味深い。同じアルゴ

リズムを同じ入力に対して、異なるタイミングで実行すると、結果がまったく異な

る可能性がある。間違った答えでも受け入れることもあるだろうし、アルゴリズム

がこの問題は解けないとお手上げになることもあるだろう。

11.1

 方式の種類

本書のこれまでのアルゴリズムは、決定性逐次コンピュータ上で、問題のインス

タンスに対して正確な答えを出す。しかし、もっと興味深い研究が、次の

3

条件を

緩めることで行われている。

近似アルゴリズム

問題の正確な答えを求めないで、真の解に近いが必ずしもそれと同等と

は限らない解を受け入れる。

並列アルゴリズム

逐次計算に制限しないで、複数の計算プロセスを作って同時に部分問題

インスタンスを解かせる。