LPっぽいのと最小カット
様々な問題をLPやその双対を駆使して解きまくっているwataさんが格好良すぎるので、ちょっといくつかの最小カットの問題を解き直してみた。
私はLPにも最大流にも詳しくないので、完全ユニモジュラとか言われても「成り立ってることを祈りましょう」くらいしか言えないし、どこがLPなんだよ！と言われてもまともに答えられる自信はないです。
基本形
x[i]は0または1の値をとり、x[s]=1,x[t]=0とする。関数f(x)=x>0?1:0と定義したとき、sum f(x[i]-x[j])*c[i][j]の最小化問題でかけるもの。ただしc[i][j]>=0。具体的にグラフを構成するにはiからjへ容量c[i][j]の辺を張れば良い。ほげほげしてはいけない、みたいな制約はc[i][j]=infだと思えば良い。
例題：Dual Core CPU (蟻本に載ってる)
x[i] = {モジュールiをAで実行する?1:0}とおく。このとき以下を最小化する。
sum_{i in [1..N]} (f(x[i])*A[i] + f(1-x[i])*B[i])
+ sum_{i in [1..M]} ( f(x[a[i] ]-x[b[i] ])*w[i] + f(x[b[i] ]-x[a[i] ])*w[i] )
ここで、
- f(x[i])=f(x[i]-0)=f(x[i]-x[t])
- f(1-x[i])=f(x[s]-x[i])
でかつ全ての係数が非負なので、
sum_{i in [1..N]} (f(x[i]-x[t])*A[i] + f(x[s]-x[i])*B[i])
+ sum_{i in [1..M]} ( f(x[a[i] ]-x[b[i] ])*w[i] + f(x[b[i] ]-x[a[i] ])*w[i] )
これは最小カットのLPとなっている。
具体的にグラフを構成するには、
- 頂点iから頂点tへ容量A[i]の辺を張る。
- 頂点sから頂点iへ容量B[i]の辺を張る。
- 頂点a[i]からb[i]へ容量w[i]の辺を張る。
- 頂点b[i]からa[i]へ容量w[i]の辺を張る。
とすればよい。
例題：GreenWarfare (SRM 465)
x[i] = {基地iを破壊する?1:0}
y[i] = {補給所iを破壊する?1:0}
CB[i]=基地iを破壊するのに必要なコスト
CP[i]=補給所iを破壊するのに必要なコスト
問題を素直に読むと、次を最小化する問題らしい。
sum_{i in [1..B]} f(x[i])*CB[i] + sum_{i in [1..P]} f(y[i])*CP[i]
+ sum_{基地iと補給所jの距離がR以下} f(1-(x[i]+y[j]))*inf
ここでf(1-(x[i]+y[j]))という式が出てきて困る。そこで、z[i]=1-y[i]と置き換えて上の式を書き直してみる。
sum_{i in [1..B]} f(x[i])*CB[i] + sum_{i in [1..P]} f(1-z[i])*CP[i]
+ sum_{基地iと補給所jの距離がR以下} f(z[j]-x[i])*inf
Dual Core CPUと同じように次のように書き換えれば終わりとなる。
sum_{i in [1..B]} f(x[i]-x[t])*CB[i] + sum_{i in [1..P]} f(x[s]-z[i])*CP[i]
+ sum_{基地iと補給所jの距離がR以下} f(z[j]-x[i])*inf
Komakiさんの例題0
今度は最大化問題なので、損害の最小化という風に考える。例えば本当は1個のゴミを処理するのに300円貰えたはずなのに、と考えると利益は300*3 - 損害となる。この場合の損害は、A,B,Cを燃やした場合の損害はそれぞれ300-50=250、300-60=240, 300-130=170。A,B,Cを埋めた場合の損害はどれも300-100=200となる。
x[A]={Aを燃やした?1:0}
などとおく。このとき以下の損害を最小化する。
f(x[A])*250+f(x[B])*240+f(x[C])*170+f(1-x[A])*200+f(1-x[B])*200+f(1-x[C])*200
+f(x[B]-x[C])*inf + f(x[C]-x[B])*inf
お馴染みの方法でf(x[A])=f(x[A]-x[t]), f(1-x[A])=f(x[s]-x[A])などと置き換えれば良い。
Komakiさんの演習0
本当は1個のゴミを処理する毎に600円貰えたはずだと考える。このとき利益は600*4-損害となる。
さっきと同じように式を立てると、次の最小化を考えていることになる。
f(x[A])*300+f(x[B])*200+f(x[C])*100+f(x[D])*0
+ f(1-x[A])*150+ f(1-x[B])*150 + f(1-x[C])*150 + f(1-x[D])*150
+ f(x[A]-x[B])*inf + f(x[A]-x[C])*inf + f(x[D]-x[A])*inf
後はやっぱり同じ。
Komakiさんの例題1
やっぱり損害の最小化。最初、各本毎に400円ずつ貰えるものだと考えて400*3-損害が答となる。
x[A]={Aを売った?1:0}
などとすると最小化すべき損害の式は次のようになる。
f(x[A])*500 + f(x[B])*100 + f(x[C])*0
+ f(1-x[A])*400 + f(1-x[B])*400 + f(1-x[C])*400
+ f(x[A]-x[B])*140 + f(x[B]-x[A])*140 + f(x[B]+x[C]-1)*30
今度はf(x[B]+x[C]-1)が出てきて困る。そこでx[C]=1-x[C]と置き換えると、
f(x[A])*500 + f(x[B])*100 + f(1-x[C])*0
+ f(1-x[A])*400 + f(1-x[B])*400 + f(x[C])*400
+ f(x[A]-x[B])*140 + f(x[B]-x[A])*140 + f(x[B]-x[C])*30
まとめ
「してはいけない」という制約はinfを係数に持つ項を目的関数に加える。コストは全部非負。
大体パターンが見えてくる。
- x[i]=1のときコストが発生。
- 目的関数にf(x[i]-x[t])*(コスト)を追加。
- x[i]=0のときにコストが発生。
- 目的関数にf(x[s]-x[i])*(コスト)を追加。
- x[i]>x[j]のときにコストが発生。
- 目的関数にf(x[i]-x[j])*(コスト)を追加。
- x[i]!=x[j]のときにコストが発生(x[i]+x[j]=1と読み替えることもできる)。
- x[i]>x[j]またはx[i]
- x[i]=x[j]=0のときにコストが発生。
- 目的関数にf(1-(x[i]+x[j]))*(コスト)を追加。
- x[i]=x[j]=1のときにコストが発生。
- 目的関数にf(x[i]+x[j]-1)*(コスト)を追加。
fの中は必ず2項の差分になってなくてはならず、そうなってない場合はx[j]=1-x[j]などで置き換える。このとき他の所で困らない保証はない(例えば2部グラフだと上手くいくことが多いが)。
これで全部上手く行くのかは分からないけど、例えばThe Year of Code Jam(蟻本の最後に載ってる)なんかはこの方針だと大分見えやすくなる気がした。
この記事の信憑性はゼロなので、間違いなどがあれば指摘して貰えると私は喜びます。
次は最小費用流に行きたい所だけど、その前に最小費用循環流勉強するべきなんだろうか。
