Geoge T. Heineman. Gary Pollice, Stanley Selkow「アルゴリズム クイックリファレンス 第２版」オライリージャパン 黒川利明,黒川洋訳

探索木によっては、盤面状態の数が大変多くなるので、深さ優先探索は、最大探索深さが前もって定まっているような場合にのみ実用的となる。
　　――7.7　深さ優先探索

幅優先探索は、もし経路が存在するなら、目標状態への最短経路を見つけることが保証されている。
　　――7.8　幅優先探索

人口知能(AI)分野の初期の開拓者の多くの特徴は、いまだ解がわからない問題を解こうとしていることであった。問題を解く一般的方法は、大規模なグラフの探索問題に変換する事であった。
　　――12.5　探索を構築せよ

【どんな本？】

　コンピュータで問題を解くには、アルゴリズムが欠かせない。そしていつの時代も、より速く問題を解く需要は尽きない。往々にして単純な解き方だと、問題の規模の二乗に比例する時間がかかる。CPUもバスも速度は上がったが、最近はリアルタイム性の要求も厳しくなった。弾幕ゲームで弾数の二乗の演算時間を費やすわけにはいかない。

　本書では基本となる全順序集合の整列と探索に始まり、地図などの経路探索や完全情報ゲームの最善手の探索、二次元ゲームの当たり判定などに便利な空間木構造など、現代のプログラミングで必要となるアルゴリズムとデータ構造を紹介する。

【いつ出たの？分量は？読みやすい？】

　原書は ALGOTITHMSS : In a Nutchell Second Edition, by Geoge T. Heineman. Gary Pollice, Stanley Selkow, 2016。日本語版は2016年12月22日初版第１刷発行。単行本ソフトカバー横一段組み約415頁。8.5ポイント37字×31行×415頁＝約476,005字、400字詰め原稿用紙で約1,191枚。文庫なら厚めの上下巻ぐらいの分量。

　文章はやや硬い。「任意の点ｐにおいて」など、数学っぽい表現も容赦なく出てくるので、そこは覚悟しよう。サンプル・プログラムも多数収録している。使っているのは c, c++, Java, Python。c++ か Java か Python がわかれば、たいがい読めるだろう。

【構成は？】

　各章はゆるく独立しているが、できるだけ頭から読んだ方がいい。

• 第２版日本語版へ寄せて
• 第２版まえがき
• １章　アルゴリズムで考える
  • 1.1　問題を理解する
  • 1.2　素朴解
  • 1.3　賢い方式
    • 1.3.1　貪欲法
    • 1.3.2　分割統治法
    • 1.3.3　並列法
    • 1.3.4　近似法
    • 1.3.5　一般化
  • 1.4　まとめ
  • 1.5　参考文献

• ２章　アルゴリズムの数学
  • 2.1　問題インスタンスのサイズ
  • 2.2　関数の成長率
  • 2.3　裁量、平均、最悪時の分析
    • 2.3.1　最悪時
    • 2.3.2　平均時
    • 2.3.3　最悪時
    • 2.3.4　下限と上限
  • 2.4　性能分類
    • 2.4.1　定数的振る舞い
    • 2.4.2　対数的振る舞い
    • 2.4.3　ｄ＜１に対する下位線形O(n^d)の振る舞い
    • 2.4.4　線形性質
    • 2.4.5　線形対数(n log n)の性能
    • 2.4.6　二乗の性質
    • 2.4.7　あまり明白でない性質を示す計算
    • 2.4.8　指数性能
    • 2.4.9　漸近的成長のまとめ
  • 2.5　ベンチマーク演算
  • 2.6　参考文献

• ３章　アルゴリズムの構成要素
  • 3.1　アルゴリズムテンプレートの形式
  • 3.2　疑似コードのテンプレート形式
  • 3.3　評価実験の形式
  • 3.4　浮動小数点計算
    • 3.4.1　性能
    • 3.4.2　丸め誤差
    • 3.4.3　浮動小数点数値の比較
    • 3.4.4　特殊な値
  • 3.5　アルゴリズム例
    • 3.5.1　名前と概要
    • 3.5.2　入出力
    • 3.5.3　文脈
    • 3.5.4　解
    • 3.5.5　分析
  • 3.6　一般的なアプローチ
    • 3.6.1　貪欲法
    • 3.6.2　分割統治
    • 3.6.3　動的計画法
  • 3.7　参考文献

• ４章　整列アルゴリズム
  • 4.0.1　用語
  • 4.0.2　表現
  • 4.0.3　比較可能な要素
  • 4.0.4　安定整列
  • 4.0.5　整列アルゴリズムの選択基準
  • 4.1　転置ソート
    • 4.1.1　挿入ソート
    • 4.1.2　文脈
    • 4.1.3　解
    • 4.1.4　分析
  • 4.2　選択ソート
  • 4.3　ヒープソート
    • 4.3.1　文脈
    • 4.3.2　解
    • 4.3.3　分析
    • 4.3.4　変形
  • 4.4　分割ベースのソート
    • 4.4.1　文脈
    • 4.4.2　解
    • 4.4.3　分析
    • 4.4.4　変形
  • 4.5　比較なしの整列
  • 4.6　バケツソート
    • 4.6.1　解
    • 4.6.2　分析
    • 4.6.3　変形
  • 4.7　外部ストレージのある整列
    • 4.7.1　マージソート
    • 4.7.2　入出力
    • 4.7.3　解
    • 4.7.4　分析
    • 4.7.5　変形
  • 4.8　整列ベンチマーク結果
  • 4.9　分析技法
  • 4.10　参考文献

• ５章　探索
  • 5.1　逐次探索
    • 5.1.1　入出力
    • 5.1.2　文脈
    • 5.1.3　解
    • 5.1.4　分析
  • 5.2　二分探索
    • 5.2.1　入出力
    • 5.2.2　文脈
    • 5.2.3　解
    • 5.2.4　分析
    • 5.2.5　変形
  • 5.3　ハッシュに基づいた探索
    • 5.3.1　入出力
    • 5.3.2　文脈
    • 5.3.3　解
    • 5.3.4　分析
    • 5.3.5　変形
  • 5.4　ブルームフィルタ
    • 5.4.1　入出力
    • 5.4.2　文脈
    • 5.4.3　解
    • 5.4.4　分析
  • 5.5　二分探索木
    • 5.5.1　入出力
    • 5.5.2　文脈
    • 5.5.3　解
    • 5.5.4　分析
    • 5.5.5　変形
  • 5.6　参考文献

• ６章　グラフアルゴリズム
  • 6.1　グラフ
    • 6.1.1　データ構造の設計
  • 6.2　深さ優先探索
    • 6.2.1　入出力
    • 6.2.2　文脈
    • 6.2.3　解
    • 6.2.4　分析
    • 6.2.5　変形
  • 6.3　幅優先探索
    • 6.3.1　入出力
    • 6.3.2　文脈
    • 6.3.3　解
    • 6.3.4　分析
  • 6.4　単一始点最短経路
    • 6.4.1　入出力
    • 6.4.2　解
    • 6.4.3　分析
  • 6.5　密グラフ用ダイクストラ法
    • 6.5.1　変形
  • 6.6　単一始点最短経路選択肢の比較
    • 6.6.1　ベンチマークデータ
    • 6.6.2　密グラフ
    • 6.6.3　疎グラフ
  • 6.7　全対最短経路
    • 6.7.1　入出力
    • 6.7.2　解
    • 6.7.3　分析
  • 6.8　最小被覆木アルゴリズム
    • 6.8.1　入出力
    • 6.8.2　解
    • 6.8.3　分析
    • 6.8.4　変形
  • 6.9　グラフについての考察
    • 6.9.1　ストレージの問題
    • 6.9.2　グラフ分析
  • 6.10　参考文献

• ７章　AIにおける経路探索
  • 7.1　ゲーム木
    • 7.1.1　静的評価関数
  • 7.2　経路探索の概念
    • 7.2.1　状態の表現
    • 7.2.2　可能な手の計算
    • 7.2.3　拡張深さの限度
  • 7.3　ミニマックス
    • 7.3.1　入出力
    • 7.3.2　文脈
    • 7.3.3　解
    • 7.3.4　分析
    • 7.3.5　
  • 7.4　ネグマックス
    • 7.4.1　解
    • 7.4.2　分析
  • 7.5　アルファベータ法
    • 7.5.1　解
    • 7.5.2　分析
  • 7.6　探索木
    • 7.6.1　経路長のヒューリスティック関数
  • 7.7　深さ優先探索
    • 7.7.1　入出力
    • 7.7.2　文脈
    • 7.7.3　解
    • 7.7.4　分析
  • 7.8　幅優先探索
    • 7.8.1　入出力
    • 7.8.2　文脈
    • 7.8.3　解
    • 7.8.4　分析
  • 7.9　A*探索
    • 7.9.1　入出力
    • 7.9.2　文脈
    • 7.9.3　解
    • 7.9.4　分析
    • 7.9.5　変形
  • 7.10　探索木アルゴリズムの比較
  • 7.11　参考文献

• ８章　ネットワークフローアルゴリズム
  • 8.1　ネットワークフロー
  • 8.2　最大フロー
    • 8.2.1　入出力
    • 8.2.2　解
    • 8.2.3　分析
    • 8.2.4　最適化
    • 8.2.5　関連アルゴリズム
  • 8.3　二部マッチング
    • 8.3.1　入出力
    • 8.3.2　解
    • 8.3.3　分析
  • 8.4　増加道についての考察
  • 8.5　最小コストフロー
  • 8.6　積み替え
    • 8.6.1　解
  • 8.7　輸送
    • 8.7.1　解
  • 8.8　割り当て
    • 8.8.1　解
  • 8.9　線形計画法
  • 8.10　参考文献

• ９章　計算幾何学
  • 9.1　問題の分析
    • 9.1.1　入力データ
    • 9.1.2　計算
    • 9.1.3　タスクの性質
    • 9.1.4　仮定
  • 9.2　凸包
  • 9.3　凸包検査法
    • 9.3.1　入出力
    • 9.3.2　文脈
    • 9.3.3　解
    • 9.3.4　分析
    • 9.3.5　変形
  • 9.4　線分交差を計算する
  • 9.5　線分走査法
    • 9.5.1　入出力
    • 9.5.2　文脈
    • 9.5.3　解
    • 9.5.4　分析
    • 9.5.5　変形
  • 9.6　ボロノイ図
    • 9.6.1　入出力
    • 9.6.2　解
    • 9.6.3　分析
  • 9.7　参考文献

• 10章　空間木構造
  • 10.1　最近傍クエリ
  • 10.2　範囲クエリ
  • 10.3　交差クエリ
  • 10.4　空間木構造
    • 10.4.1　k-d木
    • 10.4.2　四分木
    • 10.4.3　R木
  • 10.5　最近傍法
    • 10.5.1　入出力
    • 10.5.2　文脈
    • 10.5.3　解
    • 10.5.4　分析
    • 10.5.5　変形
  • 10.6　範囲クエリ
    • 10.6.1　入出力
    • 10.6.2　文脈
    • 10.6.3　解
    • 10.6.4　分析
  • 10.7　四文木
    • 10.7.1　入出力
    • 10.7.2　解
    • 10.7.3　分析
    • 10.7.4　変形
  • 10.8　R木
    • 10.8.1　入出力
    • 10.8.2　文脈
    • 10.8.3　解
    • 10.8.4　分析
  • 10.9　参考文献

• 11章　新たな分類のアルゴリズム
  • 11.1　方式の種類
  • 11.2　近似アルゴリズム
    • 11.2.1　入出力
    • 11.2.2　文脈
    • 11.2.3　解
    • 11.2.3　分析
  • 11.3　並列アルゴリズム
  • 11.4　確率的アルゴリズム
    • 11.4.1　集合のサイズを推定する
    • 11.4.2　探索木のサイズを推定する
  • 11.5　参考文献

• 12章　結び:アルゴリズムの諸原則
  • 12.1　汝のデータを知れ
  • 12.2　問題を小さく分割せよ
  • 12.3　正しいデータ構造を選べ
  • 12.4　空間と時間のトレードオフを使え
  • 12.5　探索を構築せよ
  • 12.6　問題を別の問題に帰着させよ
  • 12.7　アルゴリズムを書くのは難しい、アルゴリズムをテストするのはさらに難しい
  • 12.8　可能なら近似解を受け入れよ
  • 12.9　性能を上げるために並列性を加えよ

• 付録A　ベンチマーク
  • A.1　統計の基礎
  • A.2　例
    • A.2.1　Javaベンチマーク
    • A.2.2　Linuxベンチマーク
    • A.2.3　Pythonベンチマーク
  • A.3　報告
  • A.4　精度
• 訳者あとがき／索引

【感想は？】

　この手の本の古典としては Niklaus Wirth の「アルゴリズム＋データ構造＝プログラム」がある。プログラミングの基礎から始めて、Pascal のコンパイラを作ってゆく。その過程で、リストやバランス木などのデータ構造や、再起呼び出しなどの手口を身に着ける本だ。

　優れた本だが、さすがに今の時代に Pascal は厳しい。それにリストや連想配列(ハッシュ, 辞書)なら、イマドキのプログラミング言語は処理系やライブラリが備えている。

　ということで、そういった基礎的な部分は最小限にして、現代のプログラマ、特にリアルタイム性が必要なゲームの製作で求められる、二次元空間の探索などを加えたのが本書だ。

　とはいえ、同じ整列や探索でも、現代のプログラマ、特に Web サービスで扱うデータ量は桁違いに多い。と同時に、使えるメモリ量もキロバイト単位からギガバイト単位に変わった。またオンライン業務では、データの追加・変更・削除が頻繁に起こる。となると、探索の効率とデータの追加・削除のコストのバランスも変わってくる。

　そんなわけで、一応は昔ながらのバッチ処理に向くマージソートも出ているが、むしろハッシュを使ったブルームフィルタ(→Wikipedia)の方が実用的な場面が多いかも。

　などと５章までは「処理系のハッシュ使えばいいじゃん」で済む問題が多いが、６章からは「どんなデータ構造で表すか」がキモとなる問題が増えてくる。例えば、６章の最初に出てくる問題は、二次元の迷路の探索だ。あなた、迷路をどんなデータ構造で表します？　表せれば、とりあえず問題は解けます…処理時間はともかく。

　本書では、節と辺からなるグラフとして扱ってる。分岐点と行き止まりを節、直接に行き来できる節同志を辺でつなぐ。これで問題は半分解けたようなもん。ただ、単純に深さ優先探索すると、節の数が増えるに従い演算時間が爆発するので、何かと工夫が必要だったり。

　「７章　AIにおける経路探索」は、ちょっと誤解を招くかも。というのも、ここで言うAIは、今の流行りの強化学習じゃない。三目並べなど完全情報ゲームでの最善手を探るアルゴリズムを示すもの。昔ならLISPやPrologが得意とした問題分野ですね。今はチェスも強化学習になっちゃってるけど。

　これが「９章　計算幾何学」以降に入ると、二次元ゲームを作る際に突き当たる問題が山盛り。「与えられた点から最も近い点を見つける」「点の集合をすべて含む最小の凸多角形を見つける」「任意の多角形の集合の交差を全部見つける」とか、ありがちですね。ただし、この辺になると、放物線の幾何学とかの素養が必要だけど。ええ、私は読み飛ばしました。

　次の「10章　空間木構造」も、ゲーム屋必須の章。交差クエリとかは、モロに当たり判定だったり。

　オブジェクトが少ないうちは力任せ、すなわち全オブジェクト同士で交差判定すりゃいいけど、撃ちまくりの弾幕ゲームでそんな事やったらキリがないい＝オブジェクト数の二乗で演算時間が増えていく。リアルタイム性が求められるゲームでは、1/60秒未満で処理を終える必要があるし。

　そこで演算時間を節約するにはどうすれば、という話。

　ここの基本は、「いかに無駄な判定をせずに済ますか」。つまり、どう考えても当たらない要素同士は、なるたけ計算せずに済ませましょう、ってこと。ただし、そのためには、ｎ次元空間上にバラけている点の集合を、単なる配列やリストにするのではなく、k-d木や四分木など、何らかの秩序だったデータ構造にする必要があるのだ。

　この辺を読んでると、グレッグ・イーガンの描く派手で自由度の高いVR世界も、その末端では忙しくリストから要素を出し入れして最適化してるのかな、とか考えちゃったり。でないと、すぐに演算量が爆発しちゃうから。問題に対し、必要な演算量を見積もり、適したデータ構造とアルゴリズムを選ぶマシンなんて、本当に作れるんだろうか？

　と、序盤では古典的なネタで肩慣らししつつ、中盤以降は二次元以上の空間を扱い、より現代的な問題にアプローチしてゆく、今世紀に相応しいアルゴリズムとデータ構造の本だった。その分、歯ごたえも充分にあるので、覚悟して挑もう。

【関連記事】

• 2019.6.7 Q.Ethan McCallum「バッドデータ ハンドブック データにまつわる問題への19の処方箋」オライリージャパン 磯蘭水監訳 笹井崇司訳
• 2016.07.08 Diomidis Spinellis, Georgios Gousios編「ビューティフルアーキテクチャ」オライリージャパン 久野禎子・久野靖訳 1
• 2016.04.25 Raffaele Cecco「JavaScriptグラフィックス ゲーム・スマートフォン・ウェブで使う最新テクニック」オライリージャパン 相川愛三訳 1
• 2014.11.21 Andy Oram, Greg Wilson編 Brian Kerninghan, Jon Bentry, まつもとゆきひろ他著「ビューティフルコード」オライリージャパン 久野禎子,久野靖訳 1
• 2013.06.24 David Flanagan「JavaScript 第六版」オライリージャパン 村上列訳
• 2010.11.14 Eric.A.Meyer「CSS完全ガイド第2版 CSS2&CSS2.1対応」オライリージャパン 株式会社クイープ訳
• 書評一覧：科学/技術