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

■

1

1

章

 

アルゴリズムで考える

大事なのはアルゴリズム（

algorithm

）だ。ある環境で、どのアルゴリズムを使う

べきかを判断できるかどうかは、作成したソフトウェアに大きな違いをもたらす。

本書をソートや探索のような重要な数多くのアルゴリズム領域での学習のガイド

ブックにしてほしい。問題解決アルゴリズムで使われる分割統治法や貪欲戦略など

の一般的な方法をいくつも紹介する。この知識を活用すれば、自分のソフトウェア

の効率を改善できる。

コンピューティングの黎明期から、データ構造はアルゴリズムと切っても切れな

い関係にある。本書では、効率的な処理のために情報を適切に表現する基本データ

構造を学ぶ。

アルゴリズムを選ぶときにはどうしなければならないか。以降の節において、こ

の問題を探求する。

1.1

 問題を理解する

アルゴリズム設計の第

1

ステップは、解きたい問題の理解である。コンピュータ

サイエンスの例題を手始めに取り上げる

。

2

次元平面で図1-1に示されるような点集

合

P

が与えられ、輪ゴムでこれらの点の周りを囲んで手を離したときの絵を描く。

得られる図形は、凸包（

convex hull

）、すなわち、

P

の全点を囲む最小の凸形状（凹

みのない形）である。課題は

2

次元の点集合から凸包を計算するアルゴリズムを書

くことだ。

P

の凸包を描くことができたとすると、

P

内の任意の

2

点を結ぶ線分は、凸包内

に完全に含まれる。凸包の点を時計回りに番号を振ったと仮定しよう。すると、凸

包は、

h

個の点

L

0

, L

1

,

…

L

h

−

1

の時計回りの ...