読書: アルゴリズム設計マニュアル 上

ちゃんと勉強して強化するためにまず、S.S.スキーナのアルゴリズム設計マニュアル 上を読んだ。 数学的な解析に立ち入るのを少なめにしたアルゴリズムの入門書だった。

計算量(時間,空間)の話や正当性の証明の話から始まり、NP困難とNP完全の違いやNP困難を証明する話までたくさん扱っている。 またデータ構造やソート,グラフの重要なアルゴリズムの説明や応用や適応の具体例を通してモデル化や改善の流れを色々と追えるように書かれている。

わかりやすいと思うけど、まだ理解や実践がたりないので思うまでしか言えない。実践を通してから読み返したい。

NP困難の証明に関する演習は適度な難易度で楽しかった。またNP完全な問題でも実務だと戦わないとならないとして整理してたのはよかった。

最後に設計に向けて、考えを進めるための質問集を載せていた。アルゴリズムの設計を問題を解く行為として扱っていてポリヤの「いかにして問題を解くか」と似た感じを受けてたら言及があった。あと論文や資料への参照がとても多くて良い。

ここからは大雑把な要約を書く。読んで引っかかった事とか挟んでしまうかも知れないけどできるだけ入れないつもり。

全体の流れ

1章 アルゴリズム設計への導入

アルゴリズムと問題の定義から入って、正当性の証明の方法や反例を探すコツなどを扱う。最後にモデル化を説明していた。

アルゴリズムは問題を解き、問題は入力集合と出力集合で定義されると説明していた。例えばソートでは下のようになる。

問題	ソート
入力	n個のキーの列 a_1, …, a_n
出力	入力列の順列で a_1'<= a_2' <= … <=a_n' となるもの

モデル化は応用上の問題をアルゴリズムで扱える厳密な表現に形式化することを指す。 アルゴリズムの文献を活用するには大抵のアルゴリズムの設計で利用されている抽象構造で表現することが必要になる。 列挙されていたのは

• 順列
• 部分集合
• 木
• グラフ
• 点
• 多角形
• 文字列

正当性の証明については、擬似コードで表現してアルゴリズム問題を定義して再帰などで正当性を証明するって感じが多いと書いてた。判例の説明は、アプローチでいくつか挙げてた。

• 小さく考える
• 網羅する
• 弱点を考える
• 同点に持ち込む
• 極端な例を考える

2章 アルゴリズム解析

RAM(Random Access Machine)モデルで計算量を表現する話をしていた。

最悪・最良・平均の計算量や関連したビッグオー記法の計算や上界・下界や支配関係についても説明している。 ビックオー記法で扱われる漸近挙動について計算方法の他に、アルゴリズムのどのような状況が log(n),n!,n^2 などの関数として現れるかのパターンも紹介している。

3章 データ構造

基本的なデータ構造の分類や紹介をしていた。

まず最初に連続データ構造と連結データ構造を紹介する。

連続データ構造 配列など、ひとまとまりの連続したメモリ理領域で構成される。配列のほか、行列、ヒープ、ハッシュ表などがある。

連結データ構造 メモリ領域とポインタで構成される。リストや木、グラフの隣接リストが含まれる。

そのあとでコンテナ(スタック、キュー)、辞書、2分探索機、優先順位付きキュー、ハッシュを説明していた。 データ構造の操作と実装による時間計算量の比較をやる。

その後、いくつかの特定目的のデータ構造について紹介していた。

4章 ソート

ソートを通して他の多くの問題に関わるアイディアやアプローチやデータ構造の説明をしていた。 ソートの応用として 探索, 最近接ペア, 要素の一意性, 度数分布, 選択, 凸包を紹介している。 ソートを通して下の大きく4つについて紹介している。

• ヒープソートを通してヒープについて
• 挿入ソートを使って逐次挿入と平衡二分木
• マージソートで分割統治法
• クイックソートでランダム化アルゴリズム

また最後に分配ソート(バケットソート)を紹介していて、これは最悪での性能が酷い代わりにデータの分布が均一な場合によい性能を出すらしい。このようにヒューリスティックや対象の特徴を利用して平均の性能が良くなるアルゴリズムがあると説明していた。 またこれが、ハッシュ表やkd木など実際的なデータ構造の基礎になっているとも書かれていた。

5章 グラフ横断

グラフの特徴とか種類をいくつか列挙していた。 グラフを表現するデータ構造として隣接行列、隣接リストを比較していた。

またグラフ横断で、幅優先探索(BFS)と深さ優先探索(DFS)を比較しそれぞれの応用を挙げていた。

横断の応用として向こうグラフの連結成分の探索を挙げていた。 幅優先探索の応用で2彩色グラフの判定を出していた。

無向グラフの深さ優先探索の応用として閉路検出と関節点の検出を挙げていた。 (DFSを使って関節点を求めるアルゴリズムの理解に手間取った)

有向グラフの深さ優先探索の応用として位相的ソートと強連結成分の検出を挙げていた。

6章 重み付きグラフのアルゴリズム

重み付きグラフの問題とアルゴリズムと応用や変種を説明していた。

最小スパニング木へのプリムのアルゴリズムとクラスカルのアルゴリズムを紹介していた。 クラスカルのアルゴリズムでの部分木の連結性の検証にunion-find構造を紹介してる。

最小スパニング木の変種として最大スパニング木, 最小積スパニング木, 最小ボトルネックスパニング木, シュタイナー木, 低次数スパニング木などを説明してた。

最短経路についてダイクストラのアルゴリズムを説明していた。応用として全ペア最短経路問題と推移的閉包に触れていた。 全ペア最短経路問題についてはフロイド-ワーシャル(Floyd-Warshall)法を説明していた。

重み付きグラフをネットワークフローとして捉えて最大流量と経路の再構築について説明していた。 応用として2部マッチングを挙げていた。

7章 組み合わせ探索とヒューリスティックな方法

しらみつぶしに解候補を列挙する方法としてバックトラック法を説明している。 部分集合, 順列, グラフ内の単純経路を最初に説明していた。実践的な例では数独とチェスボード被覆を紹介している。

バックトラックでは解候補の作成順序をどうするかと枝刈りを効率的に行う方法などが大事になる。

ヒューリスティックな探索法ではランダムサンプリング, 局所探索, シミュレーテッドアニーリングが紹介されていた。他にも遺伝的プログラミング,ニューラルネット,蟻コロニー最適化が名前だけ紹介されていた。

ランダムサンプリングが向いているのは、受け入れ可能な解が高い割合で存在するときで解空間に何らの一貫性もないとき。

局所探索が向いているのは、解空間に高度に一貫性があり、逐次増加的な評価の計算コストが大域的評価よりずっと少なくて済むとき。

シミュレーテッドアニーリングはここにあるヒューリスティックではだいたい何でも使える。シミュレーテッドアニーリングに向いたモデルを作るを最初にやるのが大事。(物理出身としては、とても馴染みがあり懐かしいなぁって思った)

シミュレーテッドアニーリングの応用として最大カット, 独立集合, 回路基板の配置などが紹介されていた。 並列アルゴリズムに批判的だった。まず先に普通にアルゴリズムを改善せよとのこと。まぁ、そうですねって思った。

8章 動的計画法

再帰で表現されるアルゴリズムで異なるパラメータによる計算結果が何度も利用されパラメータ値を記憶するメモリ領域が小さい時に再帰呼び出しにキャッシュを挟むと役に立つ。これはほぼ動的計画法だとのこと。 よくメモ化とか呼んでいる気がする。

動的計画法は再帰から反復に変換して計算順序を工夫してメモリ消費を削減したものを指していた。

具体的な適用対象としてフィボナッチ数, 二項係数, 編集距離, 線形分割, 文脈自由文法の構文解析, 最小重み三角分割が載せられていた。

また編集距離の計算から編集操作の再構築などはテーブルから逆向きに走ることで計算することが示されていた。

編集距離の応用で部分文字列マッチング, 最長共通部分列, 最大単調部分列などを簡単にできることを示していた。

最後に動的計画法の正しさと効率について議論していた。

最適性の原理に従う問題であれば正しく適用できる。これは分割した問題の統合として解決しようとしても、統合方法が分割した問題の結果で定められない場合は使えないことを意味している。 グラフ内の単純経路を求める場合は途中経路を全て把握しないといけないため上手く扱えない。

動的計画の計算時間は保持しなければならない部分解の個数と各部分を計算する時間で構成され、最初の状態空間のサイズが問題になる。 扱う対象のオブジェクトに順序が付けられないと中間状態が指数関数的に増えてしまう場合が多く扱いにくい。

(正当性で挙げられた「経路をしないと正しく扱えいない」というケースも経路を元に分割すれば正しく書き下せそうだけど効率は悪すぎるって話に繋がるかなと思った)

9章 手に負えない問題と近似アルゴリズム

問題のNP困難を証明する方法やNP完全とNP困難の違いなどを説明している。 3-SATから整数計画(IP)に帰着させてIPの困難性を証明したりなどの例がたくさん扱われている。 困難性証明のコツも紹介されていた。

• 目標の問題はできるだけ難しいものを選ぶ
• もとになる問題はできるだけ単純にする
• もとの問題の選び方を間違わない
• 行き詰まったらアルゴリズムを探すか帰着を試みるか交互に行う

もとの問題の選び方を間違えないこと について少し書いておく。 スキーナは主に4つの問題に帰着させることが多いらしい。

• 3-SAT問題: 下の3つで困ったら選ぶ
• 整数分割問題: 目標の問題の困難性が大きな数に依ると思われる時に選ぶ
• 頂点被覆問題: グラフ問題で、困難性が選択からくると想像される時に選ぶ
• ハミルトン経路問題: グラフ問題で、困難性が順序からくると想像される時に選ぶ

最後にNP完全問題への対処の節が準備されていた。

NP完全でも、まだ最悪の場合に効率的に解けるアルゴリズムが存在しないとわかっただけなので、実務に向けてどうにかする手立ては残っている。

選択肢として大きく、平均の場合に速いアルゴリズム, ヒューリスティック, 近似アルゴリズムの3つを挙げている。

平均に速いアルゴリズムとして賢い枝刈りを伴うバックトラックなどとしていた。 ヒューリスティックとしてシミュレーテッドアニーリング, グリーディ法などを挙げている。 近似アルゴリズムは、問題に特化したヒューリスティックで精度保証付きのものを指す。

本書では頂点被覆,ユークリッド巡回セールスマン問題,最大非閉路部分グラフ,集合被覆問題についての近似アルゴリズムを紹介していた。

10章 どのようにアルゴリズムを設計するか

最後にアルゴリズム設計をする時に設計を突き進めるための質問集が載っていた。 著者もポーヤの「いかにして問題を解くか」に言及していた。読み返したいと思った。