スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

勉強予定のアルゴリズム

今後、勉強予定のアルゴリズムのリスト。
自分用。
ここに書いたのは、少しでも達成率を上げるため。

Tag : misc

コンテストで、アルゴリズムを知らないと手が出せない問題がたまに出てきて悲しくなるので、有名アルゴリズムを勉強する。

具体的には、今まで避けてきたりなんとなくで書いていたものを、簡潔に書き下してライブラリ化する。
おおよその目安としては、5 月末までに半分くらいは消化したい。
  • 最大流 (Ford-Fulkerson の DFS による実装) OK
    使う機会がないのでライブラリ化しないことにした。いつでも書ける。

  • 最大流 (Edmonds-Karp) 2011/10/23 OK
    隣接行列に逃げずに、ちゃんと隣接リストで書いた。
    グラフを隣接リストでもつときに逆辺をどのように参照するのかは、蟻本のコードが参考になる。

  • 最大流 (Dinic) 2012/07/26 OK
    STL 使わないやつ。速い。SPOJ の FASTFLOW が 2.31 sec。

  • 二部グラフの最大マッチング 2011/??/?? OK
    実質、最大流と同じだけど、二部グラフ用に最適化する
    同じコードを 2 回書きたくないので最適化しないことにした
    隣接行列versionと隣接リストversionの最大流を両方とも作っておいて、速度がほしいときは隣接リストversionを使うようにする

    二部グラフ用のコードを書くことにした。
    Greedy に交互道を見つける O(|V|(|V|+|E|)) 時間のアルゴリズム。

  • 二部グラフの最大マッチング (Hopcroft-Karp) 2012/03/07 OK
    速い。

  • 最小費用流 2011/10/23 OK
    隣接リスト版の Primal-Dual 法。

  • 有向グラフの強連結成分分解 (Kosaraju) OK
    ライブラリ化しない。

  • 有向グラフの強連結成分分解 (Tarjan) 2012/06/03 OK
    lowlink すごい。

  • 一般グラフの最大マッチング (Edmonds)

  • 単一始点最短路 (Bellman-Ford) 2011/05/?? OK
    なぜ動くのかまだ理解できてない。だから空で書けない。
    理解した。
    単純に辺を緩和しているだけだった。
    最短路は同じ頂点を 2 回は通らないことから、|V|-1 回の反復で十分ということか。
    動作を理解する上では、dist[k][u][v] みたいな 3 次元の配列で考えたほうがわかりやすい。

  • FFT
    最近では、Facebook Hacker Cup Round 2, CodeChef March (Long) で出題された。

  • Fenwick Tree 2011/04/09 OK
    数列の転倒数の計算など。汎用性が高い。

  • Segment Tree
    一応書いたけど、使い勝手が微妙かもしれない。

  • Suffix Tree

  • Suffix Array 2011/12/23 OK
    Larsson-Sadakane もどきの build と線形時間の LCP。
    Spaghetti Source のを参考にした。
    あと、SA-IS も論文のコードほぼそのままだけどライブラリ化した。こっちは動作が理解できてない。

  • Trie

  • Knuth-Morris-Pratt 2012/08/09 OK
    やっと重い腰を上げてライブラリ化した。正しく動作する細かい理由までは把握しきれてないけど、雰囲気はわかるし応用する問題もいくつか解いた。

  • Aho-Corasick

  • Voronoi 図
    本当にこれが必要になる問題なんてまず出ないんでは!!?

  • 最長回文 (Manacher) 2011/08/03 OK
    最近では CodeChef March Cook-off で出題された。

  • Range Minimum Query (Segment Tree)
    使い勝手をよくしたい。

  • Range Minimum Query (Sparse Table) 2012/02/09 OK
    Spaghetti Source で言及されているようにメモリを節約することもできるけど、そこまでやる必要性は低いと思う。なんだかんだで一クエリ O(log n) のしか作ってない。O(1) のもあったほうがいいかなぁ。

  • Lowest Common Ancestor 2012/10/28 OK

  • 最小 Steiner 木 (Dreyfus-Wagner) 2012/01/09 OK
    どういう DP をしているのかはわかったけど、なぜそれで最適解が求まるのかは理解できていない。

  • Union-Find 2011/04/25 OK
    経路圧縮は実装済み。ランクによる平衡処理を追加する。
    できたら、計算時間がシビアな問題をどこかから持ってきて、どのくらい改善されたかを計ってみたい。

    実装した。時間を計ってみたところ、ランク処理を追加したほうが少し遅くなった。残念。

  • baby-step giant-step 2012/02/23 OK
    そんなに難しくない。
    a, c, m : given のとき a^b = c (mod m) なる b を求める問題で、a と m が互いに素でないときもこの方法を拡張すれば解けるらしいけど未解決。こっちは難しい。

  • 線形計画法

  • 整数計画法

  • 最小有向全域木 2012/10/10 OK
    再帰的に SCC するやつを書いた。

  • 無向グラフの全域最小カット 2012/10/10 OK
    アルゴリズムは意外とシンプルだった。



リストの漏れに気付いたら、適宜追加する。


2011/10/24 : いっぱい追加
2012/01/09 : 最近、離散対数の問題に二回も出会ったので追加
2012/03/07 : LP と IP を追加
2012/10/10 : 二つ追加
スポンサーサイト

コメントの投稿

非公開コメント

プロフィール

fura2

Author : fura2
数学・コンピュータを中心に、考えたこと・やったことを書いていきます。

誤植等を含め、間違いはご指摘いただければ幸いです。

FC2カウンター
検索フォーム
最新記事
最新コメント
最新トラックバック
月別アーカイブ
リンク
RSSリンクの表示
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。