乱択アルゴリズム

アルゴリズムの振舞いを乱数に依存させる乱択アルゴリズムが流用されており、単にアルゴリズムといえば、今日では乱択アルゴリズムを含んでいると考えるのが普通である。しかし、実用アルゴリズムの世界では、乱択アルゴリズムの効果と価値が十分に認識されているとは言い難い。この状況を改善するには、アルゴリズム教育において乱択アルゴリズムに正当な地位を与える必要があろう。全体として、さまざまな分野の乱択アルゴリズムを網羅することは考えず、少数の乱択アルゴリズムを例として基本的な考え方のパターンを掘り下げる方針を採った。本書のレベルはやや高度であり、大学院あるいは学部の高学年でアルゴリズム理論とその基礎になる数学的素養を既に身につけた人、あるいはこの分野でこれから研究を始めようとする研究者を主な対象としている。
第 1 章 導入
1.1 乱択アルゴリズムの基本的な考え方
1.2 乱数の効用
1.3 乱択アルゴリズムの分類
1.4 数学とアルゴリズムの基礎
1.5 確率的解析のための準備

第 2 章 平均化効果を利用する乱択アルゴリズム
2.1 クィックソート
2.2 乱択逐次構成法: 2 次元の凸包
2.3 低次元の線形計画法
2.4 LP 型問題

第 3 章 標本乱択を利用するアルゴリズム
3.1 部分集合の大きさ
3.2 κ 番目の値
3.3 ε標本とε網
3.4 最小全域木問題の線形時間アルゴリズム
3.5 標本乱択を利用した近似アルゴリズム: 密なグラフの最大カット

第 4 章 くじ引き型のアルゴリズム
4.1 素数性判定の乱択アルゴリズム
4.2 関数の同一性の検証
4.3 成功確率の増幅

第 5 章 その他の種類の乱択アルゴリズム
5.1 制約のランダムな充足を図るアルゴリズム
5.2 乱歩を利用するアルゴリズム

第 6 章 マルコフ連鎖を用いた標本乱択
6.1 計数問題の近似アルゴリズム: 標本乱択の応用
6.2 マルコフ連鎖の基礎
6.3 標本乱択のためのマルコフ連鎖の設計
6.4 定常分布への収束の速さ
6.5 厳密な標本乱択

第 7 章 脱乱択化
7.1 条件付き確率の方法
7.2 確率空間の縮小

『乱択アルゴリズム』 (玉木 久夫 著、共立出版、2008 年 8 月刊) は、アルゴリズムの振る舞いを乱数に依存させる乱択アルゴリズムを、少数の代表的な例を通して考え方のパターンごとに掘り下げる専門書です。杉原 厚吉、室田 一雄、山下 雅史、渡辺 治 の 4 名が編者を務めるアルゴリズム・サイエンスシリーズの数理技法編 4 にあたります。版元の紹介文は本書のレベルをやや高度とし、大学院あるいは学部の高学年でアルゴリズム理論とその基礎になる数学的素養をすでに身につけた人と、この分野で研究を始めようとする研究者を主な対象に挙げています。

平均化効果から脱乱択化まで、目次に並ぶ 7 章

版元が登録する目次は、第 1 章から第 7 章までの 7 章です。第 1 章「導入」は、乱択アルゴリズムの基本的な考え方、乱数の効用、乱択アルゴリズムの分類に続き、数学とアルゴリズムの基礎と確率的解析のための準備を置きます。第 2 章「平均化効果を利用する乱択アルゴリズム」は、ソートアルゴリズム の代表であるクィックソートを皮切りに、2 次元の凸包を題材にした乱択逐次構成法、低次元の線形計画法、LP 型問題へ進みます。第 3 章「標本乱択を利用するアルゴリズム」は部分集合の大きさ、κ 番目の値、ε 標本と ε 網、最小全域木問題の線形時間アルゴリズム、密なグラフの最大カットを対象にした近似アルゴリズムを扱います。第 4 章「くじ引き型のアルゴリズム」は素数性判定、関数の同一性の検証、成功確率の増幅、第 5 章「その他の種類の乱択アルゴリズム」は制約のランダムな充足を図るアルゴリズムと乱歩を利用するアルゴリズムです。第 6 章「マルコフ連鎖を用いた標本乱択」は計数問題の近似アルゴリズムを入口に、マルコフ連鎖の基礎、標本乱択のための連鎖の設計、定常分布への収束の速さ、厳密な標本乱択を取り上げ、第 7 章「脱乱択化」は条件付き確率の方法と確率空間の縮小を扱います。

章題の多くが、何を解くかではなく乱数をどう効かせるかで立てられており、さまざまな分野の乱択アルゴリズムを網羅するのではなく基本的な考え方のパターンを掘り下げるという、版元の紹介文が示す方針がそのまま章立てに表れていると読めます。

平均化、標本、くじ引き、乱数が効く仕組み

乱択アルゴリズムの強みは、どれほど意地の悪い入力が来ても、アルゴリズム自身が引く乱数について平均をとれば良い振る舞いを保証できる点にあります。決定的なクィックソートは特定の並びの入力で計算時間が入力の大きさの 2 乗に膨らみますが、ピボットを乱数で選べば、どの入力に対しても期待計算時間を n log n の程度に抑えられます。大きな入力の一部だけを無作為に抜き出して全体の性質を推し量る標本の発想は、グラフアルゴリズム の古典的な問題である最小全域木を線形時間で解くような、決定的な手法では届きにくい効率につながります。素数性判定のように、一定の確率で誤り得る判定を独立に繰り返して誤る確率を指数的に小さくする考え方も、乱択ならではの道具です。

その一方で、乱択を持ち込めば何でも速くなるわけではありません。期待値として速いのか高い確率で速いのか、答えが常に正しいのか一定の確率で誤るのかを区別し、それぞれを確率論の道具で評価する必要があり、ここが乱択アルゴリズムを学ぶうえでつまずきやすい部分です。第 7 章の脱乱択化は、乱択で得た手法から乱数を取り除いて決定的なアルゴリズムを導く方向の議論で、乱数がそもそも本質的に必要なのかという理論上の問いにもつながっています。

研究の入口に立つ人向けの水準と、前提になる数学的素養

版元自身がやや高度と位置づけているとおり、本書はアルゴリズムの入門書ではありません。第 1 章に確率的解析のための準備の節が置かれているとはいえ、想定されているのはアルゴリズム理論とその基礎になる数学的素養をすでに身につけた読者です。代表的なアルゴリズムとデータ構造をまず幅広く知りたい段階なら、教科書型の本を先に一冊通すほうが近道で、その選び方は アルゴリズム本の選び方 が参考になります。また紹介文が述べるとおり分野ごとの網羅は狙っていないため、実務で使う個別の確率的な手法を辞書のように引く用途にも合いません。

裏返せば、乱択アルゴリズムを使う側から、自分で設計し解析する側へ移りたい人にとって、本書は手元に置く価値のある一冊です。理論計算機科学の研究室に進む学生や、乱択の手法を論文で読む機会が増えた研究者が、平均化、標本、くじ引き、マルコフ連鎖、脱乱択化という乱数の効かせ方の型を、少数の例を深く追うことで日本語で整理できます。