最小費用流の負辺除去 - あなたは嘘つきですかと聞かれたら「YES」と答えるブログ
つい最近まで最小費用流の負辺除去、「なんか上手いことやれば出来ることもあるらしい」程度の認識だったんですが、ちゃんと考えてみたら自明やんってなったので書いておきます。 この記事を読めば多分、自明かどうかはともかくとして、かなり見通しがよくなるのでは思います。 （2019-06-27に若干書き換えました） 追記 (2021-08-15)： ポテンシャルを求めるのが簡単な場合にはそれを使って負辺除去する方が楽です。 この記事の方法はグラフが複雑だったり、思考停止したいとき用かなぁ。 例題 最小費用流への認識 最小費用流は「始点 S から終点 T に水を流す」という問題に見えがちですが、それは少し本質とずれています。 水の例えを用いつつ言うならば「頂点間で水をやりとりして過不足を補い合う」という感じでしょうか。 実装の際に始点と終点があった方が分かりやすいことがあるだけで、定義上は必要なものでは
Linear-time Kernelization for Feedback Vertex Set - wataの日記
https://arxiv.org/abs/1608.01463 が ICALP 2017 に採択されたので内容の解説をします． 概略 取り除くと残りが無閉路になる頂点集合を Feedback Vertex Set (FVS)と言い，与えられた無向グラフの最小FVSを求める問題をFVS問題と言います．これは有名なNP困難問題で，FPTアルゴリズムという理論アルゴリズムの研究分野で盛んに研究されており，PACE Challenge*1 というFPTアルゴリズムの実性能を競うコンテストの記念すべき第一回目 (2016年) の題材として選ばれました (ちなみに2017年のコンテストは 5/1 締め切りでまだ間に合うので興味のある方はぜひご参加ください)．この問題に対して，答えが$k$ (頂点数$n$に対してかなり小さいと想定)の時に $4^k n^{O(1)}$ 時間で動作するアルゴリズムを以前
組合せ最適化を使おう - Qiita
野菜の選び方はナップサック問題、乗り換え駅探索は、最短路問題といいます。典型問題は、よく研究もされているので、多くの場合、効率的な解法があります。あるいは、定式化がされているので、すぐ解くことができます。あとで、やってみましょう。ここで、あげている全ての典型問題の実行例は、典型問題と実行方法をご覧ください。 汎用問題 最近、私がやっているコンテナの仕事のお話しをします。 世界中の人たちが、いろいろなものを安く買えるのはコンテナ輸送のおかげです。中国などで生産したものを日本やアメリカやヨーロッパに、大量に安く運べるからです。でも、空のコンテナが、どんどんたまります。また中国に戻さないといけません。いつ、どこからどこに戻すかを決めるのが、最小費用流問題になります。ところが、最小費用流問題で表せない制約条件もあります。1 つが、カボタージュとよばれるものです。カボタージュというのは、国内のみの輸
最小カットを使って「燃やす埋める問題」を解く
3. 2. 燃やす埋める問題 引用:Komakiさんのページ http://topcoder.g.hatena.ne.jp/CKomaki/20121019/1350663591 3. FoxAndGo3 引用:TopCoder - SRM594 Div1 Medium http://community.topcoder.com/stat?c=problem_statement&pm=12808&rd=15706 4. The Year of Code Jam 引用:Google Code Jam World Finals 2008 E （プログラミングコンテストチャレンジブック P357） https://code.google.com/codejam/contest/32011/dashboard#s=p4 5. Surrounding Game 引用:TopCoder - S
ネットワークフロー入門
ネットワークフロー入門 保坂 和宏 (東京大学理学部数学科) 第 14 回 JOI 春合宿 2015/03/19-20 1 前置き • ネットワークフローに関する理論的な興味 グラフの難しそうな問題が多項式時間で解ける！ 応用範囲が広い 賢い高速化もいろいろ • 副産物的な発見もある 2 前置き • プログラミングコンテストにおけるネットワークフロー 「問題からうまいことグラフを構成してフローを流して解く」 というパターンが多い • うまいグラフを作るのにひらめき or 経験が重要，ということでコ ンテストにお似合い • フローの部分は皆事前にコードを書いてある (または頭に入ってい る) という風潮あり 二部グラフへの応用 (最大マッチングなど) はそれだけで強力な 道具 • 複雑な貪欲法を回避できることがしばしばあります ICPC, topcoder, Code
日本橋ハーフマラソン本戦B 日本橋大渋滞 解説 - koyumeishiのブログ
日本橋ハーフマラソン本戦B 日本橋大渋滞 解説 先日 RCO が主催したプログラミングコンテスト 日本橋ハーフマラソン のオープンコンテストに参加しました。 オープン参加で賞金もレートもかかっていなかったのでA問題は放棄して、 ビジュアライザが用意されていた B問題 日本橋大渋滞 を解こうとしたのですが、実装が間に合わず未提出、0点のままコンテストは終了してしまいました。 後日考えていた方針の実装を終わらせ提出したところ、かなり出来のいい点数を出せたのでその振り返りをします。 2017/03/26 時点で一位 http://rco-contest-2017-final-open.contest.atcoder.jp/submissions/1176109 入力例2 74手 46555点 おおよその方針は次の一連のツイートの通りですが、もうちょいと詳しく解説。 天才過ぎて70手ぐらいまでにな
グラフとネットワーク - okamoto7の日記
明日から『グラフとネットワーク』という講義が始まるので，いろいろと思うことを書いておく． まず，このような授業をやることを依頼されて，それでシラバスとか考えて，立ち上がったわけだけども，この講義の名前が『グラフ理論』になりそうだったが，それは避けられた．もっとも，『グラフ理論』をやってもよいわけだし，私が『グラフ理論』の講義をすることもできるし，実際『グラフ理論』の講義もやったことがあるのだけれども，この『グラフとネットワーク』は「グラフ理論」の講義ではない．実際依頼された内容を考えれば『グラフ理論』などという名前を付けることは，学生に対して間違った印象を与えるだけで，害悪であるとさえ思える． よく大学の講義名に「○○」のあとに「理論」をつけて『○○理論』としてしまうものがあるが，それが本当に「○○理論」なのかどうかということを反省する必要がある．日本の大学において『グラフ理論』という名前
Googleの旅行アプリで使われている280年前のアルゴリズムとは？
By Celeste RC Googleが2016年9月20日にリリースした「Google Trips」は旅行に関する情報をまとめて管理できるアプリで、目的地までの移動方法や行き方、移動時間、観光地の場所や付近にあるレストランなど、さまざまな情報を元にして旅行の計画表を自動で作ることができます。Googleによれば、このGoogle Tripsに使用しているアルゴリズムは280年前のものを元にしているとのことで、その詳細をGoogleが公式ブログで明かしています。 Research Blog: The 280-Year-Old Algorithm Inside Google Trips https://research.googleblog.com/2016/09/the-280-year-old-algorithm-inside.html Google Trips - Google Pl
爆速ナンバーリンクソルバー（1）〜ナンバーリンクと充足可能性問題 - Qiita
Deleted articles cannot be recovered. Draft of this article would be also deleted. Are you sure you want to delete this article? 先ほど、ブラウザで動くナンバーリンクソルバー（http://jkr2255.github.io/js_puzzle_solvers/numberlink.html）を公開しました。それについてまとめようと思ったのですが、1本の記事に書くには長すぎるので、少しずつ分けて書いていこうと考えています。 まずは、問題そのものである「ナンバーリンク」と、それの解法に使った「充足可能性問題」について解説します。 まず、「ナンバーリンク」って？ ナンバーリンクは、数独やクロスワードといった、（もともとは）紙と鉛筆で楽しむ「ペンシルパズル」の一種です。
2-SATと強連結成分分解 - naoya_t@hatenablog
ふと2-SATの事が気になって、復習がてらPractice RoomでSRM464のDiv1 Medium問題を開いてみた。（ちなみにSRM464には出場している） SAT (充足可能性問題, SATisfiability problem) についてはここの読者の皆さんはご存知とは思います。NP完全問題でおなじみのあれです (x_0 ∨ ¬x_1) ∧ (¬x_0 ∨ ¬x_3) ∧ ... みたいな論理式（乗法標準形）を満たす真偽値 x_0, x_1, ... の組み合わせが存在するか否か。（存在する場合、その組み合わせを知りたかったりする） 上の例ではすべての節が(高々)2変数なので2-SATと呼ばれる。 （2-SATは線形時間で解けるらしい）。 論理和 x ∨ y が論理包含 ¬x⇒y （または ¬y⇒x）に書き換え可能なことを利用して、論理式を有向グラフに変換してみたり 出来上がっ
2-SATを解いた時のメモ - TopCoderとJ言語と時々F#
2-SATとは SATとはsatisfiability(充足性)の略で、与えられた論理式を満たす真偽値の組合せが存在することをいう。 特に2-SATとは、変数がx_1からx_nまであるとして以下の形の論理式について変数の真偽値の組合せを考える問題である。 ここで 論理積でつながれたひとつひとつの部分(節)に変数が二つある(節の長さが2である)ので2-SATという。 2-SATの解法について 2-SATに対しては、節の数と変数の数に対する線形時間のアルゴリズムが存在する。ちなみに節の長さが3以上の場合この問題はNP完全に属する。 2-SATを解くにはImplication graphというグラフを構築する必要がある。次節でこのグラフについて述べる。 Implication graphの構築 Implication Implicationとは「包含」という意味であり、論理で言えば論理包含がこれ
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
http://www.logopt.com/python_learning/wp-content/uploads/2014/05/mipproblem2.pdf
SSSSLIDE
グラフネットワーク〜フロー&カット〜
最小費用フロー問題
最適化基礎 第11回 最小費用流問題 最大重みマッチングとオークション
数理計画法 第9回 ネットワーク最適化 3. 最小費用フロー問題
ダイクストラ法典型問題集 - Google ドライブ
巡回セールスマン問題の近似アルゴリズムについて
2-SAT Tutorial - Codeforces