til

データ構造, アルゴリズム (data structures and algorithms)

ページ構成の際、次の情報源を参考にした。

基礎知識

漸近記法

アルゴリズムの実行時間を解析するうえで、私たちは実行時間が入力サイズに対して漸近的に増える効率に興味がある。入力サイズと相対的な実行時間を、おそらく計算量という。

計算量には時間計算量と領域計算量がある。単に計算量といえば、普通時間計算量を指す。領域計算量は空間計算量とも言う。

アルゴリズムの実行時間を表すための、漸近記法をまとめた。

漸近記法

なお、Ο (オミクロン)を変換するのが面倒なので、以降はアルファベットのO (オー)を用いる。

データ構造 (data structures)

スタック・キュー・両端キュー

先頭または末尾にデータを追加・削除できるデータ構造を次に述べる。

それぞれの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は違う。

ヒープ

B木

フィボナッチヒープ

van Emde Boas木

Union-Find

互いに素な集合がある時に、ある2つの要素が同じ集合に属しているか？を調べることをUnion-Findという。

集合を木構造で表したとき、同じ集合に属しているか？を調べるのは根を求めることに等しく、計算量が$O(N)$となりえる。

しかし、union by rank を行うことで$O(log N)$ に、さらに経路圧縮を行うことで$O(α(N))$となる。$α(N)$はアッカーマンの逆関数と呼ばれ、増加がとても遅いことで知られる。1

[!NOTE] Union-Findでfind時に経路圧縮すると、rankと木の高さが一致しないのでは？ その通り。rankと木の高さが常に等しいとは限らない。rankの代わりに木のサイズを用いても時間計算量は$O(N)$で変わらないため、説明しやすさのためにそちらを用いても良い。[^saka_pon_2022] [^saka_pon_2022]: Union-Find の実装方法まとめ

ハッシュ表 (hash table)

アルゴリズム図鑑で紹介されているチェーン法の他に、オープンアドレス法による対応がある。オープンアドレス法には、線形走査法とダブルハッシュ法がある。

[ハッシュ探索②（オープンアドレス法） Programming Place Plus　アルゴリズムとデータ構造編【探索アルゴリズム】　第７章](https://programming-place.net/ppp/contents/algorithm/search/007.html#linear_probing)

[!NOTE] オープンアドレス法って、ハッシュ値を削除したら、同じハッシュ値で再ハッシュされた値を探せなくならない？ なる。したがって、ハッシュ値の削除時には空の番地であることを示す値をいれる。この値をTombstone (墓石)という。2

基礎的なアルゴリズム (algorithms)

番兵

ソート

シェルソート

シェルソート（螺旋本）

パーティション

パーティション

探索

KMP法

文字列探索とは、文字列Sが単語Wを含む場合に、それが文字列Sの何文字目から何文字目かを調べるタスクである。例えば、S=”Hello,world!”、W=”world”の場合、6文字目から10文字目が一致する。普通に計算すると、計算量は$O( S \cdot W )$となる。

KMP法は、一度比較した文字は、なるべく2回比較したくない、という気持ちのアルゴリズムである。例えば次の文字列を考える。

この文字列は偶然にも先頭から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を1文字づつ置換・挿入・削除することで、何手で単語Bに変身できるかを指す値である。例えば、MONEYをFOODに変身させるにあたって、次の手順では4手で変身でき、同時に2単語間の最短距離でもある。

  1. MONEY → FONEY
  2. FONEY → FOOEY
  3. FOOEY → FOODY
  4. FOODY → FOOD

次に、MONEYをLOVEに変身させる場合で、編集距離の依存関係をフローチャートで示す。動的計画法（編集距離の依存関係の可視化）を参照のこと。

最大部分配列問題

最大部分配列とは、正〜負の整数を要素に持つ配列に対して、連続する部分列で和が最大のものを求める問題である。これを解くKadane[^j_kadane]’s algorithm（カデインのアルゴリズム）について、最適な小構造に注目した説明を考えた。 [^j_kadane]: 2024年現在もCMUに勤めておられる。ご本人の映像があるので、見るとアルゴリズムに親近感が湧くかもしれない。

正〜負の整数がバランスよく含まれる最大部分配列を2つの部分配列に分けると、どちらの部分配列の和も正になる。それを踏まえたうえで、次の手順で最大部分配列を求める。

  1. N文字目から順番に数を足していき、M文字目で和の合計が負になった時、最大部分配列がN文字目から始まるとしたらM−1文字目までのどこかである。
  2. N文字目からM文字目までの各段階の和の合計のうち最大のものが、最大部分配列がN文字目から始まる場合の候補となる
  3. M文字目で和の合計が負になった時、M+1文字目から再び手順を繰り返す。こうして得られた最大部分配列の候補で決勝トーナメントを行い、最大のものが配列全体の最大部分配列である。

貪欲アルゴリズム

グラフアルゴリズム

グラフの性質

グラフの要素

親、根、木辺などは<#探索木(森)の性質>を参照。

グラフの種類

他に次のような定義がある。

グラフどうしの関係

グラフ$G=(V,E)$に対して、次のように定義される。

なぜ誘導グラフと呼ぶかについては、「生成部分グラフ」という用語についてを参照。

グラフの問題

グラフのデータ構造

何か優先探索

グラフの探索には、深さ優先や幅優先などいろいろあるが、実は袋（＝候補となる辺を入れておくデータ構造）に何を採用するかの違いに過ぎない。

名前 袋 解決する問題
深さ優先探索 スタック  
幅優先探索 キュー  
最良優先探索 優先度付きキュー  
最良優先探索 優先度付きキュー（辺の重み） 最小全域木
最良優先探索 優先度付きキュー（辺の重みの和） 最短路木
最良優先探索 優先度付きキュー（路の幅） 最幅路

探索木(森)の性質

トポロジカルソート (topological sort)

強連結成分 (strong component), 関節点 (articulation)

強連結成分を計算するためのアルゴリズムは次の通り。線形時間で計算するための工夫がポイント。

最小全域木 (MST, Minimum Spanning Tree) アルゴリズム

いくつもアルゴリズムがあるが、次に述べる戦略の実装違いといえる。

その戦略とは、入力グラフ$G$に対して、その頂点だけからなる$F$（つまり、$F=(V, ∅)$）をintermediate spanning forest(中間全域森)として定義し、$F$にいい感じの辺を徐々に加えていく戦略である。

プリム法とクラスカル法が有名である。グラフが密な場合に限ってはプリム法が早いが、それ以外は実装が容易なクラスカル法を用いれば良い。

ブルーフカ法 (Borůvka’s algorighm)

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

プリム法 (Jarník’s (Prim’s) algorithm)

任意の頂点をスタート地点として、接続する中で重みが最小かつ閉路を作らない辺を付け加えることを繰り返す。グラフが隣接リストで表現されている場合、計算量はO(ElogV)となる。一方で隣接行列を用いた場合の計算量はO(V^2)となるため、辺に比べて頂点が少ない場合に特に高速になる。

[プリム法 (Prim’s Algorithm) サルでもわかるアルゴリズム](https://www.youtube.com/watch?v=anuJPP3FZ8c)が分かりやすかった。

クラスカル法 (Kruskal’s algorithm)

すべての辺の中から、重みが最小かつ付け加えても閉路にならない辺を選ぶ。このようにして選んだ辺の集合が最小全域木となる。

閉路の検出はUnion−Findを用いて高速に行うため、計算量はほぼ辺のソートにかかると考えてよく、計算量はO(ElogE)となる。

最短路問題 (shortest path problem)

重み付きグラフにおいて、2つの頂点を結ぶ経路の中で、重みが最小の経路を求める問題。次の種類がある。

ダイクストラ法 (Dijkstra’s algorithm)

[!NOTE] 実世界でのダイクストラ法の応用を知りたい

ベルマンフォード法 (Bellman Ford’s algorithm)

始点から辺の数がn以内でたどり着ける頂点について、n=1,2,3… V -1まで順番に最短経路を探す手法。[^sambol_2015]v-1回目のループの後に再度最短経路を探し、距離が更新されれば負の閉路があると判断できる。最短路は閉路を含まないため、その長さは V -1となる。負閉路の検出も行うため、計算量はO( V * E )となる。
[^sambol_2015]: [Bellman-Ford in 5 minutes Michael Sambol](https://www.youtube.com/watch?v=obWXjtg0L64)が分かりやすい。              

ジョンソン法 (Johnson’s algorithm)

動的計画法による全組最短路

動的計画法＋分割統治による全組最短路

ワーシャルフロイド法 (Floyd–Warshall Algorithm)

計算複雑性 (computational complexity)

複雑性クラス (complexity class)

入力サイズ$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の真部分集合である、つまり多項式時間では解けないが解の検証はできる問題が存在する、という命題である。

本節の執筆にあたってヒューリスティック探索入門[^jinnaiyuu_2023]を参考にした。 [^jinnaiyuu_2023]: ヒューリスティック探索入門

状態空間問題 (state-space problem)

ヒューリスティック探索のベンチマークとして、状態空間問題がある。これは初期状態とゴール条件が与えられ、それを満たす経路を探索する問題である。

よく知られたNP困難な問題として巡回セールスパーソン問題 (TSP, Traveling Salesperson Problem)がある。地図上の全ての地点を通りつつ最初の地点に戻る最短経路を求める問題である。最適な経路はその部分経路も最適だから動的計画法で解けるが、その計算量は$O(n\cdot 2^n)$など指数時間になるため、NP困難である。

状態空間問題は完全情報であり、状態遷移が決定的であることを仮定した。状態遷移が確率的である問題はマルコフ決定過程 (MDP, Markov Decision Process)という。

ヒューリスティック探索のアルゴリズム

ダイクストラ法では、スタート地点から近い地点を順に探索する。しかし、例えばゴールまでの直線距離が分かったら、もっと効率的な探索ができないか？このように、ノードの有望さを定量化する関数をヒューリスティック関数 (heuristic function)といい、それを用いたアルゴリズムをヒューリスティック探索という。逆に言えば、有望さの見積もりを用いない探索アルゴリズムは、ヒューリスティック探索が常に定数を返す特別な場合とみなせる。

A*法 (A-star algorithm)
分枝限定法 (branch and bound)

ナップザック問題や巡回セールスパーソン問題などの組合せ最適化問題を考える。例えば、100個ある荷物から、重量が一定以下になるように荷物を選ぶことを考える。$2^{100}$通りから、重量が一定以下かつ価値が最大の組合せを選べばよいが、明らかに計算が終わらない。そこで、この組合せを木に見立てる。木が分岐するとき、その部分問題の全通りを計算するよりも素早く、簡易的な方法で計算を行い、その結果次第では部分問題をスキップして良い場合がある。

例えば0-1ナップザック問題なら、条件を緩めた問題として連続ナップザック問題がある。[^okamotoy_2013]0-1ナップザック問題の解は連続ナップザック問題の解より大きくならない（上界）。そこで、全体の連続ナップザック問題の解と部分問題の解が一致したら、最適値が出たとして計算を打ち切って良いなど、計算対象を限定することができる。[^shioura_2022] [^okamotoy_2013]: 緩和問題とその威力 [^shioura_2022]: 組合せ最適化問題: 分枝限定法

branch_and_bound.ipynbも参照。

簡潔データ構造 (succinct data structure)

競技プログラミングの基礎的な問題では時間計算量を$O(N^2)$未満に抑えれば良いことが多いが、現実で遺伝子情報などの巨大データを扱うと$O(N)$でも実用的でない。更に空間計算量も問題になる。

そこで、空間計算量を最低限に抑えつつ、時間計算量も$O(N)$未満に抑えよう、というのが簡潔データ構造の動機である。ここで最低限とは、理論値に迫ろう、というくらいのニュアンス。

理論値には「情報理論的下限」という名前がついており、データ本体（簡潔表現 (succinct representation)）とインデックス（簡潔索引 (succinct index)）に対してだいたい次のように定義されている。正確な定義は教科書を参照してください。3

ちなみに succinct は「サクスィンクト」と発音し、簡潔な、準備ができた、という意味。

簡潔データ構造の計算モデル

word-RAMという架空のアーキテクチャのマシンを想定する。特徴は次の通り。

ビットベクトル

ビットベクトルのrank演算

rankとは、ビットベクトル中の特定の位置までの0または1を数える処理である。シンプルに実装すると時間計算量が$N$になってしまうので、様々な工夫がなされてきた。

まず、全てのビットベクトルに対してその位置までの1の数をあらかじめ数えて表に記録しておくことを考える。時間計算量は表引きに係る分だけになるが、空間計算量が表の行数($N$)×各行の値を表すのに必要なビット数($log_2{N+1}$)となり、簡潔索引の条件を満たさない。

次に、ビットベクトルの$l$ビットごとに累計の1の数をあらかじめ記録することを考える。ここで試しに$l$を$log_2{N}$とすると、簡潔索引の空間計算量は行数($\frac{N}{log_2{N}}$)×値を表すビット数($log_2{N+1}$) = $N$となり、やはり条件を満たさない。もっと広い間隔で記録する必要があるため、$l$を$(log_2{n})^2$とすると、簡潔索引の空間計算量が$\frac{N}{(log_2{N})^2} \cdot log_2{N+1} = \frac{n}{log_2{N}}$となり、これは条件を満たす。この表の1行を教科書では大ブロックという。

  1. Union-Find の 2 つの工夫 ↩

  2. あなたの知らないハッシュテーブルの世界 ↩

  3. 簡潔データ構造 ↩