ページ構成の際、次の情報源を参考にした。
- アルゴリズムイントロダクション 第3版 (CLRS)
- プログラミングコンテスト攻略のためのアルゴリズムとデータ構造
- Algorithms | Jeff Erickson (inzkyk訳)
- アルゴリズム | ともめも
- Claude🔐
アルゴリズムの実行時間を解析するうえで、私たちは実行時間が入力サイズに対して漸近的に増える効率に興味がある。入力サイズと相対的な実行時間を、おそらく計算量という。
計算量には時間計算量と領域計算量がある。単に計算量といえば、普通時間計算量を指す。領域計算量は空間計算量とも言う。
アルゴリズムの実行時間を表すための、漸近記法をまとめた。
- Θ記法, シータ記法 (theta notation)
- 𝑂記法、ビッグオー記法(big-o notation)
- アルファベットのO (オー)ではなく、ギリシャ文字のΟ (オミクロン)。
-
$f(x)=Ο(g(x))$ のとき、$f(x)$が$g(x)$の定数倍と同じかそれより小さいことを指す。
- 𝑜記法, リトルオー記法, スモールオー記法 (little-o notation)
-
$f(x)=ο(g(x))$ のとき、$f(x)$が$g(x)$の定数倍より小さいことを指す。
-
- Ω記法, ビッグオメガ記法 (big-omega notation)
-
$f(x)=Ω(g(x))$ のとき、$f(x)$が$g(x)$の定数倍と同じかそれより大きいことを指す。
-
- 𝜔記法, リトルオメガ記法 (little-omega notation)
なお、Ο (オミクロン)を変換するのが面倒なので、以降はアルファベットのO (オー)を用いる。
先頭または末尾にデータを追加・削除できるデータ構造を次に述べる。
- スタック (stack)
- キュー (queue)
- 両端キュー, デック (deque, double-ended queue)
それぞれのPythonにおける実装とデータ追加・削除の操作をまとめた。（pop()するのはスタック？キュー？といつも迷うので）
| データ構造\実装 | list | collections.deque | queue.Queue |
|---|---|---|---|
| スタック | 追加: append(), 取り出し: pop() | 追加: append(), 取り出し: pop() | - |
| キュー | 追加: append(), 取り出し: pop(0) | 追加: append(), 取り出し: popleft() | 追加: put(), 取り出し: get() |
| 両端キュー | 追加: append(), 取り出し: pop() / pop(0) | 追加: append(), 取り出し: pop() / popleft() | - |
末尾を取得するのがpop()と覚えておけば良さそうだ。なお、先頭を取得するのがpull()の言語もあるようだが、Pythonは違う。
- 最小ヒープは、親が子よりも小さく、根が最小になるヒープ。単にヒープといえば最小ヒープ。
- 最大ヒープはその逆となる。
- 二分ヒープの読みは 「にぶん」ヒープ
- 二分ヒープと優先度付きキューの違いは、（WIP）
互いに素な集合がある時に、ある2つの要素が同じ集合に属しているか？を調べることをUnion-Findという。
集合を木構造で表したとき、同じ集合に属しているか？を調べるのは根を求めることに等しく、計算量が$O(N)$となりえる。
しかし、union by rank を行うことで$O(log N)$ に、さらに経路圧縮を行うことで$O(α(N))$となる。$α(N)$はアッカーマンの逆関数と呼ばれ、増加がとても遅いことで知られる。1
- union by rank: 2つの木を合体させるとき、背の高い木に背の低い木をつなげる
- 経路圧縮: find処理時、中間節点を全て根に繋ぎなおす
[!NOTE] Union-Findでfind時に経路圧縮すると、rankと木の高さが一致しないのでは？ その通り。rankと木の高さが常に等しいとは限らない。rankの代わりに木のサイズを用いても時間計算量は$O(N)$で変わらないため、説明しやすさのためにそちらを用いても良い。2
アルゴリズム図鑑で紹介されているチェーン法の他に、オープンアドレス法による対応がある。オープンアドレス法には、線形走査法とダブルハッシュ法がある。
- チェーン法
- オープンアドレス法 (開番地法)
- 線形走査法・ダブルハッシュ法に共通して言えるが、いずれはハッシュ表が満杯になる。
- 線形走査法
- 衝突が発生した場合、その1つ後ろの位置を格納箇所とする
- ダブルハッシュ法 (二重ハッシュ法)
- ハッシュが衝突したら、引数に衝突回数を加えて再度ハッシュを求める。
ハッシュ探索②（オープンアドレス法） | Programming Place Plus アルゴリズムとデータ構造編【探索アルゴリズム】 第７章
[!NOTE] オープンアドレス法って、ハッシュ値を削除したら、同じハッシュ値で再ハッシュされた値を探せなくならない？ なる。したがって、ハッシュ値の削除時には空の番地であることを示す値をいれる。この値をTombstone (墓石)という。3
番兵
forループまたはwhileループで、探索のための比較以外に終了条件の判定を行うことが面倒であるため、リストの最後に目的のデータをダミーで入れておく。- Pythonでループを実装する場合や、TypeScriptで
findなどを用いる場合、勝手に最後まで探索してくれるので考慮不要。
- 挿入ソート
- カードの山を右手に取り、1枚引いて引いて左手側に加える、この時左手側の適切な位置に挿入することを繰り返す。
- 再帰でも書ける。
- 個人的には左手ソートと呼びたい。
- 選択ソート
- データの先頭（または後方）が徐々に整理済みになっていく点は、挿入ソートと変わらない。
- 1番小さい（大きい）値、2番目に小さい（大きい）値…と順番に探していく点と、値が見つかった後は元々n番目にいた値が入れ替わりで飛ばされてしまう点が異なる。
- この入れ替わりで飛ばされてしまう点が面白いので、個人的には（ダンジョン飯の）ミスルンソートと呼びたい。
- バブルソート
- 右から左に、小さい値がバトンタッチしながらやってくる様子から、個人的には玉突きソートと呼びたい。
- シェルソート
- マージソート
- クイックソート
- 再帰的にパーティションを行う。
- 計数ソート
- 基数ソート
- WIP
シェルソート
パーティション
文字列探索とは、文字列Sが単語Wを含む場合に、それが文字列Sの何文字目から何文字目かを調べるタスクである。例えば、S="Hello,world!"、W="world"の場合、6文字目から10文字目が一致する。普通に計算すると、計算量は$O(|S| \cdot |W|)$となる。
KMP法は、一度比較した文字は、なるべく2回比較したくない、という気持ちのアルゴリズムである。例えば次の文字列を考える。
- S: "firefirefighter"
- W: "firefighter"
この文字列は偶然にも先頭から6文字が一致しているので、先頭から比較を始めたKMP法は7文字目で一致しないことに気づく。ここで単純なアルゴリズムなら、次にSの2文字目"i"とWの1文字目"f"を比較するところから始めるだろう。しかしKMP法は、「もうSの6文字目までは比較したから、次はSの7文字目"r"とWの1文字目"f"を比較したい！」と考える。もちろんこれは失敗する！
失敗する原因は、すでに比較した文字列の中に、先頭が一致する他のパターンが含まれているためである。Sの部分文字列"firefir"の後半のfiは、Wの"fighter"だけでなく"fire"とも比較しなければいけないのだ！そこでKMP法では、Wの各文字に対して、「この文字で比較が失敗したら、Wの直前のX文字分と一致していたSの文字列はWの先頭とも一致するはずだから、Sの現在地をX文字巻き戻した箇所とWの先頭を揃えてから再開してね」という数Xを事前に計算しておく。これを部分マッチテーブルという。
次の4通り。
- 深さ優先探索
- 行きがけ順
- 最もシンプル。迷路の右手法と同じ。
- 通りがけ順
- 西から順番に印を付けるイメージ。
- 帰りがけ順
- 個人的には行き止まり順だと思っている。
- 行きがけ順
- 幅優先探索
- 最長増加部分列
- ある列に含まれる文字を、順序を崩さぬようにいくつか選んで再構成された列。
- 列が元の列において連続である場合は「部分文字列」と呼ぶ。
- 最長増加部分列とは、元のアルファベットなどの文字列の部分列のうち、a,b,c...の順番になっているようなものを指す。
- あずぱんさん曰く「表的計画法」。
次のような問題がある
- 編集距離
- 連鎖行列積
- なるべく大きい数字を早めに消してしまうのが方針となる。
動的計画法の例として、編集距離の問題を考える。編集距離とは、単語Aを1文字づつ置換・挿入・削除することで、何手で単語Bに変身できるかを指す値である。例えば、MONEYをFOODに変身させるにあたって、次の手順では4手で変身でき、同時に2単語間の最短距離でもある。
- MONEY → FONEY
- FONEY → FOOEY
- FOOEY → FOODY
- FOODY → FOOD
次に、MONEYをLOVEに変身させる場合で、編集距離の依存関係をフローチャートで示す。動的計画法（編集距離の依存関係の可視化）を参照のこと。
最大部分配列とは、正〜負の整数を要素に持つ配列に対して、連続する部分列で和が最大のものを求める問題である。これを解くKadane4's algorithm（カデインのアルゴリズム）について、最適な小構造に注目した説明を考えた。
正〜負の整数がバランスよく含まれる最大部分配列を2つの部分配列に分けると、どちらの部分配列の和も正になる。それを踏まえたうえで、次の手順で最大部分配列を求める。
- N文字目から順番に数を足していき、M文字目で和の合計が負になった時、最大部分配列がN文字目から始まるとしたらM−1文字目までのどこかである。
- N文字目からM文字目までの各段階の和の合計のうち最大のものが、最大部分配列がN文字目から始まる場合の候補となる
- M文字目で和の合計が負になった時、M+1文字目から再び手順を繰り返す。こうして得られた最大部分配列の候補で決勝トーナメントを行い、最大のものが配列全体の最大部分配列である。
-
頂点 (vertex), ノード (node)
- 辺$uv$および$u→v$について、頂点$u$と$v$を endpoint(端点)
-
$u→v$ について、$u$をtail(尾),$v$ をhead(頭)
-
- カット点
- ソース (source): 有向グラフにおいて、ある頂点に向かう辺がない頂点
- シンク (sink): 有向グラフにおいて、ある頂点から出る辺がない頂点。シンクは沈む、流すといった意味
- 辺$uv$および$u→v$について、頂点$u$と$v$を endpoint(端点)
-
辺 (edge), アーク (arc)
- 特に有向辺をarcと呼ぶ場合もある
- 橋
-
列 (sequence): 頂点の列
- 歩道 (walk): 隣接する頂点からなる列
親、根、木辺などは<#探索木(森)の性質>を参照。
-
辺に向きがあるかどうか
- 有効グラフ (directed graph)
- 無向グラフ (undirected graph, unordered graph)
-
ループ・多重辺を持っているか
- simple: ループ・多重辺を持たないグラフ
- 多重グラフ (multigraph): ループ・多重辺を持つグラフ
-
グラフ上のどの頂点からでも、他の頂点に行けるか？
- 連結グラフ (connected graph)
- 非連結グラフ (disconnected graph)
- 強連結 (strongly connected): 有向グラフにおいて、どの頂点からでも他の頂点に行けること
-
閉路を含むか
- 巡回グラフ (cyclic graph)
- 非巡回グラフ (acyclic graph)
- コーダルグラフ (chordal graph): 4つ以上の頂点の閉路が全て弦を持つグラフ。言い換えると、三角形から構成されるグラフ。
他に次のような定義がある。
- 森 (forest): 非巡回グラフ
- 木 (tree): 連結非巡回グラフ
グラフ$G=(V,E)$に対して、次のように定義される。
- 部分グラフ (subgraph): 頂点と辺のいずれも$G$に含まれるグラフ
- 真部分グラフ (proper subgraph): subgraphであって、$G$と等しくないもの
- 同型 (isomorphic):
$G$ と$G’$が、それぞれ対応する頂点と辺を持っている時、$G$と$G'$は同型 - 誘導部分グラフ (induced subgraph):
$E'=E∩\binom{V}{2}$ 、つまり部分グラフ内のすべての頂点は、元のグラフ$G$で持っていた辺を持っている、ということ - 全域部分グラフ (spanning subgraph):
$V'=V$ である部分グラフ。$G-e$や$G-F$で表される- 全域木 (spanning tree)
- 最小全域木 (minimum spanning tree): 全域木のうち、合計の重みが最も軽い木。「すべての地域に電力を届けるための最も安いネットワークは？」といった応用がある。
- 最短路全域木 (shortest path spanning tree): 単にshortest path tree(最短路木)といってこれを指すことが多い印象。
- 全域木 (spanning tree)
- 誘導全域部分グラフ (induced spanning subgraph): 定義する必要なし（それって同型なので）
- クリーク (clique): 完全部分グラフともいう。その部分グラフに含まれるすべての頂点はお互いに辺を持つ必要がある。
なぜ誘導グラフと呼ぶかについては、「生成部分グラフ」という用語についてを参照。
-
逆 (reversal):
$G$ のすべての辺$u→w$を$w→u$に取り換えたグラフ -
成分 (component): 極大な連結部分グラフ
- 強連結成分 (SCC, strongly connected component), 強成分 (strong component)
- ソース成分 (source component)
- シンク成分 (sink component)
-
強連結成分グラフ (strong component graph): 強連結成分を1つの頂点にまとめたグラフ
- 到達可能性
- 成分の検出
- 関節点 (articulation)の検出
- 最長路 (longest path)
- SSSP(Single Source Shortest Path, 単一始点最短経路、または単に最短路)
- APSP(All Pair Shortest Path, 全点対最短経路)
- 隣接リスト
- メモリが少ない（＝文字数が少なく済む）性質から、競プロでは、グラフは隣接リストに近い形式で渡されることが多い。
- 隣接行列
グラフの探索には、深さ優先や幅優先などいろいろあるが、実は袋（＝候補となる辺を入れておくデータ構造）に何を採用するかの違いに過ぎない。
| 名前 | 袋 | 解決する問題 |
|---|---|---|
| 深さ優先探索 | スタック | |
| 幅優先探索 | キュー | |
| 最良優先探索 | 優先度付きキュー | |
| 最良優先探索 | 優先度付きキュー（辺の重み） | 最小全域木 |
| 最良優先探索 | 優先度付きキュー（辺の重みの和） | 最短路木 |
| 最良優先探索 | 優先度付きキュー（路の幅） | 最幅路 |
- root(根)
- parent(親)
- tree edge(木辺): ?
- forward edge(前方辺): ?
- backward edge(後方辺): ?
- cross edge(交差辺): ?
- 自分なりに言い換えると「左手法」。迷路の左手法と考え方が同じだから。
- 左手法の要領でグラフを探索し、そこから先は行き止まり、というところまで行ったら現在地をリストに記録する。
- 行き止まりから引き返すごとに、そこから先が行き止まりなら現在地をリストに記録するし、分岐があれば分岐に進む。
- Topological Sort Visualized and Explained | Carl the Personが短くて分かりやすい。
強連結成分を計算するためのアルゴリズムは次の通り。線形時間で計算するための工夫がポイント。
- グラフの頂点全てに対して、お互いに到達できる点を何か優先探索で計算する（$O(VE)$）
- Kosaraju(コサラジュ)とSharir(シャリア)のアルゴリズム
- 逆グラフの帰りがけ順に辿った頂点を、さらに逆順に何か優先探索する時に、何か優先探索がシンク成分の内側に留まることを利用したアルゴリズム
- Tarjan(タージャン)のアルゴリズム
いくつもアルゴリズムがあるが、次に述べる戦略の実装違いといえる。
その戦略とは、入力グラフ$G$に対して、その頂点だけからなる$F$（つまり、$F=(V, ∅)$）をintermediate spanning forest(中間全域森)として定義し、$F$にいい感じの辺を徐々に加えていく戦略である。
プリム法とクラスカル法が有名である。グラフが密な場合に限ってはプリム法が早いが、それ以外は実装が容易なクラスカル法を用いれば良い。
def boruvka(V, E):
F = (V, ∅)
count = count_and_label(F) # 成分数
while count > 1:
add_all_safe_edges(E, F, count)
count ← count_and_label(F)
return F任意の頂点をスタート地点として、接続する中で重みが最小かつ閉路を作らない辺を付け加えることを繰り返す。グラフが隣接リストで表現されている場合、計算量はO(ElogV)となる。一方で隣接行列を用いた場合の計算量はO(V^2)となるため、辺に比べて頂点が少ない場合に特に高速になる。
プリム法 (Prim's Algorithm) | サルでもわかるアルゴリズムが分かりやすかった。
すべての辺の中から、重みが最小かつ付け加えても閉路にならない辺を選ぶ。このようにして選んだ辺の集合が最小全域木となる。
閉路の検出はUnion−Findを用いて高速に行うため、計算量はほぼ辺のソートにかかると考えてよく、計算量はO(ElogE)となる。
重み付きグラフにおいて、2つの頂点を結ぶ経路の中で、重みが最小の経路を求める問題。次の種類がある。
- 2頂点対最短経路問題 (single-pair shortest path problem)
- 単一始点最短経路問題 (SSSP, single-source shortest path problem)
- 単一終点最短経路問題 (SDSP, single-destination shortest path problem)
- 全点対最短経路問題 (APSP, all-pairs shortest path problem)
- 自分なりに言い換えると、「近さランキング法」。
- 単一始点最短経路を求めるのに用いる。計算量は$O(|V|^2)$になる。
- 隣接リストと優先度付きキューを用いると、計算量は$O((|V|+|E|)log|V|)$になる。
- Dijkstra’s Algorithm | Depth Firstが非常に分かりやすい。
- ウィザードリィのような主観視点で例えると次の通り。
- 今いる場所（＝頂点）から見える場所について、1つづつ距離を書き留め、探索候補（優先度付きキュー）に加える。
- 全て書き留めたら、最も近い場所を候補から選んで進む。
- 同じく、進んだ先から見える場所について、1つづつ距離を測る。その時、すでに書き留めた場所だったなら、今いる場所を経由した方が近道である場合に限って書き留め、探索候補に加える。
- 書き留めたら、またスタートに戻ってから、次に近い場所に進む。これを場所の数繰り返す（注）
- 注: 同じ場所を2回訪問することはない。言い換えると、探索候補の中で一番近い場所だけは、後からより近いルートが見つかることは無い。
- 螺旋本には、隣接リストと二分ヒープを用いると、計算量は$O((|V|+|E|)log|V|)$になる、とあるが...正直言って優先度付きキューでの実装より複雑だし計算量も変わらないので、私は理解していません...。
[!NOTE] 実世界でのダイクストラ法の応用を知りたい
始点から辺の数がn以内でたどり着ける頂点について、n=1,2,3...|V|-1まで順番に最短経路を探す手法。5v-1回目のループの後に再度最短経路を探し、距離が更新されれば負の閉路があると判断できる。最短路は閉路を含まないため、その長さは|V|-1となる。負閉路の検出も行うため、計算量はO(|V|*|E|)となる。
- グラフに負の重みがある場合、ダイクストラ法が機能しない。
- 重みを変更し、負の重みをなくすことで、ダイクストラ法を機能させる方法。
- アルゴリズムの教科書では全組最短路のアルゴリズムとして紹介されている。
入力サイズ$n$, 定数$k$について、計算量が$O(n^k)$で抑えられるアルゴリズムを多項式時間アルゴリズムという。計算量が$O(n^{k^k})$や$O(k^n)$の場合はいわない。
多項式時間で解ける問題は、複雑性クラスPに属しているという。逆に、多項式時間で解けない問題をNP困難 (NP-Hard)という。また、多項式時間で解けるかどうかに関わらず、多項式時間で検証できる問題をNPという。そして、NP困難かつNP、つまり多項式時間では解けないが、解の検証はできる問題をNP完全 (NP-Complete)という。多くの場合、NP完全の証明では、すでにNP完全であることが証明されている問題に多項式時間で変換できることを示す。
よく言われるP≠NPとは、PがNPの真部分集合である、つまり多項式時間では解けないが解の検証はできる問題が存在する、という命題である。
本節の執筆にあたってヒューリスティック探索入門6を参考にした。
ヒューリスティック探索のベンチマークとして、状態空間問題がある。これは初期状態とゴール条件が与えられ、それを満たす経路を探索する問題である。
よく知られたNP困難な問題として巡回セールスパーソン問題 (TSP, Traveling Salesperson Problem)がある。地図上の全ての地点を通りつつ最初の地点に戻る最短経路を求める問題である。最適な経路はその部分経路も最適だから動的計画法で解けるが、その計算量は$O(n\cdot 2^n)$など指数時間になるため、NP困難である。
状態空間問題は完全情報であり、状態遷移が決定的であることを仮定した。状態遷移が確率的である問題はマルコフ決定過程 (MDP, Markov Decision Process)という。
ダイクストラ法では、スタート地点から近い地点を順に探索する。しかし、例えばゴールまでの直線距離が分かったら、もっと効率的な探索ができないか？このように、ノードの有望さを定量化する関数をヒューリスティック関数 (heuristic function)といい、それを用いたアルゴリズムをヒューリスティック探索という。逆に言えば、有望さの見積もりを用いない探索アルゴリズムは、ヒューリスティック探索が常に定数を返す特別な場合とみなせる。
ナップザック問題や巡回セールスパーソン問題などの組合せ最適化問題を考える。例えば、100個ある荷物から、重量が一定以下になるように荷物を選ぶことを考える。$2^{100}$通りから、重量が一定以下かつ価値が最大の組合せを選べばよいが、明らかに計算が終わらない。そこで、この組合せを木に見立てる。木が分岐するとき、その部分問題の全通りを計算するよりも素早く、簡易的な方法で計算を行い、その結果次第では部分問題をスキップして良い場合がある。
例えば0-1ナップザック問題なら、条件を緩めた問題として連続ナップザック問題がある。70-1ナップザック問題の解は連続ナップザック問題の解より大きくならない（上界）。そこで、全体の連続ナップザック問題の解と部分問題の解が一致したら、最適値が出たとして計算を打ち切って良いなど、計算対象を限定することができる。8
競技プログラミングの基礎的な問題では時間計算量を$O(N^2)$未満に抑えれば良いことが多いが、現実で遺伝子情報などの巨大データを扱うと$O(N)$でも実用的でない。更に空間計算量も問題になる。
そこで、空間計算量を最低限に抑えつつ、時間計算量も$O(N)$未満に抑えよう、というのが簡潔データ構造の動機である。ここで最低限とは、理論値に迫ろう、というくらいのニュアンス。
理論値には「情報理論的下限」という名前がついており、データ本体（簡潔表現 (succinct representation)）とインデックス（簡潔索引 (succinct index)）に対してだいたい次のように定義されている。正確な定義は教科書を参照してください。9
- 簡潔表現: データを表すのに必要なビット数が、$log_2(データの種類)$ + 僅かな補助データであること。要するに全パターンにIDを振ってそれを2^nビットで表すと言っている。
- 簡潔索引: 索引を表現するのに用いるビット数がデータ量と同じペースで増えたりしない、つまり$o(lg(n))$（リトルオーであることに注意）である索引。
ちなみに succinct は「サクスィンクト」と発音し、簡潔な、準備ができた、という意味。
word-RAMという架空のアーキテクチャのマシンを想定する。特徴は次の通り。
- メモリロケーションあたりの容量が1ビット（通常は8ビット = 1バイト）
- したがって、メモリ全体の容量がUビットの場合、メモリアドレスは
$U / 1 = U$ ビット - 1単位時間でメモリアドレスを指定できるように、CPUのワード長は$log_2(U)$ビット
rankとは、ビットベクトル中の特定の位置までの0または1を数える処理である。シンプルに実装すると時間計算量が$N$になってしまうので、様々な工夫がなされてきた。
まず、全てのビットベクトルに対してその位置までの1の数をあらかじめ数えて表に記録しておくことを考える。時間計算量は表引きに係る分だけになるが、空間計算量が表の行数(
次に、ビットベクトルの$l$ビットごとに累計の1の数をあらかじめ記録することを考える。ここで試しに$l$を$log_2{N}$とすると、簡潔索引の空間計算量は行数(