燃やす埋める問題を完全に理解した話
完全に理解しても今ではもう捻くれた応用問題しか出ないので
今後解けるとは言っていないです。
数弱なのでガバってると思うけど雰囲気で察してください。
参考資料
書き終えてから見つけたけど、この記事の内容大体ここに書いてあった気がする。 再発明万歳...
燃やす埋めるをグラフ表現可能な劣モジュラ関数の視点から見たもの。 これがなかったらソルバなんて作らなかった
燃やす埋めるが出題される度に見に行くいつものやつ
より発展したやつ (よく理解していない)
発展して行く先は SAT とか SMT
tl;dl
- 燃やす埋める問題を定式化するとちゃんと最小カット問題になってる
- 変数の flip 操作をすると関係する部分が 劣モジュラ <-> 非劣モジュラ になる
- 上手く flip して全体を劣モジュラにできれば元々の入力に負のコストとか両方燃やすとかがあっても、最小カットの形に変形できるので最大流で解ける
- flip 制約は双方向辺しかない 2-SAT になるので簡単に解を見つけられる (flip 解がなかったら少なくともこのままでは最大流として解けない)
これらを踏まえると
model.add_constraint(~x, 35); // x を埋めるコスト model.add_constraint( x, 15); // x を燃やすコスト // model.add_constraint(~y, 0); // y を埋めるコスト (特に指定しなければコスト 0) model.add_constraint( y, 10); // y を燃やすコスト model.add_constraint(~x, ~y, 30); // x を埋めて y も埋めたときのコスト model.add_constraint(~x, y, -20); // x を埋めて y を燃やすときのコスト model.add_constraint( x, ~y, 10); // x を燃やし y を埋めるときのコスト model.add_constraint( x, y, -10); // x を燃やし y も燃やすときのコスト ans = model.solve(); // ans = 15, x=1, y=1
の様な形の簡易的なソルバを作れる。
複雑な条件用の補助変数を追加したりは自分でやる必要がある。
目次
1. 燃やす埋める問題は最小カット問題 ↩
毎度辺のつなぎ方がよくわからなかったり 最小費用流を考えてしまったりで解けない。 燃やす埋める問題を定式化し、最小カット問題の形になっていることを確認する。 また (割当問題の解法としての) 最小費用流と比較し、それぞれ何ができて何ができないかを確認する。 (誤認する人向け)
1.1. 最小カット問題とは ↩
- 有向グラフの各頂点を色 $\lbrace s, t \rbrace $ に塗り分ける
- 辺には重みが設定されている
- 色 $s$ の頂点 $u$ と色 $t$ の頂点 $v$ の間に有向辺 $(u,v)$ があるとき、この辺を消す。 辺の重み $w_{uv}$ の費用がかかる
- 合計費用を最小化せよ
式にすると
$$ \text{minimize} \quad f(\boldsymbol{x}) = \sum_{(u,v) \in E} w_{uv} \, g(x_u, x_v) $$
ただし
$$ x_i = \begin{cases} 1 \quad (\text{頂点 $i$ の色が $s$}) \cr 0 \quad (\text{頂点 $i$ の色が $t$}) \end{cases} $$
$$ g(x_u, x_v) = x_u \, (1-x_v) $$
とする。 $g(x_u, x_v)$ は 頂点$u$ が色$s$ で 頂点$v$ が色$t$ のとき $1$ 、それ以外のとき $0$ となる。
特に辺の重みが全て非負なら効率的に解ける。 必ず色 $s$ で塗らないといけない頂点 $s$ 、 必ず色 $t$ で塗らないといけない頂点 $t$ があるとき、 辺の重みを容量としたグラフの s-t 最大流を求めるとそれが答えになる。 (最大フロー最小カット定理)
一般的にはこの色指定付き非負制約バージョンを最小カットと言うっぽい。 (色の指定がない場合、全部同じ色にすれば費用 0 になる無意味な問題。 最大流的に言うと流量 0 )
負の重みの辺がある場合 NP-hard になって効率的に解けないらしい。 全部負なら最大カット問題で NP-complete らしい。 そういう場合でも頂点数が小さければ O( 2N ) 通り全探索すれば解けないこともない。 大きければもうマラソン。
色$s$ (赤) -> 色$t$ (青) の有向辺の重みの分だけ費用がかかる。 負辺があると最大流で解けない。
1.2. 燃やす埋める問題とは ↩
- ゴミ $i$ を燃やすと $b_i$ 円かかる
- ゴミ $i$ を埋めると $c_i$ 円かかる
- ゴミ $i$ を燃やして ゴミ $j$ を埋めると $d_{ij}$ 円かかる
- 費用はすべて非負 $\, (b_i, c_i, d_{i,j} \geq 0)$
- 全てのゴミは燃やすか埋めるかしないといけない
- 費用合計を最小化せよ
費用が負 (報酬) のケースや 両方燃やした場合に費用が発生するケースもあるが、基本はコレ。 各ゴミを頂点、費用関係を辺にしたグラフの最小カットを求めるとそれが答えになるらしい。
1.3. 燃やす埋める問題の定式化 ↩
- "ゴミ $i$ を燃やす" $\Leftrightarrow$ "$item_i$ を クラス $s$ に分類する"
- "ゴミ $i$ を埋める" $\Leftrightarrow$ "$item_i$ を クラス $t$ に分類する"
と言い換えると、元の問題は各 $item$ を 2 クラス に分ける問題であると言える。
一方を燃やして一方を埋めたときに発生する費用があることを思うと、 燃やす埋める問題は 2 変数間制約付きの 2 クラス分類コスト最小化問題であると言える。 (呼び方は今考えたもので、そういう用語があるわけじゃない。 分類問題というか割当問題というべき？ 費用合計が目的関数だと言い張れば分類問題と言っても良い気もする)
$item_i$ をクラス $s$ に分類するとき $x_i=1$ 、 クラス $t$ に分類するとき $x_i=0$ とすると、 燃やす埋める問題は次のように定式化できる。
$$ \begin{aligned} &\text {minimize}& f(\boldsymbol{x}) &=& &a + \sum_i b_i \, x_i + \sum_i c_i \, (1-x_i) + \sum_{i,j} d_{ij} \, x_i \, (1-x_j)& \cr &\text{subject to}& x_i &=& &\lbrace 0, 1 \rbrace & \cr && b_i &\geq& &0& \cr && c_i &\geq& &0& \cr && d_{ij} &\geq& &0& \end{aligned} $$
$b_i, c_j, d_{ij}$ はそれぞれ、
- $item_i$ をクラス $s$ に分類したときのコスト
- $item_i$ をクラス $t$ に分類したときのコスト
- $item_i$ をクラス $s$ に分類して $item_j$ をクラス $t$ に分類したときのコスト
に対応している。 定数項 $a$ は今の段階だと $0$ だが後で必要になるので式に入れておく。 意味的には どう分類しても必要になるコスト。
以降見た目が長くなるので $(1-x_i) = \overline{x_i}$ と表記する。
変数 $x_s, x_t \quad (x_s = 1, \, x_t = 0)$ を導入すると、 右辺第2項 第3項 は
$$ b_i \, x_i \, = d_{it} \, x_i \, \overline{x_t} $$
$$ c_i \, \overline{x_i} \, = d_{si} \, x_s \, \overline{x_i} $$
となるので、結局は $$ f(\boldsymbol{x}) = a + \sum_{i,j} d_{ij} \, x_i \, \overline{x_j} $$ とまとめられる。 定数項の $a$ を除いて最小カット問題の式と同じ形になった。
最小カット問題としては $i \rightarrow j$ へ重み $d_{ij}$ の辺を張ったグラフになるので、 最大流問題として効率的に解くことができる。 ($x_i = 1 \land x_j = 0$ のとき費用 $d_{ij}$ が発生する)
$x_s$ は常に $1$、 $x_t$ は常に $0$ を取るので
- $s \rightarrow i$ は $item_i$ を埋めるときのコスト $c_i$
- $i \rightarrow t$ は $item_i$ を燃やすときのコスト $b_i$
に対応する。 費用は $赤い頂点 \rightarrow 青い頂点$ の辺の重みの合計になる。
1.4. 最小費用流との比較 ↩
わかってる人はこの辺飛ばして。
最小費用流とは次のような問題。
- 有向グラフ $G(V, E)$ がある
- 頂点 $s$ から頂点 $t$ に流量 $f$ を流したい
- 辺 $e$ に流量 $f_e$ が流れるとき $c_e \, f_e$ の費用がかかる
- 辺 $e$ には流量の上限 $u_e$ (場合によっては下限も) が設定されている ($0 \leq f_e \leq u_e$)
- 費用の合計 $\sum_e c_e f_e$ を最小化せよ
特に
- $N$ 人に ${M}$ 種のプレゼントを配る (各人に好み, 各プレゼントの数に上限あり)
のような問題は割当問題と言って、 人とプレゼントで分けた二部グラフ (+ source, sink) にすると最小費用流で解くことができる。 燃やす埋めると混同しやすいのは多分このタイプの問題。
$$ \begin{aligned} c_{ij} &= \text {人 $i$ にプレゼント $j$ を配るときのコスト (報酬)}\cr x_{ij} &= \begin{cases} 1 \quad (\text{人 $i$ にプレゼント $j$ を配るとき}) \cr 0 \quad (otherwise) \end{cases} \end{aligned} $$
として、
$$ \begin{aligned} &\text{minimize}& f(\boldsymbol{x})& &=& &\sum_{ij} c_{ij} \, x_{ij}\cr &\text{subject to}& \sum_j x_{ij}& &=& &1& \quad (\text{プレゼントは一人一つ}) \cr && \sum_i x_{ij}& &\leq& &u_j& \quad (\text{プレゼント $j$ の在庫}) \cr && x_{ij}& &=& &\lbrace 0, 1 \rbrace & \end{aligned} $$
となる。 特に $M=2$ のとき
$$x_{i0} + x_{i1} = 1$$
なので
$$ \text{minimize} \quad f(\boldsymbol{x}) = \sum_{i} c_{i0} \, x_{i0} + \sum_{i} c_{i1} \, (1-x_{i0}) $$
と表現できる。 これは燃やす埋める問題の 1 次の項と同じ形をしていて、 実際に最小費用流 (割当問題) と燃やす埋めるは似た形の問題なんだなぁと思う (?)。 2 次の項がここに出現しないのは重要なポイント。
まとめるとこんな感じ。
- 燃やす埋めるは $2$ クラス分類
最小費用流 (割当問題) は ${M}$ クラス分類 - 燃やす埋めるは $2$ 変数間の制約が使える
最小費用流はダメ - 最小費用流は各クラスの割当数に上限下限の指定が可能
燃やす埋めるはダメ
ちなみに燃やす埋めるの方は補助頂点を追加することで柔軟に対応できる場合がある。
(多クラス化、多変数間制約等)
最小費用流の方も「ここは一人しか通れません」みたいな感じでグラフを工夫すると
疑似的に多変数間の制約ができたりするけどまぁ基本の話なので。
2. 燃やす埋める問題の条件を緩和する ↩
ここからが本題。
再掲
$$ \begin{aligned} &\text {minimize}& f(\boldsymbol{x}) &=& &a + \sum_i b_i x_i + \sum_i c_i \overline{x_i} + \sum_{i,j} d_{ij} \, x_i \, \overline{x_j}& \cr &\text{subject to}& x_i &=& &\lbrace 0, 1 \rbrace & \cr && b_i &\geq& &0& \cr && c_i &\geq& &0& \cr && d_{ij} &\geq& &0& \end{aligned} $$
燃やす埋める問題には
$b,c,d$ は非負、 2 変数間制約は
$x_i \, \overline{x_j}$ の形のみという制限があった。
これらの制限を緩和した問題を元の問題の形に変換できれば、
緩和した問題も最大流で解くことができる。
2.1. $b$, $c$ について ↩
これは簡単に非負制約を取り除ける。
$b_i \geq c_i$ のとき、 $x_i, \overline{x_i}$ どちらでも $c_i$ はかかると思えば
$$a \leftarrow a + c_i$$ $$b_i \leftarrow b_i - c_i$$ $$c_i \leftarrow 0$$ と $a$ に押し付けて $b_i,\, c_i \geq 0$ に変換できる。 $b_i \lt c_i$ のときも同様。
2.2. $d$ について ↩
2.2.1. $d$ の拡張 ↩
$x_i \, \overline{x_j}$ 以外の形の 2 変数間制約を追加できるように、 $d_{ij}$ を $d_{ij}^{00}, \, d_{ij}^{01}, \, d_{ij}^{10}, \, d_{ij}^{11}$ に拡張する。
$$d_{ij}^{00} \, \overline{x_i} \, \overline{x_j}$$ $$d_{ij}^{01} \, \overline{x_i} \, x_j$$ $$d_{ij}^{10} \, x_i \, \overline{x_j}$$ $$d_{ij}^{11} \, x_i \, x_j$$
$d_{ij}^{00}$ は両方色 $t$ ならかかるコスト、 $d_{ij}^{11}$ は両方色 $s$ ならかかるコストといった具合。 負のコストも許容することにする。
$$ \left\lbrack \begin{array}{cc} d^{00} & d^{01} \cr d^{10} & d^{11} \end{array} \right\rbrack = \left\lbrack \begin{array}{cc} 0 & 非負 \cr 非負 & 0 \end{array} \right\rbrack $$
なら元の問題と同じ。 ( $d_{ji}$ は $d_{ij}$ にまとめる)
2.2.2. $x_i$ の flip 操作 ↩
$$x_k = \overline{x_i}$$
となる新しい変数 $x_k$ を導入して
$$ \begin{aligned} b_k = c_i \\ c_k = b_i \end{aligned} $$
$$ \boldsymbol{d}_{kj} \, = \, \left\lbrack \begin{array}{cc} d_{ij}^{10} & d_{ij}^{11} \cr d_{ij}^{00} & d_{ij}^{01} \end{array} \right\rbrack \quad (\text{行が入れ替わる}) $$
$$ \boldsymbol{d}_{jk} \, = \, \left\lbrack \begin{array}{cc} d_{ji}^{01} & d_{ji}^{00} \cr d_{ji}^{11} & d_{ji}^{10} \end{array} \right\rbrack \quad (\text{列が入れ替わる}) $$
のようにして $x_i$ を $x_k$ で置き換えると元の問題の条件を満たすようにできることがある。
($i$ と関連のある全ての $j$ について入れ替える必要があることに注意)
燃やす埋める問題の解説記事によくある辺 (選択肢) を入れ替えて解ける形にする操作はこれ。
燃やす埋めるをなんとなくでやってた頃は
「よくわかんないけど、こねこねしてたら偶然解ける形になった！」
と凄く雑にやってた。
実はどういう風に入れ替えれば解ける形になるのかはちゃんと条件がある。
この記事ではこの操作を "flip" と呼び、 変数 $x_i$ を flip する / しないを 論理変数 $flip_i, \, \neg flip_i$ で表す。
2.2.3. $\boldsymbol{d}_{ij}$ の reduction 操作 ↩
見難いので $d_{ij}^{**}$ を $d^{**}$ と書く。
$d^{**}$ は足し引きすることで一か所以外は $0$ にできる。
$$ \left\lbrack \begin{array}{cc} d^{00} & d^{01} \cr d^{10} & d^{11} \end{array} \right\rbrack = \left\lbrack \begin{array}{cc} d^{00} & d^{00} \cr d^{00} & d^{00} \end{array} \right\rbrack + \left\lbrack \begin{array}{cc} 0 & 0 \cr d^{10} - d^{00} & d^{10} - d^{00} \end{array} \right\rbrack + \left\lbrack \begin{array}{cc} 0 & d^{11} - d^{10} \cr 0 & d^{11} - d^{10} \end{array} \right\rbrack + \left\lbrack \begin{array}{cc} 0 & d^{01} + d^{10} - d^{00} - d^{11} \cr 0 & 0 \end{array} \right\rbrack $$
右辺について
- 1 項目は $x_i, x_j$ によらない定数になるので $a$ に押し付けられる $$ a \leftarrow a + d^{00} $$
- 2 項目は $x_j$ によらないので $b_i$ に押し付けられる $$b_i \leftarrow b_i + d^{10} - d^{00}$$
- 3 項目は $x_i$ によらないので $b_j$ に押し付けられる $$b_j \leftarrow b_j + d^{11} - d^{10}$$
という感じで 4 項目だけが残り、 $d^{01}$ 以外は 0 にできる。 同様の操作で他の場所に残すことも可能。 $d^{11}$ の位置に残すならこんな感じ。
$$ \left\lbrack \begin{array}{cc} d^{00} & d^{01} \cr d^{10} & d^{11} \end{array} \right\rbrack_{ij} = \left\lbrack \begin{array}{cc} d^{10} & d^{10} \cr d^{10} & d^{10} \end{array} \right\rbrack + \left\lbrack \begin{array}{cc} d^{00} - d^{10} & d^{00} - d^{10} \cr 0 & 0 \end{array} \right\rbrack + \left\lbrack \begin{array}{cc} 0 & d^{01} - d^{00} \cr 0 & d^{01} - d^{00} \end{array} \right\rbrack + \left\lbrack \begin{array}{cc} 0 & 0 \cr 0 & d^{00} + d^{11} - d^{10} - d^{01} \end{array} \right\rbrack $$
この操作をすると結局 $\pm (d^{01} + d^{10} - d^{00} - d^{11})$ が残ることになる。
$$ s = d^{01} + d^{10} - d^{00} - d^{11}$$
とすると $\boldsymbol{d}$ を
$$ \left\lbrack\begin{array}{cc} -s & 0 \cr 0 & 0 \end{array}\right\rbrack , \left\lbrack\begin{array}{cc} 0 & +s \cr 0 & 0 \end{array}\right\rbrack , \left\lbrack\begin{array}{cc} 0 & 0 \cr +s & 0 \end{array}\right\rbrack , \left\lbrack\begin{array}{cc} 0 & 0 \cr 0 & -s \end{array}\right\rbrack $$
のいずれかに変換することができる。
$d^{00}, d^{11}$ が消せるので拡張前の $d$ と同じ形になり、
最小カット問題(負辺あり) の有向グラフとして表現できるようになる。
この記事ではこの操作を "reduction" と呼ぶことにする。
(オレオレ呼称。 標準的な呼び方があったら教えて)
reduction 操作で $d^{01}, d^{10}$ に寄せるとグラフ的には上図のようになる。
2.2.4. flip と reduction を組み合わせる ↩
$$ (\text{flip 操作で $s_{ij} \geq 0 \quad (\forall i,j)$ にできる}) \Rightarrow (\text{最大流問題として解くことができる}) $$
$$ (\text{flip 操作で $s_{ij} \geq 0 \quad (\forall i,j)$ にできない}) \Rightarrow \\ (\text{(少なくとも flip 操作だけでは) 最大流問題として解くことができない}) $$
後者は劣モジュラにする手段が他に存在しなければ (少なくとも...) が取れる。 多分難しいと思うんだけどよくわからない。
- 2021/03/03 追記
flip で解けないなら flip だけで解けないのはそれはそうだろ、って感じだけど、 「flip で解けないなら多分無理だろ」って気持ちが先にあって、でもそうとは言い切れないことに気づいたので () 付きになった。
例えば $x_i = x_j$ みたいな実は同値の変数が存在して $s_{ik} = -1, s_{jk} = 2$ であるとき、うまく flip はできないけど、 $x_i = x_j$ だから $s_{jk} + s_{ik} = 1 \geq 0$ と合成して非負にすることができる。
$s_{ij}, s_{ji}$ でバラしちゃってる場合も同じ話かな？
そういうのがない既約状態になってて flip で解けないなら多分無理…？
以下説明。
reduction と flip を組み合わせると
$s_{ij} \geq 0$
- reduction 操作で $d_{ij}^{01} \leftarrow s_{ij} \, (\geq 0)$ にする
$s_{ij} \lt 0$
- reduction 操作で $d_{ij}^{11} \leftarrow -s_{ij}$ にする
- $x_i$ に flip 操作をして $d_{ij}^{01} \leftarrow -s_{ij} \, (\gt 0)$ にする
のようにして $d_{ij} \, x_i \, \overline {x_j} \, (d_{ij} \geq 0)$ の形のみという元の制約を満たす形に変換できる。 つまり $s_{ij} \geq 0 \, (\forall {i,j})$ になる flip 操作ができれば最小カット問題(負辺なし)になり、最大流問題として解くことができると言える。 (i,j は適宜入れ替えて読んで)
ところで参考資料によると燃やす埋めるは劣モジュラ関数であることが重要らしい。 (劣モジュラの定義とかはググったり参考資料をどうぞ)
最小カット問題(負辺なし)は劣モジュラだそうなので、
操作後に劣モジュラ関数にできない場合は最小カット問題(負辺なし)にならない。
$$ g_{ij}(x_i, x_j) = d^{00}_{ij} \, \overline{x_i} \, \overline{x_j} + d^{01}_{ij} \, \overline{x_i} \, {x_j} + d^{10}_{ij} \, {x_i} \, \overline{x_j} + d^{11}_{ij} x_i x_j $$
とすると、 $g_{ij}$ が劣モジュラ関数になる条件は
$$ \begin{aligned} &&g_{ij}(0,1) + g_{ij}(1,0) &\geq g_{ij}(0,0) + g_{ij}(1,1) \cr &\Leftrightarrow& d_{ij}^{01} + d_{ij}^{10} - d_{ij}^{00} - d_{ij}^{11} &\geq 0&& \cr &\Leftrightarrow& s_{ij} &\geq 0&& \cr \end{aligned} $$
となり、 全ての $s_{ij}$ が非負であること。 また、
$$ h_{ijkl}(x_i, x_j, x_k, x_l) = g_{ij}(x_i, x_j) + g_{kl}(x_k, x_l) $$
としたとき、 $h_{ijkl}$ は例えば
$$ h_{ijkl}(0,0,1,0) + h_{ijkl}(0,0,0,1) \geq h_{ijkl}(0,0,0,0) + h_{ijkl}(0,0,1,1) \\ \Rightarrow g_{kl}(1,0) + g_{kl}(0,1) \geq g_{kl}(0,0) + g_{kl}(1,1) $$
を満たさないと劣モジュラ関数にならないので、 $s_{ij} \lt 0$ が一つでもあると全体も非劣モジュラになり最小カット問題(負辺なし)にならない。 負辺があると最大流で解けない、といったのは多分この辺の話も関係ありそう。
$s$ の値は reduction 操作によらないので 劣モジュラ性は flip 操作の解の存在を考えればよく、 全体を劣モジュラにする flip が実行可能なら reduction 操作で 元の問題の形に変形可能。 そうじゃないなら不可能。
$$ (\text{flip 操作で $s_{ij} \geq 0 \quad (\forall i,j)$ にできる}) \Rightarrow (\text{最大流問題として解くことができる}) $$ $$ (\text{flip 操作で $s_{ij} \geq 0 \quad (\forall i,j)$ にできない}) \Rightarrow \\ (\text{(少なくとも flip 操作だけでは) 最大流問題として解くことができない}) $$
(知らないだけで flip 操作以外の凄いテクがあるのかもしれないので絶対に最大流問題にできないとは言えない…。 いわゆる燃やす埋める問題の範疇で出題されてるものなら flip + reduction (+変数追加)で解けると思う。)
2.2.5. 全体を劣モジュラにする flip 操作 ↩
$s_{ij}$ は $x_i, x_j$ 一方の flip 操作で 符号が入れ替わり、 両方 flip すると元の符号に戻るので、 次のような操作をする必要がある。
$$ \begin{aligned} s_{ij} \gt 0 &\Rightarrow& &(flip_i \land flip_j)& &\lor& &(\neg flip_i \land \neg flip_j)& \cr s_{ij} \lt 0 &\Rightarrow& &(flip_i \land \neg flip_j)& &\lor& &(\neg flip_i \land flip_j)& \end{aligned} $$
($s_{ij} = 0$ なら特に制限はない。 $\boldsymbol{d_{ij}}$ 自体を消せるからそれはそう)
$flip_i \leftrightarrow flip_j$
みたいな感じでグラフを作るとよさそう。
念のため分配法則で分けてみる。
$$ \begin{aligned} s_{ij} \gt 0 &\Rightarrow& &(flip_i \lor \neg flip_j)& &\land& &(\neg flip_i \lor flip_j)& \cr s_{ij} \lt 0 &\Rightarrow& &(flip_i \lor flip_j)& &\land& &(\neg flip_i \lor \neg flip_j)& \end{aligned} $$
2-SAT になったので $flip_i$, $\neg flip_i$ に対応する
頂点を作って辺をつないで、 $flip_i$ と $\neg flip_i$
が強連結なら解なしで最大流じゃ解けない形。
2-SAT 用に構築するグラフは
- $flip_i \leftrightarrow flip_j$ $(s \gt 0)$
- $\neg flip_i \leftrightarrow \neg flip_j$ $(s \gt 0)$
- $flip_i \leftrightarrow \neg flip_j$ $(s \lt 0)$
- $\neg flip_i \leftrightarrow flip_j$ $(s \lt 0)$
になる。 分配法則適用前のと一致した。
双方向の辺しかないので一般 2-SAT の様に強連結成分分解する必要はなくて、
適当に探索したり Union-Find をしたりで連結性を確かめればよい。
$flip_i$ と $\neg flip_i$ が同一の連結成分になってたら充足不可能(c)。 充足可能なら連結成分単位で適当に割り当ててやればいい。
3. グラフ構築 & 解の復元 ↩
3.1. グラフ構築 ↩
最大流で解けるとわかったらもう簡単。
- flip + reduction で解ける形に変形
- $d_{ij}^{01} \gt 0$ なら $j \rightarrow i$ に重み $d_{ij}^{01}$ の辺を張る
- $d_{ij}^{10} \gt 0$ なら $i \rightarrow j$ に重み $d_{ij}^{10}$ の辺を張る
- $b_{i} \gt 0$ なら $i \rightarrow t$ に重み $b_{i}$ の辺を張る
- $c_{i} \gt 0$ なら $s \rightarrow i$ に重み $c_{i}$ の辺を張る
- $s$ から $t$ への最大流 $f$ を求める。 最小カット問題の答えは $f$
- 燃やす埋める問題の答えは $f + a$
3.2. 解の復元 ↩
最大流を流したグラフで $s$ と 頂点 $i$ が容量 $1$ 以上の辺でまだつながっているなら $x_i = 1$、
そうでないなら $x_i = 0$。
$s \rightarrow i$ への直接辺がない or 容量 $0$ の場合でも
$s \rightarrow u \rightarrow \ldots \rightarrow v \rightarrow i$ といくつかの頂点を辿って
到達可能なら $x_i = 1$ なことに注意。
また $flip_i = true$ なら $x_i \leftarrow \overline{x_i}$ とする必要がある。
4. まとめ ↩
- 燃やす埋める問題とは $$ \begin{aligned} &\text {minimize}& f(\boldsymbol{x}) &=& &a + \sum_i b_i \, x_i + \sum_i c_i \, (1-x_i) + \sum_{i,j} d_{ij} \, x_i \, (1-x_j)& \cr &\text{subject to}& x_i &=& &\lbrace 0, 1 \rbrace & \cr && b_i &\geq& &0& \cr && c_i &\geq& &0& \cr && d_{ij} &\geq& &0& \end{aligned} $$
変数 $x_s, x_t$ を追加すれば最小カット問題(負辺なし)と同じ式になるので最大フロー最小カット定理より最大流で解ける
条件を緩和すると $$ \begin{aligned} &\text {minimize}& f(\boldsymbol{x}) &=& &a + \sum_i \bigl( b_i \, x_i + c_i \, \overline{x_i} \bigr) + \sum_{i,j} \bigl( d_{ij}^{00} \, \overline{x_i} \, \overline{x_j} + d_{ij}^{01} \, \overline{x_i} \, x_j + d_{ij}^{10} \, x_i \, \overline{x_j} + d_{ij}^{11} \, x_i \, x_j \bigr) \cr &\text{subject to}& x_i &=& & \lbrace 0, 1 \rbrace & \cr \end{aligned} $$ としてもうちょっと柔軟な形で解くことができる。 ただし解けない (最大流問題にならない) 場合あり。
足し引きしたり選択肢を入れ替えたりするような小技で解ける形にする燃やす埋める問題は多分解ける。$s_{ij} = d_{ij}^{01} + d_{ij}^{10} - d_{ij}^{00} - d_{ij}^{11} \geq 0 \quad (\forall i,j)$
なら reduction 操作で緩和前の問題 (最小カット) に変形できる- flip 操作で $s_{ij}$ の符号を入れ替えられる
一方のみ flip なら $-s_{ij}$ 、 両方 flip / 両方 flip しないなら $+s_{ij}$ - 要件を満たす flip 操作は双方向辺しかない 2-SAT になるので適当に解ける (あるいは解なしで最大流問題にできない)
- reduction と flip で解ける形にしたらグラフを作って流して解ける
- 流した後のグラフで $s \rightarrow i$ に到達可能なら $x_i=1$
- $flip_i = true$ なら $x_i \leftarrow \overline{x_i}$ として flip 前に戻す
5. 実践編 ↩
緩和した燃やす埋める問題を解くとき、次のようなテーブルを埋めていくことになる。
1次の項 ($b_i, c_i$) の制約
| $x_i=0$ $(c_i)$ | $x_i = 1$ $(b_i)$ | |
|---|---|---|
| $x_0$ | 35 | 15 |
| $x_1$ | 0 | 10 |
| $\vdots$ | ||
| $x_k$ | 0 | 0 |
テーブルの左右は実装によっては逆。
2次の項 ($d_{ij}$) の制約
| $d_{01}^{**}$ | $x_1=0$ | $x_1=1$ |
|---|---|---|
| $x_0=0$ | 30 | -20 |
| $x_0=1$ | 10 | -10 |
$\vdots$
| $d_{mk}^{**}$ | $x_k=0$ | $x_k=1$ |
|---|---|---|
| $x_m=0$ | 0 | $\infty$ |
| $x_m=1$ | 0 | 0 |
最大で $_nC_2$ 個の 2x2 のテーブルができる。
$i \lt j$ とかを決めて一つのテーブルにまとめておこう。 ($d_{ij}, d_{ji}$ で分かれていると、 $s_{ij} \gt 0, s_{ji} \lt 0, s_{ij}+s_{ji}\geq 0$ の様なときに解けないと判定されてしまう)
いくつか問題例を挙げる。 といっても問題に書いてあることを入力するだけ。
問題によっては補助変数を追加しないといけない。 そういうときは頑張って頭を使おう。
ネタばれ注意。
5.1. Project Selection Problem ↩
https://en.wikipedia.org/wiki/Max-flow_min-cut_theorem#Project_selection_problem
燃やす埋めるの本当の名前はこれ？と話題になったやつ。
なんかもう全部"最小カット問題"にしか見えなくなったので個人的にはどっちでも。
- $Project_i$ を実行すると報酬 $r_i$ が貰えるけど値段 $c_k$ の $Machine_k$ が必要
みたいな関係があるので利益を最大化してね、という問題。
wikipedia に載ってる問題を考える。
| Project $r(p_i)$ | Machine $c(q_j)$ | ||
|---|---|---|---|
| 1 | 100 | 200 | Project 1 requires machines 1 and 2. |
| 2 | 200 | 100 | Project 2 requires machine 2. |
| 3 | 150 | 50 | Project 3 requires machine 3. |
$$x_i = 1 \Rightarrow Project_i を実行$$ $$y_i = 1 \Rightarrow Machine_i を購入$$
としてテーブルを埋めていく。 報酬は負のコストなことに注意。
| $x_i=0$ $(c_i)$ | $x_i = 1$ $(b_i)$ | ||
|---|---|---|---|
| $x_1$ | 0 | -100 | Project 1 |
| $x_2$ | 0 | -200 | Project 2 |
| $x_3$ | 0 | -150 | Project 3 |
| $y_1$ | 0 | 200 | Machine 1 |
| $y_2$ | 0 | 100 | Machine 2 |
| $y_3$ | 0 | 50 | Machine 3 |
| $y_1=0$ | $y_1=1$ | |
|---|---|---|
| $x_1=0$ | 0 | 0 |
| $x_1=1$ | M | 0 |
| $y_2=0$ | $y_2=1$ | |
|---|---|---|
| $x_1=0$ | 0 | 0 |
| $x_1=1$ | M | 0 |
| $y_2=0$ | $y_2=1$ | |
|---|---|---|
| $x_2=0$ | 0 | 0 |
| $x_2=1$ | M | 0 |
| $y_3=0$ | $y_3=1$ | |
|---|---|---|
| $x_3=0$ | 0 | 0 |
| $x_3=1$ | M | 0 |
$Project_{i}$ を行うのに $Machine_{j}$ がないという状況はダメなので バカデカコスト ${M}$ がかかるようにする。
こんな感じで条件を入力するだけでもう解ける。
5.2. ARC085 E - MUL ↩
https://atcoder.jp/contests/arc085/tasks/arc085_c
かなりシンプルな燃やす埋める。
宝石 $i$ を割ると $i$ で割り切れる全ての $j$ について 宝石$j$ も割らないといけない。
$x_i = 1$ なら宝石 $i$ を割ることにする。
各宝石を残す / 割るときのコストについて
- 宝石$i$ を割る ($x_i=1$) とき $a_i$ の費用がかかる ($b_i \leftarrow b_i + a_i$)
- 宝石$i$ を残す ($x_i=0$) とき $-a_i$ の費用(報酬)がかかる ($c_i \leftarrow c_i -a_i$)
のどちらかをソルバに追加する。 両方追加しちゃダメ。 1 だと答えが $\sum a_i - cost$ の形になってちょっとわかりにくい。 2 ならコスト合計がそのまま答えになるのでオススメ。
宝石$i$ を割ったら宝石$j$ も割らなくちゃいけない ($x_i \Rightarrow x_j$) を満たすようにするには、 クソデカ定数 ${M}$ を用意して
$$d_{ij}^{10} \leftarrow d_{ij}^{10} + {M}$$
の様にすると、 $i$ を割ったのに $j$ を割っていない場合に ${M}$ のコストがかかるようになる。 reduction 操作で足し引きするので ${M}$ を大きくしすぎるとオーバーフローするので注意。
おしまい。
5.3. The Year of Code Jam (World Finals 2008 - Google Code Jam 2008) ↩
https://codingcompetitions.withgoogle.com/codejam/round/00000000004329f6/0000000000432a81
なんと GCJ 決勝の最高難度(当時)の問題。 蟻本にも載ってる。 今ではやるだけ。凄いインフレしてる…。
N x M グリッドに白と青で塗られているセル、まだ塗られていないセルがある。
青セルの数 x 4 点の報酬があるが、 各青セルの周囲(4近傍)にある青セルの数だけペナルティ。
("青--青" なら計 -2 点のペナルティ)
コードを見たほうが多分早い。
// x -> blue // ~x -> white for(int i=0; i<n; i++){ for(int j=0; j<m; j++){ int id = i*m + j; if(s[i][j] == '.'){ // white model.add_constraint(x[id], inf); }else if(s[i][j] == '?'){ // any model.add_constraint( x[id], -4); }else if(s[i][j] == '#'){ // blue model.add_constraint( x[id], -4); model.add_constraint(~x[id], inf); } for(int k=0; k<4; k++){ int r = i + dy[k]; int c = j + dx[k]; if(r<0 || r>=n || c<0 || c>=m) continue; int id_ = r*m + c; // both blue model.add_constraint(x[id], x[id_], 1); } } }
すでに青/白で塗られているセルを違う色で塗っちゃいけないので inf のコスト (実際には大きな定数)、 青で塗ったら -4 のコスト(報酬)、 白で塗るなら 0 のコスト (0 は入力しなくていい)、 青で塗ったところに隣接する青があったらそれぞれ 1 のコスト。 これだけ。
市松模様で辺を良い感じに入れ替えないといけないタイプ。 自動 flip があれば特に意識しないで制約を追加するだけでらくちん。
画像セグメンテーションでつかう最小カットは大体こんな感じっぽい (周辺ピクセルとの関係を最適化)。 ググると応用例が色々でてきます。
5.4. SurroundingGame (SRM 558 Div 1 - Problem 1000) ↩
https://community.topcoder.com/stat?c=problem_statement&pm=12158&rd=15180
昔の問題 Arena で開こうとするとめっちゃ待たされる…。
- セル$_{ij}$に石を置くか、セル$_{ij}$の周囲のセル全てに石を置くと得点 $b_{ij}$
- セル$_{ij}$に石を置くとペナルティ $c_{ij}$
+- が面倒なのでどっちもコストだと思うことにする。
- セル$_{ij}$ に石を置く $c_{ij} - b_{ij}$
- セル$_{ij}$ に石を置かない $0$
- セル$_{ij}$ には置かず、周囲全てに石を置く $- b_{ij}$
の状態があると思うことにする。
$$(セル_{ij} に石を置く) \Leftrightarrow x_{ij} = 1$$
とする。
選択肢 3 に対応する補助変数 $y_{ij}$ を導入する。
$$y_{ij} \Rightarrow \overline{x_{ij}} \land x_{arround_0} \land \dots \land x_{arround_3}$$
という制約がつく変数なので、報酬と、矛盾する場合のペナルティ
- $y_{ij} \Rightarrow -b_{ij}$
- $y_{ij} \land x_{ij} \Rightarrow +\infty$
- $y_{ij} \land \overline{x_{arround}} \Rightarrow +\infty$
のような制約を追加すると良い。
え？ $\Leftarrow$ の方の制約はいらないのかって？ よくわかんない…
この問題に限って言えば、周りに石を置いたのに $y_{ij} = 0$ だと
せっかくもらえる報酬を無視していることになるから、
最小カットのとき $y_{ij} = 1$ に絶対なっているというのはわかる。
絶対なるといえないような形の問題は解けないグラフになってる？ それとも $2^k$ 個変数追加すればいける？ 対偶を取る？ わからん…。 何も理解できていない…。
結局高難度の燃やす埋めるはちゃんとした補助変数を追加したりしないと 上手く解けないので難しい…。
6. 補足 ↩
- flip 操作で無理なら絶対解けない問題？
問題制約が小さければ全探索が可能だし、
乱択アルゴリズムや焼き鈍しで最適解が
求められる可能性もある。
他にも例えば 2-SAT を壊してそうな変数を 0/1 に固定して試す、みたいなことをするとそのうち解ける形になる。
最悪 2n 回試すことになるけど…。
効率的に固定するために MAX 2-SAT で充足できなかった節のところを固定とかしたいものだけど、 MAX 2-SAT も NP-hard らしい。
2-SAT の無向グラフを思うと、原因になってる部分が二重辺連結成分になってるので、こういうところを崩していくとかかなぁ？
あとは分枝限定法で枝刈りしつつ、みたいな感じの研究もあるっぽい。
- なんか答えが合わないんだけど
解ける形判定されても 補助変数が上手に設定できていないと 思った通りに充足してくれず 答えが合わない場合がある。 特に 4 変数以上が関連する制約の場合 そもそもグラフ表現不可能な関数になる場合があるらしい。
おしまい。
ぼやき
vscode の markdown 拡張で tex 形式の数式をプレビューしながら書いてたけど、
出来上がったものを貼り付けたら
はてなブログのマークダウン + mathjax とはちょっと違うっぽくって修正にめっちゃ時間取られた…。
記事中のグラフも最初 graphviz 形式で書いてたんだけど上手く数式を表示できず路線変更。
(tex経由とかsvg経由とか試したんだけどなんかどれでも壊れた…)
結局 diagrams.net (旧 draw.io ) を使って手動。こっちのが早かった…。
