アルゴリズムとライブラリ

アルゴリズムとライブラリ
eX(ry
グラフ

とりあえず定番






Dijkstra, Warshall-Floyd, Bellman-Ford
Prim, Kruskal
Union-Find
安定結婚マッチ
二重連結成分, 強連結, Topological sort
この辺は質問ないでしょ？
グラフ-フロー

フローについては綿密に調べ上げました


結果的にこれが仇となったわけですがorz
結論：通常のフロー問題ではFord-Fulkersonで
十分



Maxflow (Ford-Fulkerson)
Bipartite match (Ford-Fulkerson)
Min-cost flow (Ford-Fulkerson)
フローのアルゴリズム達

Ford-Fulkerson系




増加可能パスを探し、その方向にフローを増やす
実装が直感的、コードも短い
実用上は悪い(フローの幅によっては終了しない)
Goldberg-Tarjan系



とにかく始点から流して、後で余った分は戻す
コードは中程度のサイズ
実用上高速
選択とその理由



我々はすべてFord-Fulkerson法で統一しました。
理由：「本番で修正しやすい」
ICPCではアルゴリズムを修正して適用すること
が多いので、これが必要
フローの幅？


幅が無理数の場合にどうするのか？
Ford-Fulkersonは終了しない


整数ならO(VE2)だが…
解決法： Ahuja-Orlin’s algorithm


216のフローが流せるか、215のフローが流せるか、…
を順にチェック
O(E2 logU)になる
実装

4回ほど書き直してrefineしています


150行 → 70行 → 50行 → 40行未満
一番大きかったのは会長ライブラリの衝撃
最小費用フロー

Dijkstraを使うもの(PrimalDual法)で実装



ここでBellmanFordにしてれば…orz
結果的に修正されたので、後でライブラリを公開しま
す
O(V3U log V)
リサーチの結果

通常の最大流ではGoldberg-Tarjanが理論最速。
実装もそれほど長くない


強多項式時間、メモリ使用も僅少
ICPC過去問では基本的にFord-Fulkersonです
べて通る


UVA 820 (Finals 2000) はFord-Fulkersonの方が速
い
ただし、G-Tならジャッジの意図していない解法で通
すことができる可能性がある
リサーチの結果

最小費用流については最適なアルゴリズムとい
えるものがまだ存在しない


どうしてもU（フロー幅）またはC（コスト）に依存
擬多項式のものは比較的簡単に実装できる

Goldberg-Tarjan O(V3 log(VC))


Orlin O(V3 log(UV))



高速且つ比較的使いやすい
アルゴリズムは単純だが問題を標準型に変換するのが大変
強多項式のものは事実上実装不可能
負サイクルキャンセル（プライマル法）は遅い
その他グラフライブラリ

いろいろ調べて（時には実装して）不要だと結論
づけたもの


Min-cut algorithm (Karger’s)
Graph isomorphism




Tree isomorphism
K shortest path problem
Euler回路(Hierholzer’s)
集合カバー近似アルゴリズム
数理


Gaussの消去法
中国剰余定理と拡張互除法
線形計画は？

結論としては「combat’s heuristicsで十分」


不安があったとしても非線形最適化の方があら
ゆる点で優秀



タブロー法は低速且つ非効率すぎる
共役勾配法があれば最高だが、最急降下法で十分な
気がする。
反復法は丸め誤差に強い
数理系は反復アルゴリズムにした方がいろいろ
と安定しているのではないか？
幾何

凸包



正直かなり自信があります
交差判定
多角形ポリゴンのクリッピングと拡大縮小
幾何

線分アレンジメント


線分による線分の分解
Interval tree

実装できてしまった
不要だったもの

台形分割



ドロネー(Delaunay)三角形分割


かなり厳しい。コード長が200行ぐらいになる
その割に使いどころが「日本地区大会幾何最終防衛
問題を力業で突破」ぐらい
これも長い割に使いどころがない
立体幾何

まずもって何かしらアルゴリズムを用意することその
ものが無意味
幾何

全体的に幾何の需要は下がっている？

正直、まともな問題を作っているのは日本の地区大
会だけではないだろうか？
文字列

KMP


再帰降下パーザ


あの日の過ちを教訓に
ほとんどはLL(1)で充分。LL(∞)は不要？
Split, join, etc
Suffix Array

結局M&Mを実装


実体はNirm○dからのパクリ
Radix sortを使わないとやはり遅かった
その他

Aho-Corasick


検証が間に合わずライブラリには入らなかった
BM

ICPCでは不要なので捨てた
その他


範囲更新, LIS, date2days, etc.
今後GCC4が使えると、SGIの非標準ライブラリ
が使える

Download Report