アルゴリズムデザイン

突然ですがアルゴリズムとは何でしょうか。

例えば大学生と大学を適切にマッチングする、その効率のよいマッチングの方法
例えば電車を使って、目的地まで最短あるいは最安で行けるルートの発見手法
例えば区間ごとの物流の運搬量が決まっているときに資材はどれだけ運ぶことはできるかを求める手順

アルゴリズムとはこのように現実に遭遇する複雑だがルールは明解な問題を高速に解くための手順だといえます。

では同じ問題を解くアルゴリズム同士の速度の違いは？問題は解けるの？解はそもそも唯一？そういう疑問に解を与える本がこの本、アルゴリズムデザインです。

アルゴリズムデザインの著書の一人であるJ. Kleinbergという方は、HITSのアルゴリズムで有名です。HITSはPageRankに並ぶランキングアルゴリズムとして、Yahooの検索エンジンに入っています。

俺もアルゴリズムの本はそれなりに読んできましたが、この本は抜群に良いです。話も面白い。サクサク読めます。

アルゴリズム本で読んでいて初めて笑いました。まだ第1章しか読んでいないんですが、その1章に面白い問題があります。

結婚問題

• n人と男性とn人の女性がいる
• どの人も異性に対する好意順リストを保持していている
• 好意順リストには同じ性別の人が全員書かれており、全員に対し順位がついている。
• 多重婚や独身は認めない
• この時に満足度が最大化されるような、夫婦のマッチングのリストを探す

いくつか細かいところを省いているので、詳細は本書を参照していただきたい。この問題を解くアルゴリズムとして以下のようなものを考えた時に導き出される話が面白い

• プロポーズは男性から、最も好意的な人から順に行う。
• 女性はプロポーズした人の中から最も好意をもつ人を選ぶ

得られる結論はこちら。

• 男性は最善の正当な女性のペアとなっている
• 女性は最悪の正当な男性のペアとなっている

詳しくは本書をどうぞｗ

アルゴリズムデザイン

第 1 章　はじめに：いくつかの代表的問題
1.1 最初の問題：安定マッチング
1.2 五つの代表的な問題
解答付き演習問題
演習問題
ノートと発展文献

第 2 章　アルゴリズム解析の基礎事項
2.1 計算容易性
2.2 増加の漸近的オーダー
2.3 リストと配列による安定マッチングアルゴリズムの実装
2.4 よく現れる計算時間の復習
2.5 より複雑なデータ構造：優先順位付きキュー
解答付き演習問題
演習問題
ノートと発展文献

第 3 章　グラフ
3.1 基本的定義と応用
3.2 グラフの連結性とグラフ走査
3.3 キューとスタックを用いたグラフ走査
3.4 二部グラフ性の判定：幅優先探索の応用
3.5 有向グラフの連結性
3.6 有向無閉路グラフとトポロジカル順序付け
解答付き演習問題
演習問題
ノートと発展文献

第 4 章　グリーディアルゴリズム
4.1 区間スケジューリング：グリーディアルゴリズムの先進性
4.2 遅延最小化スケジューリング：交換議論
4.3 最適キャッシング：より複雑な交換議論
4.4 グラフにおける最短パス
4.5 最小全点木問題
4.6 Kruskalのアルゴリズムの実装：Union-Findデータ構造
4.7 クラスタリング
4.8 Huffman符号とデータ圧縮
4.9 最小コスト有向木：多フェーズグリーディアルゴリズム
解答付き演習問題
演習問題
ノートと発展文献

第 5 章　分割統治法
5.1 最初の漸化式：マージソートアルゴリズム
5.2 さらなる漸化式
5.3 反転数の数え上げ
5.4 最近点対の発見
5.5 整数の積の計算
5.6 畳込みと高速フーリエ変換
解答付き演習問題
演習問題
ノートと発展文献

第 6 章　動的計画法
6.1 重み付き区間スケジューリング：再帰的手続き
6.2 動的計画法の原理：部分問題上での記憶化と反復
6.3 区分最小二乗法：多肢選択
6.4 部分集合和とナップサック：変数の追加
6.5 RNA二次構造：区間上での動的計画法
6.6 系列アライメント
6.7 分割統治法による線形の領域の系列アライメント
6.8 グラフの最短パス
6.9 最短パスと距離ベクトルプロトコル
6.10 グラフの負閉路
解答付き演習問題
演習問題
ノートと発展文献

第 7 章　ネットワークフロー
7.1 最大フロー問題とFord-Fulkersonアルゴリズム
7.2 ネットワークの最大フローと最小カット
7.3 良い増加パスの選択
7.4 プリフロープッシュ最大フローアルゴリズム
7.5 最初の応用：二部グラフのマッチング問題
7.6 有向グラフと無向グラフにおける素パス
7.7 最大フロー問題の拡張版
7.8 市場調査デザイン
7.9 航空スケジューリング
7.10 画像分割
7.11 プロジェクト選択
7.12 野球ペナントレースの優勝の可能性の消去
7.13 発展：辺にコストの付随するマッチング問題
解答付き演習問題
演習問題
ノートと発展文献

第 8 章　NPと計算困難性
8.1 多項式時間リダクション
8.2 "ガジェット"を用いたリダクション：充足可能性問題
8.3 効率的な証明とNPの定義
8.4 NP-完全問題
8.5 系列化問題
8.6 分割問題
8.7 グラフ彩色問題
8.8 数値問題
8.9 co-NPとNPの非対称性
8.10 計算困難な問題の部分的な分類
解答付き演習問題
演習問題
ノートと発展文献

第 9 章　PSPACE：クラスNPを超える問題のクラス
9.1 クラスPSPACE
9.2 PSPACEに属する困難な問題
9.3 限量化問題とゲームの多項式領域解法
9.4 計画問題の多項式領域解法
9.5 PSPACE-完全性の証明
解答付き演習問題
演習問題
ノートと発展文献

第10章　計算容易性の拡大
10.1 小さい点カバーの発見
10.2 木におけるNP-困難問題の解法
10.3 円弧集合の彩色
10.4 グラフの木分解
10.5 木分解の構成
解答付き演習問題
演習問題
ノートと発展文献

第11章　近似アルゴリズム
11.1 グリーディアルゴリズムと最適解に対する近似解の上界：負荷均等化問題への適用
11.2 センター選択問題
11.3 集合カバー：一般的なグリーディヒューリスティック
11.4 価格付け法：点カバーへの適用
11.5 価格付け法による最大化：素パス問題
11.6 線形計画法とラウンディング：点カバーへの適用
11.7 負荷均等化問題（再考）：より高度な LPの応用
11.8 究極の近似保証：ナップサック問題
解答付き演習問題
演習問題
ノートと発展文献

第12章　局所探索
12.1 最適化問題の景観図
12.2 Metropolisアルゴリズムとシミュレーテッドアニーリング
12.3 Hopfieldニューラルネットワークへの局所探索の応用
12.4 局所探索による最大カットの近似
12.5 近傍関係の選択
12.6 局所探索による分類
12.7 最善反応行動と Nash均衡
解答付き演習問題
演習問題
ノートと発展文献

第13章　乱択アルゴリズム
13.1 第一の応用：競合の解消
13.2 大域的最小カットの発見
13.3 ランダム変数と期待値
13.4 MAX3-SATに対する乱択近似アルゴリズム
13.5 乱択分割統治法：中央値発見とクイックソート
13.6 ハッシング：辞書の乱択実装
13.7 最近点対を求める乱択アプローチ
13.8 乱択キャッシング
13.9 Chernoff限界
13.10 負荷均等化
13.11 パケットルーティング
13.12 背景：いくつかの基本的な確率の定義
解答付き演習問題
演習問題
ノートと発展文献

第14章　永遠に動作するアルゴリズム

http://www.kyoritsu-pub.co.jp/shinkan/shin0807_03.html