3行でいうと

  • 擬似コードで手順を書き、なぜ正しいかを数学的に証明する。
  • 計算量をO・Ω・Θの記法で厳密に分析し、手法を比べる。
  • 分割統治・動的計画法・貪欲法など、設計の技法を体系立てて示す。

向いている人

アルゴリズムの正しさと計算量を、証明まで踏み込んで理解したい学生や技術者。

読む意味

データ構造や設計技法を選ぶ判断の根拠を、体系的に確かめられる。技術面接の定番の問題の土台にもなる。

読むときの注意

数式と証明が多く、初学者には難しい。日本語版は原著第4版の抄訳で、特選トピックなど第7部以降は邦訳の第1・2巻には含まれない。

どんな本か

MITなどで教える4人の研究者(コルメン、ライザーソン、リベスト、スタイン)が書いた、アルゴリズムの標準的な教科書です。著者の頭文字から「CLRS」と呼ばれ、1990年の初版以来、2022年の第4版まで版を重ねてきました。アルゴリズムとは、問題を解く手順のことです。

特徴は、特定のプログラミング言語に頼らない擬似コードで手順を書き、それがなぜ正しく動くのかをループ不変式などで数学的に証明し、必要な時間や空間をO・Ω・Θという記法で厳密に分析する点です。全体は8つの部に分かれ、基礎、ソートと順序統計量、データ構造、動的計画法・貪欲法などの設計技法、高度なデータ構造、グラフアルゴリズム、そして並列アルゴリズムや数論、NP完全性などの特選トピックを扱います。第4版には、安定結婚問題、オンラインアルゴリズム、機械学習の新しい章が加わったと出版社は紹介しています。

書評は、実装よりも数学的な厳密さを重んじる記述で、初心者には数式と証明が多く難しい一方、理論的な裏づけを求める読者には代わりの効きにくい参照先だとしています。日本語版は近代科学社から出ていますが、原著第4版の抄訳で、第1巻と第2巻には原著の第1〜6部に当たる内容が収められています。

中身の柱

書評データベースの全文を読む

概要

マサチューセッツ工科大学(MIT)などで教鞭を執る4名の研究者、トーマス・H・コルメン、チャールズ・E・ライザーソン、ロナルド・L・リベスト、クリフォード・スタインによって書かれた、計算機科学におけるアルゴリズムの標準的教科書。著者名の頭文字から国際的に「CLRS」と呼び習わされている。1990年に初版(著者3名、通称CLR)が刊行されて以来、2001年の第2版でスタインが著者に加わり、2009年の第3版、2022年の第4版へと版を重ねてきた、世界で最も広く採用されているアルゴリズム教科書のひとつである。日本語版は近代科学社から「世界標準MIT教科書」シリーズの一冊として刊行されており、最新の第4版は第1巻・第2巻・総合版という形態で分冊または合本での入手が可能になっている。

本書の最大の特徴は、特定のプログラミング言語に依存しない擬似コードによってアルゴリズムを記述する点、そして個々のアルゴリズムが「なぜ正しく動作するのか」をループ不変式などの手法によって数学的に証明し、「どれだけの時間・空間を要するのか」を漸近的記法(O記法・Ω記法・Θ記法)によって厳密に解析する点にある。単なるアルゴリズム集ではなく、アルゴリズムを設計するための一般的な技法(分割統治法・動的計画法・貪欲法など)を体系立てて提示し、それらの技法がどのような問題群に適用可能かを俯瞰できる構成になっている点も特徴で、大学の学部・大学院向けアルゴリズム講義の教科書として採用されるだけでなく、ソフトウェアエンジニアが計算量やデータ構造の選定について体系的な知識を得るための参照先としても広く用いられている。

本の構成

全体は8つの部から構成される、1000ページを優に超える大部の教科書である。

第I部 基礎では、アルゴリズムとは何か、アルゴリズムの正当性と効率をどう論じるかという導入的な内容から始まり、擬似コードの読み方、関数の増加(漸近的記法)、そして分割統治法という設計技法とその計算量解析に用いるマスター定理を扱う。

第II部 ソートと順序統計量では、確率的解析とランダム化アルゴリズムの考え方を導入したうえで、ヒープソート、クイックソート、比較に基づかない線形時間ソート(計数ソート・基数ソート・バケットソート)、そして中央値をはじめとする順序統計量を線形時間で求めるアルゴリズムを扱う。

第III部 データ構造では、スタック・キュー・連結リストといった初等的データ構造、ハッシュテーブルと衝突解決法、二分探索木、平衡二分探索木である赤黒木、既存のデータ構造に付加情報を持たせて機能を拡張する手法を扱う。

第IV部 高度な設計と解析技法では、動的計画法、貪欲法、そして償却解析(一連の操作全体で計算量を評価する手法)を扱う。

第V部 高度なデータ構造では、多分岐探索木であるB木、併合可能ヒープであるフィボナッチヒープ、整数の集合を扱うファンエンデボアス木、互いに素な集合を管理するデータ構造(Union-Find)を扱う。

第VI部 グラフアルゴリズムでは、幅優先探索・深さ優先探索といった初等的グラフアルゴリズムから、最小全域木(プリム法・クラスカル法)、単一始点最短路(ベルマン-フォード法・ダイクストラ法)、全点対最短路(フロイド-ワーシャル法)、最大フロー問題(フォード-ファルカーソン法)、二部グラフにおけるマッチングまでを扱う。

第VII部 特選のトピックスでは、並列アルゴリズム、行列演算、線形計画法、多項式と高速フーリエ変換、数論的アルゴリズム(最大公約数・モジュラー演算・RSA暗号への応用)、文字列照合、計算幾何学、そしてNP完全性理論と近似アルゴリズムを扱う。巻末の付録には、総和・集合・計数と確率・行列演算といった、本文の証明を追ううえで必要になる数学的基礎がまとめられている。

主要な内容

漸近的記法とマスター定理

アルゴリズムの効率を入力サイズnに対する実行時間の増加の仕方として捉え、定数倍や下位の項を無視して本質的な増加のオーダーだけを比較するための道具としてO記法(上界)・Ω記法(下界)・Θ記法(上下界が一致する場合の正確な評価)を導入する。分割統治法によって得られる漸化式(たとえばT(n) = aT(n/b) + f(n)の形の再帰的な時間計算量)を、個別に解くことなく機械的に評価できるマスター定理を提示し、マージソートの計算量がなぜΘ(n log n)になるのかといった具体例を通じてその使い方を示す。

ソートアルゴリズムの比較

挿入ソート・マージソート・ヒープソート・クイックソートといった比較に基づくソートアルゴリズムについて、それぞれの最悪計算量・平均計算量・実装上の特徴を比較検討する。特にクイックソートについては、最悪計算量がΘ(n^2)になり得る一方で、ランダム化によってピボットの選び方に確率的な操作を加えることで、期待計算量をΘ(n log n)に抑えられることを確率的解析によって示す。また、比較ソートには「決定木モデル」によりΩ(n log n)という下界が存在することを証明したうえで、要素の値についての追加の仮定(整数であることなど)を置けば、比較を用いずに線形時間Θ(n)でソートできる計数ソート・基数ソート・バケットソートが存在することを対比的に示す。

データ構造とその使い分け

配列・連結リストといった初等的な構造から始め、平均計算量O(1)での検索・挿入・削除を実現するハッシュテーブルについて、チェイン法とオープンアドレス法という2つの衝突解決策、および良いハッシュ関数の設計指針を扱う。二分探索木は平均的には効率が良いが、入力の与え方次第で片方に偏った木になり計算量が線形時間まで悪化しうるという弱点を指摘したうえで、各ノードに赤・黒の色を持たせ挿入・削除のたびに回転操作によって木の高さをO(log n)に保つ赤黒木を、その自己平衡の仕組みとともに詳細に解説する。

動的計画法と貪欲法

動的計画法については、部分問題の重複と最適部分構造という2つの性質を備えた問題に対して、計算結果を表に記録しながらボトムアップに解いていく手法として、棒の切り出し問題・行列連鎖積問題・最長共通部分列問題・最適二分探索木問題といった定番の題材を通じて丁寧に解説する。貪欲法については、各段階で局所的に最善に見える選択を繰り返すだけで全体最適解が得られる問題のクラス(マトロイド構造を持つ問題など)を、活動選択問題やハフマン符号化を例に説明し、動的計画法との違い(貪欲法は部分問題を解き直す必要がなく、より高速に解ける代わりに適用できる問題が限られる)を明確にする。

グラフアルゴリズムと最適化問題

幅優先探索・深さ優先探索という2つの基本的なグラフ探索法から始め、閉路を持たない有向グラフのトポロジカルソート、強連結成分の分解へと展開する。最小全域木問題についてはプリム法とクラスカル法という2つの貪欲法に基づくアルゴリズムを、最短路問題については負の重みを許容できるベルマン-フォード法、非負の重みに限定して高速化を図るダイクストラ法、全点対の最短路を動的計画法で一括して求めるフロイド-ワーシャル法を、それぞれ計算量とともに提示する。最大フロー問題では、残余グラフと増加パスという概念に基づくフォード-ファルカーソン法の考え方を出発点に、その特殊化であるエドモンズ-カープ法にも触れ、二部グラフの最大マッチング問題への応用を示す。

NP完全性と近似アルゴリズム

多項式時間で解けることが知られていない問題群(NP困難問題)を扱う枠組みとして、決定問題・判定可能性・多項式時間帰着といった概念を整理したうえで、あるNP困難な問題が別のNP困難な問題に帰着できることを示すことで難しさを立証する手法(SAT問題を起点とした帰着の連鎖)を解説する。P対NP問題という計算機科学最大級の未解決問題の位置づけを説明したうえで、厳密解を多項式時間で求めることが困難な問題に対して、一定の近似精度を保証しつつ現実的な時間で解を得るための近似アルゴリズムの設計手法(頂点被覆問題や巡回セールスマン問題への適用など)を扱う。

具体例

マスター定理の適用例として、二分探索の漸化式T(n) = T(n/2) + O(1)からΘ(log n)を、マージソートの漸化式T(n) = 2T(n/2) + Θ(n)からΘ(n log n)を導く計算過程が具体的に示される。

動的計画法の題材として頻繁に引用される棒の切り出し問題では、長さnの鉄の棒を何本かに切り分けて売るときの最大利益を求める際、切り方の総数が2^(n-1)通りにも及ぶ組合せ爆発を、部分問題の解を表に保存する動的計画法によってO(n^2)まで削減できることが具体的な数値例とともに示される。

グラフアルゴリズムの具体例としては、都市間の道路網を重み付きグラフとしてモデル化し、ダイクストラ法によって単一始点から全頂点への最短距離を求めていく過程が、優先度付きキューを用いた実装とともに段階的にトレースされる。

ハフマン符号化の具体例では、出現頻度の異なる文字集合(例えばテキスト中の各文字の出現回数)に対して、頻度の低い2つのノードを繰り返し併合していく貪欲法によって、可変長の接頭辞符号のうち平均符号長が最小になる符号を構成する手順が、具体的な文字と頻度の組を用いて図解される。

実践への応用

本書で扱われる技法は、実務上のソフトウェア開発において、どのデータ構造を選べば要求される計算量(検索・挿入・削除の速度)を満たせるかを判断する基準として応用される。たとえば大量の要素に対する高速な検索が必要な場面ではハッシュテーブルを、要素間の順序関係を保ったまま動的な挿入・削除が必要な場面では平衡二分探索木を選ぶといった判断は、本書で示される各データ構造の計算量特性の理解に基づいている。

動的計画法や貪欲法といった設計技法は、最適化問題に直面した際に、力任せの全探索ではなく多項式時間で解を得られないかを検討する出発点として応用される。また、ある問題がNP困難であることを帰着によって示す考え方は、実務上「厳密な最適解を求めるのは現実的に困難であり、近似解やヒューリスティックで妥協すべきだ」という判断を裏付ける根拠として使われる。

技術面接、特に大手IT企業のソフトウェアエンジニア採用選考で頻出するアルゴリズム・データ構造に関する設問の多くは、本書で扱われる技法や問題の変形であることが多く、競技プログラミングやコーディング面接対策の基礎教養としても本書の内容が参照される。

位置づけ・評価

1990年の初版刊行から30年以上にわたり版を重ね続けている、計算機科学のアルゴリズム分野における事実上の標準教科書であり、しばしば英語圏では簡潔に"the algorithms bible"と称される。MIT・スタンフォード大学をはじめとする世界各国の大学のアルゴリズム系講義で教科書として採用され続けている実績が、その内容の網羅性と厳密性を裏付けている。

同分野の他の代表的な教科書、たとえばロバート・セジウィックの『アルゴリズムクイックリファレンス』シリーズやスティーブン・スキーナの『アルゴリズム設計マニュアル』などと比較すると、CLRSは実装よりも数学的な厳密性(証明)に重きを置いた記述スタイルを取っており、擬似コードは特定言語の実装よりも抽象度の高いレベルで示される。この性質から、初学者にとっては数式や証明の分量が多く難解に感じられやすい一方、大学院レベルの理論的な裏付けを求める読者やアルゴリズムの正当性を厳密に理解したい読者にとっては、代替の効きにくい参照先として位置づけられている。第4版では並列アルゴリズムなど現代的なトピックへの言及も拡充されており、刊行から30年以上を経てなお計算機科学の基礎科目における中心的な教材であり続けている。