アルゴリズムとライブラリ eX(ry.

Presentation on theme: "アルゴリズムとライブラリ eX(ry."— Presentation transcript:

1 アルゴリズムとライブラリ eX(ry

2 グラフ とりあえず定番 この辺は質問ないでしょ？ Dijkstra, Warshall-Floyd, Bellman-Ford
Prim, Kruskal Union-Find 安定結婚マッチ 二重連結成分, 強連結, Topological sort この辺は質問ないでしょ？

3 グラフ-フロー フローについては綿密に調べ上げました 結論：通常のフロー問題ではFord-Fulkersonで十分
結果的にこれが仇となったわけですがorz 結論：通常のフロー問題ではFord-Fulkersonで十分 Maxflow (Ford-Fulkerson) Bipartite match (Ford-Fulkerson) Min-cost flow (Ford-Fulkerson)

4 フローのアルゴリズム達 Ford-Fulkerson系 Goldberg-Tarjan系 増加可能パスを探し、その方向にフローを増やす
実装が直感的、コードも短い 実用上は悪い(フローの幅によっては終了しない) Goldberg-Tarjan系 とにかく始点から流して、後で余った分は戻す コードは中程度のサイズ 実用上高速

5 選択とその理由 我々はすべてFord-Fulkerson法で統一しました。 理由：「本番で修正しやすい」
ICPCではアルゴリズムを修正して適用することが多いので、これが必要

6 フローの幅？ 幅が無理数の場合にどうするのか？ Ford-Fulkersonは終了しない
整数ならO(VE2)だが… 解決法： Ahuja-Orlin’s algorithm 216のフローが流せるか、215のフローが流せるか、…を順にチェック O(E2 logU)になる

7 実装 4回ほど書き直してrefineしています 150行 → 70行 → 50行 → 40行未満 一番大きかったのは会長ライブラリの衝撃

8 最小費用フロー Dijkstraを使うもの(PrimalDual法)で実装 ここでBellmanFordにしてれば…orz
結果的に修正されたので、後でライブラリを公開します O(V3U log V)

9 リサーチの結果 通常の最大流ではGoldberg-Tarjanが理論最速。実装もそれほど長くない
強多項式時間、メモリ使用も僅少 ICPC過去問では基本的にFord-Fulkersonですべて通る UVA 820 (Finals 2000) はFord-Fulkersonの方が速い ただし、G-Tならジャッジの意図していない解法で通すことができる可能性がある

10 リサーチの結果 最小費用流については最適なアルゴリズムといえるものがまだ存在しない どうしてもU（フロー幅）またはC（コスト）に依存
擬多項式のものは比較的簡単に実装できる Goldberg-Tarjan O(V3 log(VC)) 高速且つ比較的使いやすい Orlin O(V3 log(UV)) アルゴリズムは単純だが問題を標準型に変換するのが大変 強多項式のものは事実上実装不可能 負サイクルキャンセル（プライマル法）は遅い

11 その他グラフライブラリ いろいろ調べて（時には実装して）不要だと結論づけたもの Min-cut algorithm (Karger’s)
Graph isomorphism Tree isomorphism K shortest path problem Euler回路(Hierholzer’s) 集合カバー近似アルゴリズム

12 数理 Gaussの消去法 中国剰余定理と拡張互除法

13 線形計画は？ 結論としては「combat’s heuristicsで十分」 不安があったとしても非線形最適化の方があらゆる点で優秀
タブロー法は低速且つ非効率すぎる 不安があったとしても非線形最適化の方があらゆる点で優秀 共役勾配法があれば最高だが、最急降下法で十分な気がする。 反復法は丸め誤差に強い 数理系は反復アルゴリズムにした方がいろいろと安定しているのではないか？

14 幾何 凸包 正直かなり自信があります 交差判定 多角形ポリゴンのクリッピングと拡大縮小

15 幾何 線分アレンジメント 線分による線分の分解 Interval tree 実装できてしまった

16 不要だったもの 台形分割 ドロネー(Delaunay)三角形分割 立体幾何 かなり厳しい。コード長が200行ぐらいになる
その割に使いどころが「日本地区大会幾何最終防衛問題を力業で突破」ぐらい ドロネー(Delaunay)三角形分割 これも長い割に使いどころがない 立体幾何 まずもって何かしらアルゴリズムを用意することそのものが無意味

17 幾何 全体的に幾何の需要は下がっている？ 正直、まともな問題を作っているのは日本の地区大会だけではないだろうか？

18 文字列 KMP あの日の過ちを教訓に 再帰降下パーザ ほとんどはLL(1)で充分。LL(∞)は不要？ Split, join, etc

19 Suffix Array 結局M&Mを実装 実体はNirm○dからのパクリ Radix sortを使わないとやはり遅かった

20 その他 Aho-Corasick 検証が間に合わずライブラリには入らなかった BM ICPCでは不要なので捨てた

21 その他 範囲更新, LIS, date2days, etc. 今後GCC4が使えると、SGIの非標準ライブラリが使える