draft:アルゴリズム設計マニュアル

アルゴリズムとデータ構造のとてもよい教科書。 上下巻あるが、上が授業に使うような教科書で下はアルゴリズム図鑑になっている。 上だけ買ってもいいと思う。

よいところ - 抽象アルゴリズムを実問題に適用することの重要性が繰り返し意識づけられる。 - 例えばソートがなぜそんなに重要なのか等、理由がしっかり述べられている。無味乾燥でない。 - 重要なアルゴリズムについて、実際に動く C のコードがたくさん載っている。 - 演習問題に「インタビュー問題」が含まれており、読者がIT業界の技術面接を受けることも意識している感じ。

読み返すついでにメモを残してみる。

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

• 良いアルゴリズムの3つの望ましい性質: 正しく、効率的で、容易に実装できること
• アルゴリズムが常に正しい答えを出力するのに対し、ヒューリスティックは正しい動作をする保証がない。
  • 例: 巡回セールスマン問題: 全探索(n!)アルゴリズムは正しいが極めて遅く、最近接点や最近接ペアヒューリステックは明らかな弱点がある
  • 例: 映画撮影スケジューリング問題: 最初に終わる仕事を選択するというよいアルゴリズムが存在。撮影区間に切れ目がある場合にはよいアルゴリズムはない。
• アルゴリズムには正しさの論証が必要
• アルゴリズムの表現: アイディアを表現した自然言語、疑似コード、プログラムコード。明確にアイディアを表現することが大切。
• 問題の記述: (1) 許される入力例の集合、 (2) アルゴリズムの出力に要求される性質
• 反例はアルゴリズムの誤りを示す強力な方法。不必要な詳細を拭い去った単純な反例がよい。
  • 反例の探し方: 小さく考える、網羅的に考える、弱点を探す、同点(タイ)を作る、極端なものを探す
• アルゴリズムの証明には数学的帰納法がよく使われる
• アルゴリズムを実問題に応用するためには応用問題を抽象的なデータ構造に変換することが大切
  • データ構造: 順列、部分集合、木、グラフ、点や点集合、多角形、文字列
• 再帰的な思考が大切。上記のデータ構造はいずれも一部を取ると同じ種類のデータ構造が得られる再帰的なデータ構造であることに留意せよ。

第2章 アルゴリズム解析

• 計算量: 最悪計算量、最良計算量、平均計算量
  • 本にはないが償却計算量というのものある。平均計算量は独立施行、償却計算量は同一系列での連続施行。平均の意味合いは不明確で、最悪を考えるのが有益。
• ビッグオー記法: f(n)=O(g(n))とは、c*g(n)がf(n)の上界であることを示す。Ω(・)は下界、Θ(・)はO(・)かつΩ(・)であることを表す。
  • おもな計算時間のクラス: O(1), O(log(n)), O(n), O(n*log(n)), O(n^2), O(2^n), O(n!)
• 計算量の事例: 挿入ソート、選択ソート、行列の積
• 対数の概念は重要。
  • 二分探索はアルゴリズム設計における最も強力なアイディアの一つ。
  • 平衡二分木(またはn分木)の高さは葉の数やノードの数のlog。
  • n通りのビットパターンを表せる最小のビット数はlog(n)。
  • a^nの高速な再帰的計算

第3章 データ構造

• データ構造の選択は臓器移植なみに効く。
• データ構造の大別
  • 連続 (contiguous) 構造: 配列、行列、ヒープ、ハッシュテーブル
  • 連結 (linked) 構造: リスト、木、グラフの隣接リスト表現
• 配列
  • 長所: 定数時間アクセス、領域の効率、メモリの局所性
  • 短所: サイズ固定。動的配列(領域が足りなくなったら倍々に拡張)で解決できる。動的配列へのアクセスは最悪時定数時間ではなくなるが、償却(amorized)定数時間。
• 連結リスト
  • 長所: オーバーフローが起こらない、挿入と削除は配列より簡単、レコードサイズが大きいときポインタ操作のほうが効率的
  • 短所: ポインタ格納に余分な領域が必要、ランダムアクセスに弱い、キャッシュが効きにくい
• コンテナ: データアイテムを、その内容と無関係に保管したり取り出したりできるデータ構造。
  • スタック: push, popメソッドを備える。LIFO。
  • キュー: enqueue, dequeuqメソッドを備える。FIFO、最悪待ち時間の最小化。
  • 辞書(dictionary): KVS。search, insert, deleteメソッドを備える。さらに、 max, min, predecessor(ソート順での一つ前の要素), successor(ソート順での一つ次の要素)を備える場合もある。
• いろいろなデータ構造を使って辞書を実装したとき

(*)サーチはすでにできているとする

(**)サーチができていても前ノードを探すのに先頭から探索しなおす必要がある

(***)リストの末尾ポインタを保持しておくものとする

• 二分探索木
  • 配列とリンクリストを見る限り、探索と更新にはトレードオフ。
  • 二分探索木を使えば探索、挿入、削除の3操作はいずれもO(h)。
  • n!通りの挿入順序が等確率だとすると、平均ではhはO(logn)だが、最悪ではO(n)。
  • 平衡二分探索木の実装は赤黒木(この本では2色木と書いてある)やスプレイ木などがあり、すべての辞書操作がO(logn)でできる。
  • 平衡二分探索木をブラックボックスとして使ってO(nlogn)のソートが自然な形で実現できる。
• 優先順位付きキュー: insert, find-minimum, delete-minimum の3メソッドを備える抽象データ構造
• いろいろなデータ構造を使って優先順位付きキューを実装したとき

(*) insert時に最小要素へのポインタを保持しておく

• ハッシュ表
  • キーを整数に写像する。衝突がなければ辞書のsearch, insert, deleteがいずれもO(1)になる。実用的には辞書を実装するベストの方法。
  • 衝突回避: 連鎖法 (各バケットをリンクリストにする)、開アドレス法 (挿入時に衝突が見つかったら次のアドレスに要素を入れる)。
  • 連鎖法はメモリを食う。開アドレス法は充填率が上がってきたときの要素削除で大量の要素再配置が発生する。
• 双方向リンクリストを使った連鎖法による要素数mのハッシュ表を使って辞書を実現したとき

• ハッシングを用いた効率的な文字列探索: Rolling hash を使った Rabin-Karp のアルゴリズム。素朴な実装の最悪計算時間はO(mn)、Rabin-Karpのアルゴリズムの期待時間はO(m+n)

第4章 ソートと探索

• よいソートアルゴリズムがO(nlogn)で走ることは重要。
• ソートは二分探索、最近接ペア、要素の一意性、度数分布、k番目に小さい要素を探す、凸包 (convex hull) など多くの問題を簡単にする。
• ヒープを使ってO(nlogn)のソートができる。
• minヒープは、子より親が小さいことが保証された二分木(maxヒープはその逆。)。ヒープは配列にうまく格納できる。
• ヒープへの挿入は、末尾に要素を足しbubble upすればよい。
• bubble upは2つの子と親を比べ、子のほうが小さければより小さいほうの子を親と入れ替える操作。入れ替えが起これば木の根に向かって反復的に操作を繰り返す。
• ヒープでのextract minは根ノードを取り除き、末尾要素を根に移動させてbubble downすればよい。
• bubble downは2つの子と親を比べて親のほうが大きければ小さいほうの子を親と入れ替える操作。入れ替えが起これば木の葉に向かって反復的に操作を繰り返す。
• サイズnのヒープの初期化はO(nlogn)ではなくO(n)でできる。
• クイックソート
• マージソート
• バケットソート

• 基数ソート

• バイナリサーチ: 応用として、ソート済み配列の中に与えられたキーkが現れる回数の数え上げ、片側二分探索。

第5章 グラフ横断

• いろんなグラフがある
  • 無向と有向
  • 重み付きと重みなし
  • 単純と非単純(多重辺または自己ループを含む)
  • 閉路と非閉路 (有向非閉路グラフ=DAGは特に重要)
  • その他: 埋め込み(頂点と辺が幾何的な位置を持つ)と位相 (topology)、暗黙と明示、ラベル付きとラベルなし
• グラフのデータ構造: 隣接行列と隣接リスト
• グラフの横断: もれなくかぶりなく。
• 幅優先探索(BFS)
  • 応用
    • 重みなしグラフの最短経路
    • 連結成分の列挙
    • 二部グラフかどうかの判定(二彩色)
• 深さ優先探索(DFS)
  • 重要な性質として、無向グラフの辺を木辺(tree edge)と逆辺(back edge)に分類する。DFSの性質上、兄弟やいとこに辺が行くことはない。
  • 応用
    • 閉路の有無判定。逆辺が存在することと閉路があることは同値。
    • 関節点(または切断点)を探す: 一つの頂点およびそこにつながる辺を除去すると連結成分が連結でなくなるような頂点
    • 有効グラフのDFSを使って位相的ソート(topological sort)ができる: 依存関係のあるタスクの実行順序。
    • 有効グラフの強連結性の判定: 頂点vから任意の頂点に到達でき、辺の向きを逆にした後でも頂点vから任意の頂点に到達できるか
    • 応用して強連結成分への分割

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

• 最小スパニング木: 全ての頂点を連結する木(スパニング木)のうち辺の重みの総和が最小のもの
  • プリムのアルゴリズム: 連結成分から出ている最短辺を採用
  • クラスカルのアルゴリズム: 未連結の成分をつなぐ最短辺を採用
• union-find データ構造: 集合のサブグループへの分割状態を記憶するデータ構造。要素iとjが同じグループに入っているかの判定と、2つのグループを連結を効率よく行える。
• ダイクストラのアルゴリズム: 最短経路法。プリムのアルゴリズムと非常に似ている。スタート点からの距離最小の未連結点をグラフに組み入れる。
• フロイド-ワーシャルのアルゴリズム: 全ペア間最短経路、3重ループ
• エドモンズ-カープの最大フローアルゴリズム: bfsで始点から終点までの経路を見つけ、そこを通れる分だけフローを足すことを繰り返す。ただし容量いっぱい流れている辺はbfsのときに無視する。

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

• バックトラック法: 探索空間におけるDFSを使った、組み合わせ問題の解の探索。
• モンテカルロ法とシミュレーテッドアニーリング: コードを書くことはないので略。

第8章: 動的計画法

• フィボナッチ数列
• 二項係数
• 文字列の編集距離: 様々に応用できる
  • 部分文字列マッチング: 文字列の途中から探索を始めてもよいようにする
  • 最長共通部分列 (longest common subsequence, LCS): 置換操作を禁止
  • 最大単調部分列: 数列から単調増加部分列が残るよう最小個数の要素を削除する問題。自分をソートした数列とのLCS。

• 入れ替えなしの整数分割: 数列を入れ替えずに間に決まった数の

  を入れて、各連の合計の最大値を最小にする。

• DPはどのようなときに嬉しいか: 対象が自然な順序を持つ列になっているとき。任意の順序で要素をとるような場合は組み合わせが爆発するのでうれしくない。

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

• 多項式時間で解ける問題と解けない問題がある
• 困難な問題が困難だとわかることは大事
• NPとNP complete (略)

(復習用)問題集

以下の問題について、(1)自然言語と図、(2)疑似コード、(3)コード、(4)最悪計算量と平均計算量、を答えよ。

• p.3 挿入ソート
• (p.12 映画撮影スケジューリング問題の最適スケジューリング)
• p.47 選択ソート
• p.49 愚直な文字列パターンマッチング
• (p.75 動的配列)
• p.76 単方向連結リストの実装と探索、挿入、削除
• (双方向連結リストの実装と探索、挿入、削除)
• (p.80 スタックの実装、pushとpop演算)
• (p.80 キューの実装、enqueueとdequeue演算)
• {未ソート、ソート済み}{配列、単方向リンクリスト、双方向リンクリスト}を用いて辞書を実装したときの、search, insert, delete, predecessor, successor, max, min メソッドの時間計算量 (コードは書かなくていい)
• p.87 二分木の実装 : 親へのポインタあり
• p.87 二分探索木の探索、p.88 最小要素探索、 pre-order, in-order, post-orderでのtraverse, p.89 挿入、削除の時間計算量 (コードは複雑なので書かなくていい)、predecessor、successor
• p.92 平衡探索木を使い、(1) insertとin-order traverseのみ、 (2)min, successor, insert のみ、 (3) min, insert, delete, search のみ、でそれぞれ O(nlogn)時間でソートする方法(コードは書かなくていい)
• p.94 未ソート配列、ソート済み配列、平衡二分探索木を使って優先順位付きキューを実装したときの、insert, find-minimum, delete-minimum メソッドの時間計算量 (コードは書かなくていい)
• p.101 Rabin-Karp の文字列検索アルゴリズム
• p.123 ヒープの実装、p.125 挿入、p.126 extract_min、p.127 heap sort
• p.128 ヒープの高速な初期化
• p.129 要素nのヒープと実数xを与え、ヒープ中のk盤面に小さい要素がx以上かどうかを高速に判定せよ。
• p.136 マージソート
• p.138 クイックソート (最悪計算量と平均計算量を論じよ)
• クイックソートを応用し、配列の中で小さいほうからk番目の要素を求めよ。
• p.148 バイナリサーチ
• p.148 ソート済み配列の中に与えられたキーkが現れる回数
• p.169 隣接リストを使ったグラフのデータ構造の定義、p.170 各行が”i j”の形式(辺iから辺jへの有向辺を意味する)からなる入力の読み込み
• p.180 幅優先探索
• p.188 深さ優先探索
• p.212 プリムのMSTアルゴリズム
• p.216 クラスカルのMSTアルゴリズム
• p.218 union-find データ構造: 初期化、find (自分が属するグループの親ノードを見つける)、union_sets (2つの点が属するグループを結合する)、same_component (2つの点が同じグループに属するか判定する)
• p.227 ダイクストラのアルゴリズム
• p.230 フロイド-ワーシャルのアルゴリズム
• p.240 エドモンズ-カープの最大フローアルゴリズム
• p.252 すべての部分集合の数え上げ
• p.254 すべての順列の数え上げ
• p.256 グラフのすべての経路の数え上げ (- N-Queen 問題)
• p.299 動的計画法を使ったフィボナッチ数列(x_{n+2}=x_{n+1}+x_n)の計算。(メモ化再帰でも書いてみよ)
• p.302 二項係数の計算
• p.306 編集距離

• p.319 入れ替えなしの整数分割: 数列を入れ替えずに間に決まった数の

  を入れて、各連の合計の最大値を最小にする。