2-SATと強連結成分分解
ふと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)に書き換え可能なことを利用して、論理式を有向グラフに変換してみたり
- 出来上がったdagを強連結成分分解してみる
- 同じ強連結成分に含まれるノード(が表すリテラル、すなわちxなり¬yなり)は同じ真偽値をもつ。ということは、xと¬xが同じ強連結成分に含まれたらアウト。
2-SATも強連結成分分解も、蟻本§4-3「グラフマスターへの道」(p.285〜) で解説されている(のを以前読んだがすっかり忘れている。p.286のグラフをノートに書いてscc()を手動トレースして一度は納得したはずなのだが)。
マイナビ
売り上げランキング: 40,311
参考
Medium ("ColorfulDecoration", 550)
この問題で何が x ∨ y にあたるのか思いつかない…orz
http://d.hatena.ne.jp/komiyam/20110925/1316920692 を見たら、
「x と y が共存できない」¬(x ∧ y) が ¬x ∨ ¬y に等しいことを利用すればいいらしい。
するとこれは 「x⇒¬y かつ y⇒¬x」に書き直すことができる。
書いてみたコード
- 強連結成分分解ではなく、x から ¬x に行く経路(とその逆)が存在するかをWFで求めている。O(n^3)ですけど。
- passed system test
#include <vector> using namespace std; #define rep(var,n) for(int var=0;var<(n);++var) #define all(c) (c).begin(),(c).end() #define tr(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i) #define mid(x,y) ((x)+((y)-(x))/2) #define ev(v1,v2,n) for(int v1=0;v1<(n)-1;++v1)for(int v2=v1+1;v2<(n);++v2) vector<int> xa_, ya_, xb_, yb_; vector<vector<int> > arc; int n; inline bool intersects(int xi, int yi, int xj, int yj, int d){ int dx = abs(xi - xj), dy = abs(yi - yj); return (dx < d && dy < d); } inline void add_edge(int i, int j) { // ¬(i ∧ j) // ¬i ∨ ¬j // (i ⇒ ¬j) かつ (j ⇒ ¬i) arc[i][j<n ? j+n : j-n] = 1; arc[j][i<n ? i+n : i-n] = 1; } bool po(int d){ if (d == 0) return true; arc.assign(n*2, vector<int>(n*2, 10000)); rep(i,n*2) arc[i][i] = 0; ev(i,j,n) { if (intersects(xa_[i],ya_[i], xa_[j],ya_[j], d)) { // i && j が駄目 add_edge(i, j); } if (intersects(xa_[i],ya_[i], xb_[j],yb_[j], d)) { // i && ¬j が駄目 add_edge(i, n+j); } if (intersects(xb_[i],yb_[i], xa_[j],ya_[j], d)) { // ¬i && j が駄目 add_edge(n+i, j); } if (intersects(xb_[i],yb_[i], xb_[j],yb_[j], d)) { // ¬i && ¬j が駄目 add_edge(n+i, n+j); } } rep(k,n*2) rep(i,n*2) rep(j,n*2){ arc[i][j] = min(arc[i][j], arc[i][k] + arc[k][j]); } rep(i, n) { if (arc[i][n+i] < 10000 && arc[n+i][i] < 10000) return false; } return true; } class ColorfulDecoration { public: int getMaximum(vector<int> xa, vector<int> ya, vector<int> xb, vector<int> yb) { n = xa.size(); xa_ = xa; ya_ = ya; xb_ = xb; yb_ = yb; int lo = 0, hi = INT_MAX; while (true) { int mi = mid(lo, hi); if (mi == lo) break; if (po(mi)) lo = mi; else hi = mi; } return lo; } };
さて。
強連結成分分解をちゃんとやってみよう。
dagの強連結な部分集合:「有向グラフの部分集合のうち、それに含まれる任意の2頂点u, vを取った時 uからvへ辿り着く有向路が存在する」
強連結成分:強連結な部分集合のうち、これ以上頂点を付け足したら強連結でなくなってしまうもの
最大クリーク(無向グラフで、あらゆる2つの頂点を繋ぐ辺が存在する集合(=クリーク)のうち、これ以上頂点を付け足したらクリークでなくなってしまうもの)に似ている。
vector<vector<int> > arc; vector<vector<int> > arc_r; vector<int> cmp; // 属する強連結成分の、グラフ全体におけるトポロジカル順序 vector<bool> visited; vector<int> vs; // post-order void dfs(int v) { visited[v] = true; tr(it, arc[v]) { if (!visited[*it]) dfs(*it); } vs.push_back(v); // 帰りがけにvを記録。グラフの末端に近いものから並ぶ } void rdfs(int v, int k) { visited[v] = true; cmp[v] = k; tr(it, arc_r[v]) { if (!visited[*it]) rdfs(*it, k); } } int scc() { // 強連結成分分解 vs.clear(); visited.assign(n*2, false); rep(i,n*2) { if (!visited[i]) dfs(i); } visited.assign(n*2, false); int k=0; reverse(all(vs)); // グラフの末端から遠いものから始めたい tr(it, vs) { if (!visited[*it]) rdfs(*it, k++); } return k; } bool po(int d){ if (d == 0) return true; arc.assign(n*2, vector<int>()); arc_r.assign(n*2, vector<int>()); // 追加 cmp.assign(n*2, -1); // 追加 ev(i,j,n) { if (intersects(xa_[i],ya_[i], xa_[j],ya_[j], d)) { ... } scc(); // 強連結成分分解 rep(i, n) { // x と¬x が同じ強連結成分に属してしまったらアウト if (cmp[i] == cmp[n+i]) return false; } /* // 式を満たす具体的な真偽値を求める方法。 //「 x を含む強連結成分のトポロジカル順序 cmp[x] が、¬x を含む強連結成分のトポロジカル順序 cmp[¬x] よりも後ろ」⇔「xは真」 vector<bool> ans(n); rep(i, n) { ans[i] = (cmp[i] > cmp[n+i]); } cout << ans << endl; */ return true; }
ショートコーディング「世界を革命する力を」
ふとしたツイートからコードゴルフ大会が勃発
もくし
くしも
しもく
くもし
もしく
しくも
という6行(UTF-8を想定)を出力するCプログラムって最短何バイトまで縮められるだろうか
— naoya t (@naoya_t) 2013, 7月 2
続きを読む
MacBook Airの電源アダプタが断線すると読書が捗る
MacBook Air (13-inch, Mid 2011) のACアダプタ(45W) の根本が断線した。残りバッテリ47分なので新バッテリを得るまで暫く休業…
— naoya t (@naoya_t) 2013, 6月 29
でMacが使えなかったので、週末は「きつねさんでもわかるLLVM」とか「Real World OCaml」とか読んでました。
Oreilly & Associates Inc
売り上げランキング: 31,941
Real World OCamlはβ版(HTML、無料)のやつですけど。
電源アダプタは互換品をポチりました。
売り上げランキング: 529
graph-tool(のMacへのインストールに挫折してvagrantと戯れるの巻)
Pythonでグラフの最小カットを計算しようと思ったのだけれど、Wikipediaから拝借してきた最大フローを求めるFord-Fulkersonコードを元に書いたものでイマイチ速度が出なかった*1ので、速いと噂の
graph-tool
を試してみることにした。
brewで入れるとか、easy_installで入れるとか色々試したけれど自分のMac環境では依存関係のあちこち(Boost, CGAL, cairo, ...)で軒並み引っかかってビルドに失敗する。
Ubuntuだとapt-getで一発で入ったのに。
時間も気力も溶けて行くので、諦めてローカルにUbuntuのvirtualboxを立てて使うことにした。vagrant便利だし。
http://qiita.com/awakia/items/895b3d61311b19737237 あたりを見て
boxの選択は Ubuntu Quantal 64 (12.10) Vanilla (※389MB) にしてみる。
$ vagrant box add quantal64-vanilla https://dl.dropboxusercontent.com/u/165709740/boxes/quantal64-vanilla.box $ vagrant init quantal64-vanilla $ vagrant up
これで
$ vagrant ssh
ローカルのvirtualboxに入れる。
Pythonは2.7.3, 3.2.3が入っていた。
本家ダウンロードページにある指示どおりに /etc/apt/sources.list を編集し、apt-get update した後
vagrant@quantal64-vanilla:~$ sudo apt-get install python-graph-tool
など実行。graph-tool がさくっと入った。
Mac側のホームディレクトリでvagrantを立てたので、virtualbox側の /vagrant/ 以下にホームの内容が見える。個人的に使うにはとても便利。
Mac側でスクリプトを編集して
$ vim foo.py
中身はこんな感じ。ここの最初のプログラムから。
from graph_tool.all import * g = Graph() v1 = g.add_vertex() v2 = g.add_vertex() e = g.add_edge(v1, v2) graph_draw(g, vertex_text=g.vertex_index, vertex_font_size=18, output_size=(200, 200), output="two-nodes.pdf") print(v1.out_degree())
これをvirtualbox側で実行
vagrant@quantal64-vanilla:~$ python graph.py ** (graph.py:25309): WARNING **: Could not open X display
うーむ。
Xが開けないのはMac側に繋いでやればいいはずなので*2Mac側で
$ vim ~/.vagrant.d/boxes/quantal64-vanilla/virtualbox/Vagrantfile
Vagrant::Config.run do |config| # This Vagrantfile is auto-generated by `vagrant package` to contain # the MAC address of the box. Custom configuration should be placed in # the actual `Vagrantfile` in this box. config.vm.base_mac = ... config.ssh.forward_x11 = true ## ←この1行を追加 end ...
これでvagrantを立ち上げなおしたら行けるんじゃね
vagrant@quantal64-vanilla:~$ exit logout Connection to 127.0.0.1 closed. $ vagrant halt $ vagrant up $ vagrant ssh ... Last login: Wed Jun 26 07:11:08 2013 from 10.0.2.2 vagrant@quantal64-vanilla:~$ python graph.py 1
今度はうまく行った。
Mac側で
$ open two-nodes.pdf
すると
ちゃんと出来てた。
PRML §8.3.3 例:画像のノイズ除去
【次回復々習レーン(2013/7/21開催予定)の発表資料準備】
反復条件付きモード(ICM)での画像復元
- 左上から順番に走査しながら、反転するとエネルギーを減らせるピクセルを反転
- 走査前後のエネルギー差分がεを下回ったら(あるいは10回やったら)終了
MacBook Air (1.8 GHz Intel Core i7) でノイズ除去にかかった時間:
noise | iter | sec |
---|---|---|
5% | 5 | 0.850 |
10% | 6 | 1.037 |
15% | 6 | 1.029 |
20% | 8 | 1.374 |
25% | 10 | 1.705 |
30% | 8 | 1.373 |
320x180の画像をPythonで1秒前後で処理できています。
25%で走査数が多いのは気にしない(ノイズ生成パターンをいくつも作ったら吸収されると思う)
Pythonの辞書内包表記 (2.7〜)
3.1で入ったのは聞いてたけれど、今使ってる2.7でも使えるの知らなかった><
- 集合のリテラル文法 ({1,2,3} は mutable set になります)
- 辞書と集合の内包表記 ({i: i*2 for i in range(3)}).
コードテンプレート加筆 + TZTesterの文言変更
assert() を使おう
SRMがドジっ子アピールの場となっている現状を打破すべく
#define NDEBUG $BEGINCUTS #undef NDEBUG $ENDCUTS #include <cassert>
を追加。
全体だとこんな感じ→ https://gist.github.com/naoyat/5821991
これでローカルテストの時だけassert()が使える。こんな感じ。
typedef long long ll; ... bool f(ll x) { ... } ll lo = 1LL, hi = LONG_LONG_MAX; int z = 0; while (true) { // lo:x hi:o assert(lo < hi); assert(0 <= lo); assert(!f(lo)); assert(f(hi)); if (lo+1 == hi) { return hi; } ll mi = (lo + hi)/2; if (f(mi)) hi = mi; else lo = mi; assert(mi >= 0); }
TZTester文言変更:Expected/Received を Expected/Your answer に変えてみる
SRM583 Div2 Easy "SwappingDigits" より。わざと間違えてます。
Test Case #0...PASSED (0.024 msec) Test Case #1...PASSED (0.009 msec) Test Case #2...PASSED (0.006 msec) Test Case #3...FAILED (0.004 msec) Expected: "10234" Your answer: "01234" Test Case #4...FAILED (0.006 msec) Expected: "13218910471211292496" Your answer: "03218919471211292416" Test Case #5...FAILED (0.006 msec) Expected: "10720376171328422763213753122612211005355347513" Your answer: "01720376171328422763213753122612211005355347513"
これでテスト失敗時の視認率が上がるかも。
https://github.com/naoyat/TZTester
↑他にも魔改造が施されているので、ご利用は計画的に&自己責任で!