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とは「包含」という意味であり、論理で言えば論理包含がこれ
巡回セールスマンの計算量はO(n)というのはなんとなくわかるのですが動的計画法を使った時はO(n^2×2^n)というのが何故だ... - Yahoo!知恵袋
Ｏ（ｎ）で解けたら学術雑誌で大注目を浴びると思うのですが？ 動的計画法の肝は、同じ状態になるルートが多数あるとき一番いいルート以外切り捨てることです。 巡回セールスマン問題の状態は。 今まで通ってきた地点の組み合わせが２＾ｎで今いる地点がｎ通りなので。 動的計画法では ｎ*２＾ｎ通りの状態を考えこれらすべてから次の地点への移動を検証する必要があります。 これをｎ点回りおわるまで続けるのですが、この中で２＾ｎ通りでいらない状態を無視することで計算量をおとせます。 大雑把な計算量がｎ*ｎ*２＾ｎ となるわけです。
Borůvka's algorithm - Wikipedia
Borůvka's algorithm is a greedy algorithm for finding a minimum spanning tree in a graph, or a minimum spanning forest in the case of a graph that is not connected. It was first published in 1926 by Otakar Borůvka as a method of constructing an efficient electricity network for Moravia.[1][2][3] The algorithm was rediscovered by Choquet in 1938;[4] again by Florek, Łukasiewicz, Perkal, Steinhaus,
A* (1968) - Qiita
Deleted articles cannot be recovered. Draft of this article would be also deleted. Are you sure you want to delete this article? 東京大学大学院 総合文化研究科、福永研究室の浅井です。 続いて、探索の高速化に必須の手法、A* (エースター) を紹介します。 Aは「ヒューリスティック探索」とか「発見的探索」と呼ばれます。この名前が悪くて、おかげで、酷い誤解を受けています。例えばあるスライドでは、Aは「近そうなところから探索」と書かれています。なんか適当に探索するかのような印象ですね。A*は、ダイクストラ法を拡張し、 理論的裏付けを持った下界を用いてグラフを探索するための手法 です。 Dijkstra法 の何がタコか Dijkstra法は、最適解を見つけることができる
/proc/cpuinfo: 全点対間最短路を高速に求める
フィックスターズは今年も ACM ICPC つくば大会 にスポンサーとして協賛しております。今年はコンテスト後の懇親会でクイズを出題しているのですが、その問題準備の際に作ったはいいものの結局使われなかったコードが大量に出てきてしまったため、それらをまとめて簡単な解説とともに公開いたします。 全点対間最短路問題 全点対間最短路問題はN個の頂点を持つ有向グラフにおける任意の2点間の最短路を求める問題です。密なグラフの全点対間最短路を求めるアルゴリズムとしてワーシャル-フロイド法が広く知られており、以下のような非常にシンプルなコードで求めることができます。 // 入力: A[i][j] = 頂点iと頂点jを結ぶ辺の重み // 出力: A[i][j] = 頂点iから頂点jまでの最短路の重みの総和 for(int k = 0; k < N; ++k) for(int i = 0; i < N; ++
はてなグループの終了日を2020年1月31日(金)に決定しました - はてなの告知
はてなグループの終了日を2020年1月31日(金)に決定しました 以下のエントリの通り、今年末を目処にはてなグループを終了予定である旨をお知らせしておりました。 2019年末を目処に、はてなグループの提供を終了する予定です - はてなグループ日記 このたび、正式に終了日を決定いたしましたので、以下の通りご確認ください。 終了日: 2020年1月31日(金) エクスポート希望申請期限:2020年1月31日(金) 終了日以降は、はてなグループの閲覧および投稿は行えません。日記のエクスポートが必要な方は以下の記事にしたがって手続きをしてください。 はてなグループに投稿された日記データのエクスポートについて - はてなグループ日記 ご利用のみなさまにはご迷惑をおかけいたしますが、どうぞよろしくお願いいたします。 2020-06-25 追記 はてなグループ日記のエクスポートデータは2020年2月28
問題 I : 乱択平衡二分探索木
東京大学プログラミングコンテスト 2011 問題 L : 𝐿 番目の数字 東京大学大学院情報理工学系研究科 秋葉 拓哉 2011/05/14 東京大学駒場キャンパス 問題概要 • 各ノードに数字が決まってるツリーがある • 以下のタイプのクエリを大量に処理: ある頂点 𝒗 から 𝒘 への経路上の数字で， 𝒍 番目に小さい物を求めよ 頂点番号 頂点 1 に決ま っている数字 例: 頂点 1 から頂点 6 への経路での，3 番目 → 2, 5, 8, 7 の 3 番目 → 7 が答え 問題を変形 • 頂点 1 を根にして，向き付きの木にする • 以下を効率的に計算できるか？ 頂点 𝒗 から根までで 𝒙 以下が何個あるか？ 例: 頂点 4 から根に 6 以下は何個あるか？ → 8, 5, 2 に 6 以下は何個あるか？ → 2 個 それができると？ • それができると，任意の 2 頂
最小カットについて - よすぽの日記
わっけわかんねえほど沢山の制約ドパァな問題を解く一般的なテクとして、 なんかいい感じのグラフを作ったらなんかそれの最小カットが答え というのがあります 最小カットで解ける問題はどんなのなのか考えてみました 頂点がたくさんあって、それを赤と青に塗り分けるという問題を考えます。燃やすと埋めるでも大丈夫です 最小カットで解ける問題というのは、実は 頂点がたくさんある。それを赤と青に塗り分ける。全部の頂点を必ず赤か青に塗らなくてはいけない 必ず赤色に塗らなくてはいけない頂点(Sとする)と青色に塗らなくてはいけない頂点(Tとする)が存在する 「Xが赤で、Yが青の時にZ円の罰金がかかる」という制約が沢山ある 罰金の最小値は？ という問題だけです。 これの解法は、 「Xが赤で、Yが青の時にZ円の罰金がかかる」ならX->Yに容量Zの辺を貼る SからTに最大流 流せた量が答え 処理できる条件は「Xが赤で、Y
最短路問題: 双方向探索(bidirectional search) - 1 - 研究日誌。
前回の記事で登場した双方向探索(bidirectional search)を説明していく。 まずは、通常のダイクストラ法から復習する。P2P最短路問題の終了条件は「終点が探索点となる」ことであり、それまでひたすら幅優先探索的に探索済み範囲を広げていく。 「両方向探索」では、通常のダイクストラ法を２つ同時に走らせるだけのように感じるかもしれないが、その終了条件が多少複雑かもしれない。もちろん単に forward, backward の両方で確定済みになったらではない。 forward, backward それぞれのポテンシャルの更新時に、求めるべきパスの長さの更新を行う。そのパスが更新できなくなれば終了となる。 Df(v) : forward-search におけるポテンシャル(始点からの距離) Db(v) : backward-search におけるポテンシャル(終点からの距離) Qf(v
Spaghetti Source - 木の直径
説明 非負の重みを持つ無向の木が与えられたとき，木の直径，すなわち最遠頂点間距離を求める． アルゴリズム自体はシンプルである．まず適当な頂点 s から探索を行い，最も遠い頂点 u を求める．次に u から探索を行い，最も遠い頂点 v を求める．このとき (u, v) は最遠頂点対である． 実行時間が O( E ) となることは明らかである．探索に深さ優先探索を用いれば，定数も（行数も）小さくすむ．そこで以下アルゴリズムの正当性を証明する． アルゴリズムの正当性のためには，木の最遠頂点対を x, y としたとき，x または y として s からの最遠頂点 u を選んでもかまわないことを証明すれば十分である．s からの最遠頂点を u とし，s からの経路で，u と x が分かれる点を t と置く．y の位置について，次のように場合わけを行う． y が s-t 間にある場合：y を s に取り直
Trianguler
バリバリのグラフ理論 ● 命題：辺の数がMのグラフのなかで最も次数が小さ い頂点の次数は√(2M)を超えない – 頂点の次数というのはそれに繋がっている辺の数↓ –次数の総和は2Mと一致する ● 背理法で証明 – 全て次数が√(2M)以上と仮定 – 頂点数は√(2M)を超える – 次数の総和が2Mを超える
Bellman–Ford algorithm - Wikipedia
The Bellman–Ford algorithm is an algorithm that computes shortest paths from a single source vertex to all of the other vertices in a weighted digraph.[1] It is slower than Dijkstra's algorithm for the same problem, but more versatile, as it is capable of handling graphs in which some of the edge weights are negative numbers.[2] The algorithm was first proposed by Alfonso Shimbel (1955), but is in
Shortest Path Faster Algorithm - PEGWiki
The Shortest Path Faster Algorithm (SPFA) is a single-source shortest paths algorithm whose origin is unknown[see references]. It is similar to Dijkstra's algorithm in that it performs relaxations on nodes popped from some sort of queue, but, unlike Dijkstra's, it is usable on graphs containing edges of negative weight, like the Bellman-Ford algorithm. Its value lies in the fact that, in the avera
SPFAの紹介 - hogloidのブログ
なんかPKUのコードあさると時々見るSPFAというアルゴリズムを紹介します。 SPFAは単一始点の最短経路アルゴリズムで、負辺があっても動作します。 shortest path faster algorithmとかいうたいそうな名前がついてますが、普通はダイクストラに比べ遅いです。 オーダーはO(VE)なんですが、これだけ聞くとベルマンフォードで十分です。 SPFAはqueueを使ってベルマンフォードと大体同じことをします。 始点のコストを0にしてqueueに詰み、 queueが空でない間、そこからつながっている辺について、最短距離を更新できるか考えます。(ダイクストラ法のように) また、ある頂点vがqueueに入っているかの配列を持っておき、すでにqueueに入っているなら最短距離を更新するだけです。 最短距離を更新できて、queueにないならqueueに入れます。 ちょっと想像すると、
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
データ構造とアルゴリズム - 第十二回
色々なダイクストラ高速化
コスト行列とハンガリー法
http://www.bunkyo.ac.jp/~nemoto/lecture/mathpro/2002/dual2002.pdf
Advanced Algorithms and Applications