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

392

■

12

章 結び：アルゴリズムの諸原則

な手が選ばれたことを保証するだけであって、ある特定の手が選ばれたことを保証

するものではない。

9

章のアルゴリズムのテストは、浮動小数点計算のためにさらに複雑になる。

凸

包走査

のテスト方法を考えよう。元々の考えは、性能が

O(n

4

)

の力任せの凸包アル

ゴリズムを実行して、その出力を

Andrew

の

凸包走査

の出力と比較するものであっ

た。テストに際して、

[0, 1]

単位正方形内から、一様に抽出した

2

次元データをラン

ダムに生成した。しかし、データセットが十分に大きくなると、この

2

つのアルゴ

リズムの結果が異なるという状況に必ず出くわした。データが隠れていた欠陥を明

らかにしたのだろうか、それとも何か他の要因があるのか。実際に発見したのは、

力任せ凸包アルゴリズムで用いた浮動小数点演算が、

凸包走査

と比べて（非常にわ

ずかな）相違を生み出したということだった。これは偶然だったのだろうか。不幸

なことにそうではない。

線分走査法

も、力任せ交差法と比べると、わずかに違う結

果を出すことを見つけた。

どのアルゴリズムが「正しい」結果を生成するのか。この問題はそう単純なもの

ではない。というのも、浮動小数点値を使うためには、浮動小数点値を比較する一

貫した概念を開発しなければならないからだ。実際、

FloatingPoint.epsilon

を、

2

つの数の差が区別できない閾値であると（適当に）定義した。計算結果が（

10

–9

に

設定した）この閾値に近いと、予期しない振る舞いが起こる