0
Help us understand the problem. What are the problem?

posted at

updated at

燃やす埋める問題の自己流まとめ

短い版をこちら に書きました.

背景

ネットワークフローを勉強してみよう,と思っていたところで,グラフの最小カット問題に行き当たりました.診断人さんの『最小カットを使って「燃やす埋める問題」を解く』 というスライドがたいへん親切にわかりやすく書かれていて,勉強になりました.ただ,「考えて選択肢の順番を決めないといけない」(スライド35) というところが難しく感じました.

次に,よすぽさんのblog記事「最小カットについて」 を読みました.最小カットで解ける問題とは,要するに次のタイプだ,というまとめに,なるほど,と思いました.

  • 頂点がたくさんある。それを赤と青に塗り分ける。全部の頂点を必ず赤か青に塗らなくてはいけない
  • 必ず赤色に塗らなくてはいけない頂点(Sとする)と青色に塗らなくてはいけない頂点(Tとする)が存在する
  • 「Xが赤で、Yが青の時にZ円の罰金がかかる」という制約が沢山ある
  • 罰金の最小値は?

ただ,その記事の後ろに出てきますように,「Xが赤で、Yが赤の時にZ円の報酬」や「Xが青で、Yが青の時にZ円の報酬」も扱えるわけです.もちろんその記事に詳述されているのですが,自分なりの理解をしたいな,と思い,以下のように整理しました.

本質的には,お二人の説明と何も変わっているところはありませんが,自分としては,問題への適用方針がはっきりできたような気がしています.

一般形

次の形をしている問題が,最小カットによって解ける燃やす埋める問題です.

  • ある条件が満たされたときに (正の量を) 支払う.ある条件が満たされたときに (正の量を) 受け取る.支払を最小 (あるいは受取りを最大) にせよ,という形で問題が規定されている.
  • 適当な命題の集合 $P_0$ が,以下の条件を満たすように定義できる.
  • $P_0$ は,True (真) と False (偽) を含む.
  • 「支払う」タイプの条件は,$Q \subseteq P_0$ と $R \subseteq P_0$ を使って,「$Q$のうち1つ以上が成り立ち,しかも,$R$のうち1つ以上が成り立たない」と記述できる.論理式で書けば,$\bigvee_{q \in Q} q \land \bigvee_{r \in R} \neg r$ となる.
  • 「受取る」タイプの条件は,$Q \subseteq P_0$ と $R \subseteq P_0$ を使って,「$Q$のすべてが成り立つか,または,$R$のすべてが成り立たない」と記述できる.論理式で書けば,$\bigwedge_{q \in Q} q \lor \bigwedge_{r \in R} \neg r$

ただし,$Q$, $R$ は空ではないことにします.

$P_0$ をうまく決定できれば,あとは後述する方法に従って機械的に解ける,ということになります.

良く現れる形

一般には,$Q$ と $R$ を使って上のように表現できますが,頻出するのは次の形かと思います.
$p$, $q$ を $P_0$ の命題とします.

支払う条件

  • p が成り立つ ($p$)
  • p が成り立たない ($\neg p$)
  • p が成り立ち,q が成り立たない ($p \land \neg q$)
  • p か q の少なくとも一方が成り立つ ($p \lor q$)
  • p か q の少なくとも一方が成り立たない ($\neg p \lor \neg q$)

受取る条件

  • p が成り立つ ($p$)
  • p が成り立たない ($\neg p$)
  • p が成り立たないか,q が成り立つ ($\neg p \lor q$)
  • p と q の両方が成り立つ ($p \land q$)
  • p か q の両方が成り立たない ($\neg p \land \neg q$)

たとえば,支払う条件の一般形で,$Q = \{p\}$, $R = \{False\}$ としますと,1番目に挙げた「pが成り立つ」が得られますし,$Q = \{True\}$, $R = \{p, q\}$ としますと,5番目に書いた「pかqの少なくとも一方が成り立たない」が得られます.

適用例.その1

MUL

AtCoder Regular Contest 085 の 問題E. MUL です.表現しなければならない規程は以下の通りです.

  • $i$ が $j$ の約数である時,宝石 $i$ を割ったら,宝石 $j$ を割らなければならない.
  • $a_i > 0$ なる $i$ について,宝石 $i$ が割られなければ,$a_i$ 受取る.
  • $a_i < 0$ なる $i$ について,宝石 $i$ が割られなければ,$- a_i$ 支払う.

使用する命題の集合 $P_0$ は,次の命題の全体とします.

  • $p_i$ ... 宝石 $i$ を割る.

すると,3つの規程が,前節の条件を満たすように表現できます.

  • $i$ が $j$ の約数であるような$i$, $j$ に対し,「$p_i$ が成立して $p_j$ が成立しない」とき,$\infty$ 支払う.
  • $a_i > 0$ なる $i$ について,「$p_i$が成り立たない」とき,$a_i$ 受け取る
  • $a_i < 0$ なる $i$ について,「$p_i$が成り立つ」とき,$-a_i$ 支払う

FoxAndGo3

診断人さんのスライド 36~54 でとり上げられている問題です.そこでは,うまくいくグラフと,そうでないグラフが説明されています.

$P_0$を,次の命題全体とします.

  • $p_{ij}$ ... 位置 $(i, j)$ に黒を置く
  • $q_{ij}$ ... 位置 $(i, j)$ の白を取り除く

すると,次のように条件が書けます.

  • 何も置かれていない位置 $(i, j)$ について,
    • $p_{ij}$が成り立つとき1支払う
    • $p_{ij}$が成り立たないとき1受け取る
  • 白石が置かれている位置 $(i, j)$ について,
    • $q_{ij}$が成り立つとき1受け取る
    • $(i,j)$ の隣接4点 (この問題では,隣接4点には白はないと仮定されている) のうち,何も置かれていない点 $(x, y)$ について,$q_{ij}$が成立して $p_{xy}$が成立しなければ,$\infty$ 支払う.

これでうまく表現できました.注意すべき点としては,$P_0$ を次のように定めたのではうまくいかない,ということがあります.

  • $p_{ij}$ ... 位置 $(i, j)$ に黒を置く
  • $q'_{ij}$ ... 位置 $(i, j)$ の白を置いたままにする.

こうしますと,最後の規程に現れる条件が,「$q'_{ij}$と$p_{xy}$がともに成立しないならば」となってしまいます.これは,受取りの条件としては正当ですが,支払の条件に使うことはできません.

グラフの構成

まず,問題を言い換えて,受取りに関する規定「条件Aが成り立てばB受取る」を,「条件Aが成り立たなければ,B支払う」に変更します.あらかじめ B を受取っておいてこの新たな規程を適用するのと,もとの問題は同じ事になります.したがって,言い換えた後の問題を解いて,結果に Bを加えれば良いです.ここで,受取りの条件が満たすべき形の否定を作ると,支払の条件が満たすべき形になっていることに注意してください.

グラフを構成します.まず,$P_0$ の各要素に対応するノードを作ります.つぎに,各支払規程を見ます.条件は,$Q$ と $R$ を使って表されています.支払額を$C$とします.

  • 新しいノード $u$ と $v$ を作る.
  • $Q$ の各要素に対応するノードから,$u$ へ,容量$\infty$の辺を張る.
  • $v$ から $R$ の各要素に対応するノードへ,容量$\infty$の辺を張る.
  • $u$ から $v$ へ,容量$C$の辺を張る.

ただし,$Q$ や $R$ が単元集合の時には,$u$ や $v$ を作るのを省略して,その単元自身を用いるものとします.

ノードTrueとFalseの最小カットが,もとめる最小値になっています.

正当性

以下の2つを示します.

  1. $P_0$への任意の真偽値割り当てに対し,その時の支払額が最小カット以上であること
  2. 支払額が,最小カットと等しくなるような$P_0$の真偽値割り当てがあること

まず,1.です.ノードは,$P_0$ の要素に対応しているか,または,規程の条件 $Q$, $R$ に対応しているかのいずれかです.ノードの集合$U$ を,つぎのノードの全体と定義します.

  • ノードが$P_0$の要素に対応しているときには,その対応している要素に真が割り当てられている
  • $Q$に対応しているときには,$Q$の要素の少なくともひとつに真が割り当てられている
  • $R$に対応しているときには,$R$の要素のすべてに真が割り当てられている

$V$ は,$U$ に属さないノードの全体とします.すると,$(U, V)$ は,True-False カットであり,支払額がこのカットの値となることが確認できます.

次に2.です.最小カット$(U_0, V_0)$ をとり,$P_0$ に対する真偽値割り当てとして,$p \in P_0$ に対応するノードが $U_0$ に属しているときに真,そうでないときに偽とするものを取ります.このときの支払額 $C'$ がカットの値 $C_0$ と一致することを言います.帰謬法で,$C_0 \neq C'$ としましょう.1.より,$C_0 < C'$ です.特に $C_0 < \infty$ です.すると,規程に現れる$Q$と$R$の組で,$Q$がすべて偽で,$R$がすべて真になっているものであって,この$Q$と$R$に対応するノード$s$と$t$について,$s \in U_0$, $t \in V_0$ となるものが存在しなければなりません.なぜなら,そのようなものが無いとすると,グラフ上の有限容量の辺でカットの値に寄与できるものは,$Q$ のうち一つ以上が真で,$R$のうち一つ以上が偽のものだけですが,そのようなものを全部集めても $C'$ しかないからです.さてこの場合,カット $(U_0 - \{s\}, V_0 \cup \{s\})$ を考えると,カット $(U_0, V_0)$ よりも真に値が小さくなってしまいます.矛盾が導かれました.

適用例.その2

The Year of Code Jam

診断人さんのスライド 56~68 でとりあげられている問題です.

今度は,次の命題を考えてもうまくいきません:

  • $p_d$ ... 日付 $d$ のマスを青にする.

条件を書くと,次のようになってしまいます.

  • 「?」が書かれている日付 $d$ に対し,「$p_d$が成立すれば,4受け取る」
  • 隣接する日付の組 $(d, e)$ に対し,「$p_d$が成立し,$p_e$も成立すれば 2 支払う」

前者は適用可能な条件ですが,後者はそうではありません.

そこで,診断人さんのスライドにあるのと同じ工夫をすることになります.命題を次のようにします.

  • $p_d$ ... 日付 $d$ が奇数マスかつ青であるか,偶数マスかつ白であるかのいずれかである.

この言い換えによって,条件は以下のようになります.

  • 「?」が書かれている奇数マス日付$d$について,「$p_d$が成立すれば,4受け取る」
  • 「?」が書かれている偶数マス日付$d$について,「$p_d$が成立しなければ,4受け取る」
  • 隣接する日付の組 $(d, e)$ に対し,「$p_d$が成立し,$p_e$が成立しなければ 2 支払う.」(ただし,奇数マスに入っている方を$d$とする)

これで問題が最小カットに帰着できました.

Surrounding Game

診断人さんのスライド70~84です.

マス$v$に隣接するマスの集合を $N(v)$ と書きます.命題をまず次のように考えてみます.

  • $p_v$ ... マス$v$に石を置く.

すると,条件は以下のようになります.

  • $b_v - c_v > 0$のとき,$p_v$ が成り立てば,$b_v - c_v$ 受け取る.
  • $b_v - c_v < 0$のとき,$p_v$ が成り立てば,$c_v - b_v$ 支払う.
  • $p_v$ が成り立たず,すべての $w \in N(v)$ に対して $p_w$ が成り立つならば,$b_v$ 受け取る.

3番目の条件は,前節に書いた形と似ているようにも見えますが,残念ながら,肯定と否定が混じっています.さきほどの The Year of Code Jam と同じように,奇数マスと偶数マスでyes/noを入れ換えればうまくいきます.

  • $p_v$ ... $v$が奇数マスでありかつ石を置かれているか,または,$v$が偶数マスでありかつ石が置かれていない.

条件を書き直します.

  • $b_v - c_v > 0$となる奇数マス$v$について,$p_v$ が成り立てば,$b_v - c_v$ 受け取る.
  • $b_v - c_v > 0$となる偶数マス$v$について,$p_v$ が成り立たなければ,$b_v - c_v$ 受け取る.
  • $b_v - c_v < 0$となる奇数マス$v$について,$p_v$ が成り立てば,$c_v - b_v$ 支払う.
  • $b_v - c_v < 0$となる偶数マス$v$について,$p_v$ が成り立たなければ,$c_v - b_v$ 支払う.
  • 奇数マス$v$ について,すべての $w \in \{v\} \cup N(v)$ に対して $p_w$ が成り立つならば,$b_v$ 受け取る.
  • 偶数マス$v$ について,すべての $w \in \{v\} \cup N(v)$ に対して $p_w$ が不成立ならば,$b_v$ 受け取る.

前節の形になりましたので,最小カットに帰着できます.

Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Sign upLogin
0
Help us understand the problem. What are the problem?