実装が載っていないけど、これはわかりやすい。大学の1,2年向けらしい。情報系って1,2回でこんなことやってたのか。うらやましい。囲み記事のカーペンターズアルゴリズムの解説が良かった、というか読むべし。
データ構造とアルゴリズム- 第1章 アルゴリズムと計算量
- 第2章 リスト構造
- 第3章 ヒープ
- 第4章 ハッシュ法とバケット法
- 第5章 再帰呼出しと分割統治
- 第6章 グラフ探索
- 第7章 最短路問題
- 第8章 動的計画法
- 第9章 縮小法
- 第10章 最大流と割当て問題
- 第11章 ボロノイ図とドロネー図
- 第12章 3次元凸包とドロネー図
- 第13章 平面走査法
- 第14章 問題の難しさの測り方
- 第15章 難問対策
- 第16章 難問を利用した情報保護
以下メモ
- ヒープソートの良さはメモリを効率的に扱えるところ
- 分割統治は問題が比で小さくなるか差で小さくなるかを考えることが重要
- 縮小法の中央値を早く見つける方法
- 空円性
- 最近点対
- 最小全域木に属する全ての辺はドロネー辺
- 平面走査法は次元を下げることにより問題を効率よく扱う
- 分枝限定法
14章から先はちょっと端折っている感があるが、ここらへんが気になるのであれば「メタヒューリスティクスの数理」でも読めばいいのではと。Pythonの実装も載ってるし。
メタヒューリスティクスの数理