読者です 読者をやめる 読者になる 読者になる

テストステ論

高テス協会会長が, テストステロンに関する情報をお届けします.

初級グラフアルゴリズムをまとめてみる

一週間前から集中的にプロコン勉強をしている. まるで受験生だ. 楽しい.

とりあえず, 以下の3冊の本をざっくり見ると, カバーする範囲において, 蟻本(<=初級) =~ ALDS(全部) =~ 最強最速(全部)というのが大体成り立つと分析した. すなわち, この範囲が極めて大切だということだと解釈した.

時間的に, 蟻本の中級以上の範囲を学ぶことは不可能だし, どうも体系立ってない領域に思えたので, 学習方針としては, 初級範囲をきっちり学んで, それで落ちたら諦めるということにした.

さて, 初級において特に重要なことは,

である. 初等的なグラフアルゴリズムの多くがDPであることから分かるように, この2つは非常に密接に関わっている. プロコンの問題として作りやすいからか, これらに関連した問題が頻繁に出される. この2つを初等的なレベルでもマスターすれば, ARCで2完未満になることはまずないと思うし, 3完にもチャレンジ出来ると思う(たぶん, 4完は無理だろう). 今後もARCにチャレンジしていこうと思う.

以下では, 初等的なグラフアルゴリズムについて, 私の理解を示す. もし追記すべきこと, 誤ってる箇所があったらTwitterか何かで指摘してほしい.

Union Find

グラフを連結集合に分解するために使う. このためには, dfs/bfsなどを使っても出来ると思うが, Union Findが楽. プロコンほぼ必携.

Bellman Ford法

最短経路問題(グラフ上の始点sが与えられた時に, グラフ上の各点への最短経路/距離を求める)を解くとてもナイーブなアルゴリズム. O(|V|*|E|)

d[i] = min(d[j] + cost(j, i))を利用して, 全エッジについてこの漸化式が収束するまでループさせる. エッジ重みが負であっても適用可能.

Dijkstra

最短経路問題を解くアルゴリズム.

その中においては最短経路が確定しているノード集合S(<V)を拡大していく. 考え方はBellman Fordと同じ. あるノードを選んだ時, そのノードへのsから距離がSにおいて最短であったならば, その後どういうノードをSに追加しても, そのノードを経由することでS内のノードへの最短距離が更新されることはあり得ないという原理に基づく(もしそうであればもっと先に追加されてるはずだ!).

Sを拡大する戦略として, sからの仮の距離がもっとも短いものを選択する(故にこれが本当の最短距離. なぜならば他のノードを経由して距離を更新出来ないから)ことにしているため, priority queueを使って実装することで実装を最適化出来る(ただし, C++のpriority queueは大きいものをpopするので, デフォルトのcomparatorを上書きする必要がある)

通常はO(|V|^2). priority queueを使うと O(|E| log |V|).

Prim法

最小全域木(Mimimum Spanning Tree. グラフにおいて, すべてのノードを通過し, かつ, エッジのコスト和が最小な木)を計算するアルゴリズム.

Dijkstra法とほぼ同じ. 今度は, Sから見て, 最短のエッジを追加していく. 適当な証明の理解としては, 以下のような感じ.

  1. 仮に最小全域木が求まったとする.
  2. その木の末端のノードを除いたノード集合をSとする.
  3. 仮にアルゴリズムの途中でそのSが求まっていたとする.
  4. この時, Sからその末端のノードに至るエッジが, 最短距離のエッジであることは疑わないでしょう.

Prim法はDijkstra法同様, ナイーブではO(|V|^2). priority queueを使うとO(|E| log |V|)となる.

Kraskal法

Prim法同様, 最小全域木を求めるアルゴリズム. エッジをコスト昇順にソート. 閉路が出来ないようにエッジを追加していけばなぜか最小全域木が出来上がってる. 閉路が出来てるかの判定にはUnion Findを使う(追加しようとするエッジの端点がすでに同じ連結集合に属していたら, 追加出来ない).

証明は, Prim法において, エッジの追加順を入れ替えましたというだけ. Prim法でやった場合もどの道追加することになるエッジを, ばらばらに追加していく. オーダは, 最初のソートが一番重くてO(|E| log|E|).

Warshall Floyd法

全点対最短経路問題を解くアルゴリズム. FOR(k, V) FOR(i, V) FOR(j, V) d[i][j] = min(d[i][j], d[i][k] + d[k][j]);の三重ループで計算量はO(|V|^3)

意味するところは, kをいうノードを経由することで最短距離を更新出来ないか?を問い続ける. 新しいkを追加した場合は, 当然だが内側の二重ループを回せばよく, O(|V|^2).

実装が簡単なので, 計算量に余裕がある(つまり|V|がせいぜい100とか小さい)場合はこれを使って単一最短経路を求めても良いと蟻本には書いてある.

今後のプロコン計画

プロコンが就職にとても重要ということがわかったので, 今後も勉強を進めていく. まずは蟻本に書いてあることを上級編まで完全に理解することだろうと思う. これはまぁまぁ時間がかかると思う. コンテストとしてはARCで30番以内に入ることが当面の目標. プロコンは重要だ. カーネルの外におけるプログラミングでは, プロコン的なアルゴリズムの知識が必須となる. 炎上から始まった転職活動でたまたまプロコンが必要になって, その重要さに気づけたので, 長期的にみると炎上してむしろ良かったんじゃないかな.