アルゴリズム論

『アルゴリズム論』は、浅野 哲夫、和田 幸一、増澤 利光の 3 氏による共著で、情報処理学会が編集する IT Text シリーズの 1 冊として、オーム社から 2003 年 7 月に刊行された大学向けのアルゴリズムの教科書です。版元は本書を洗練されたアルゴリズムへの道筋を解説した大学テキストと紹介し、さまざまな最適なアルゴリズムについて、どのように改善して洗練されたアルゴリズムに到達できたかを説明することで、基礎から標準的な設計技法まで学べると案内しています。探索と整列、データ構造、グラフ、文字列照合、設計手法、近似アルゴリズム、計算複雑さまでを 1 冊で通したい情報系の学部生に向いた教科書です。

全 10 章の構成、探索問題から計算複雑さまで

構成は全 10 章に参考文献と演習問題へのヒントが続き、各章の末尾に演習問題が置かれています。1 章「アルゴリズムの重要性」でアルゴリズムの記述、効率、最適性という見方を導入したあと、2 章「探索問題」は逐次探索から「m-ブロック法」「2 分探索法」「ハッシュ法」へと進みます。3 章「基本的なデータ構造」は配列と連結リスト構造、スタックとキュー、ヒープを扱い、4 章「動的探索問題とデータ構造」で「2 分探索木」「平衡 2 分探索木」「動的ハッシュ法」へと話を広げます。5 章「データの整列」はバブルソートからシェルソート、ヒープソート、クイックソート法、マージソートまでを並べ、最後の節で「ソート問題の計算複雑度」を取り上げます。後半は 6 章「グラフアルゴリズム」がグラフの探索、最短経路問題、ネットワークフロー、7 章「文字列のアルゴリズム」が力まかせ法、ラビン－カープ法、クヌース・モリス・プラッツ法、ボイヤー・ムーア法、8 章「アルゴリズム設計手法」が再帰、分割統治法、動的計画法、グリーディ法、分枝限定法、線形計画法を扱います。9 章「近似アルゴリズム」はナップサック問題と巡回セールスパーソン問題、10 章「計算複雑さ」は計算可能性と「クラス P と NP」で締めくくられます。

改善の過程を追う読み方と、計算量で比べる意味

同じ問題を解く手順でも、データが 10 倍、1000 倍と増えたときの振る舞いは手順ごとに大きく違います。逐次探索と 2 分探索、バブルソートとヒープソートの差は、手元の小さな入力では体感しにくい一方、入力の大きさに対する手間の増え方、つまり 計算量 で比べると一目で分かります。2 章で逐次探索から順序関係を使う探索、m-ブロック法、2 分探索法へと節が並び、5 章で単純な整列法から順に並べた最後にソート問題の計算複雑度が置かれている並びは、素朴な手順から出発して改善を重ね、最後にそれ以上速くできるのかという限界を問う流れとして読めます。版元の紹介文が言う改善の道筋とは、このように手順を比べ、より良い手順へ進む理由を確かめる学び方を指していると読めます。

設計手法と近似アルゴリズム、難しい問題への向き合い方

8 章の設計手法は、個々の解法を覚える段階から、新しい問題に手順を自分で組み立てる段階へ移るための章です。分割統治法は問題を小さく分けて解を組み合わせ、動的計画法 は重なり合う部分問題の答えを再利用し、グリーディ法はその場で最善の選択を積み重ねます。分枝限定法は探索の枝を見込みで刈り込む手法で、厳密な答えを求めつつ手間を抑える考え方です。そのうえで 9 章と 10 章は、ナップサック問題や巡回セールスパーソン問題のように、厳密に解こうとすると入力の大きさに対して手間が急増する問題をどう扱うかへ進み、近似アルゴリズムとクラス P と NP の話題に至ります。実務で最適化や経路計算に向き合ったとき、まずこの問題は効率よく厳密に解けそうか、近似で割り切るべきかを見極められることが、この範囲を学ぶ大きな見返りです。

情報系の学部生向け、前提とほかの本との使い分け

版元は本書を情報系大学学部の学生と教員、そしてプログラミングの初級技術者に勧めています。章立ては探索とデータ構造から始まるため、配列やループを使ったプログラムを書いた経験があれば入り口で迷うことは少ないはずですが、後半の計算複雑さは数学的な議論に慣れているほど読みやすくなります。2003 年刊の大学テキストで、扱う題材は特定のプログラミング言語や開発環境に依存しない古典的な範囲ですから、時間を置いても価値が目減りしにくい内容です。反対に、特定の言語でコードを書きながら覚えたい人や、競技プログラミングの解法パターンを素早く集めたい人には、実装を前面に出した別の本のほうが合います。実装寄りの本と理論寄りの本の違いは アルゴリズム本の選び方 にまとめています。講義の教科書や参考書として、あるいは実装寄りの本で覚えた手順がなぜ速いのかを体系立てて確かめ直したい人にとって、探索から計算複雑さまでを章末の演習問題とともに通せる本書は、基礎を固める 1 冊として手元に置く価値があります。