燃やす埋める問題
問題設定(例題)
$a_1,a_2,\ldots,a_N$ の $N$ 個の廃棄物がある。全て燃やすか埋めるかして処分する。それぞれにコストがかかる。
| $a_1$ | $a_2$ | … | $a_N$ | |
|---|---|---|---|---|
| 燃やす | 50 | 60 | … | 130 |
| 埋める | 100 | 100 | … | 100 |
さらに、「$a_1$ を燃やすなら、$a_2$ は埋めると罰金100円」など、2つの廃棄物の関係性に依存する追加条件がある。
かかるコストを最小化せよ。
解き方
追加条件が無ければ、単純に$a_1 \ldots a_N$についてコストの安い方を選べば良いだけだが、追加条件のためにあちらを立てればこちらが立たずで、こんがらがってくる。
これは、グラフで表すことで、最小カットで解くことができる。廃棄物をノード、処分方法をリンクとし、リンクコストを処分コストとする。
ただし、追加条件次第で解けないことがある。この解法で解ける条件と解けない条件は後述する。
グラフ化
まず、追加条件の無い、燃やすコストと埋めるコストだけを考えると、以下のようなグラフになる。廃棄物を縦に並べ、s と t を追加する。
燃やす 埋める ,- 50→ a1 -100--, | ↓ s -60→ a2 -100→ t | ↑ `-130→ a3 -100--'
これの s - t 間を最小カットするには、左右で小さい方のリンクを選べばよい。コストの安い方を選択することを表す。
リンクをカットする＝リンクに対応した処分方法を取る＝コストを支払うことを意味する。
燃やす 埋める ,- | → a1 -100--, | ↓ s -| → a2 -100→ t | ↑ `-130→ a3 - | --' 50+60+100 = 210
ここに「$a_2$ を燃やし $a_3$ を埋めると罰金100」という条件を追加するには、上の状態でまだ最小カットが成立しないように、辺を追加すればよい。
燃やす 埋める ,- | → a1 -100--, | ↓ s -| → a2 -100→ t | ↑100 ↑ `-130→ a3 - | --' 50+60+100 = 210 ... 追加で100?
$a_3$ → $a_2$ にコスト100の辺を追加した。こうすると、まだ s - t 間はつながっている。追加でカットしないといけない＝罰金を表現する。
こうなると、そもそも $a_3$ も燃やした方が安くなる。
燃やす 埋める ,- | → a1 -100--, | ↓ s -| → a2 - 100→ t | ↑100 ↑ `- | → a3 -100--' 50+60+130 = 240
これが罰金を考慮した最小コストとなる。
制約
負辺はだめ
最小カットは、結果的に最大流で解くので、負辺があると上手くいかない。（最大フロー最小カット定理）
| $a_1$ | $a_2$ | $a_3$ | |
|---|---|---|---|
| 燃やす | -50 | -60 | +130 |
| 埋める | +100 | -100 | +100 |
+50は50円もらえて、-100は100円支払う、なんて時は、どうやって辺のコストを設定するか。
全て良い方を選んだと仮定
全て良い方の選択肢を選び、もらえるお金はもらった上で、そこからの差分を「コスト」と見なす。
あらかじめ、100+130 = 230円はもらったと仮定。その上で、差分をコストとすると、
| $a_1$ | $a_2$ | $a_3$ | |
|---|---|---|---|
| 燃やす | 150 | 60 | 0 |
| 埋める | 0 | 100 | 30 |
となり、負のコストが消える。あとは答えから、230を引けばよい。
解けない追加条件
たとえばこの例では「$a_1$ と $a_2$ を同時に埋めると罰金」など、2つの廃棄物に同じ処理を施す条件は、表現できない。
a1-a2間の辺をどう張ろうと、 最初から最小カットが成立している ,- | → a1 -100--, | ↓? ↓ s -| → a2 -100→ t | ↑ `-130→ a3 - | --'
厳密には、追加条件がこの1つだけなら、とりあえずは $a_1$ のみ選択肢の左右を逆にすることで対応できる。燃やす埋める問題のグラフでは、左右の行動を個々に入れ替えても問題ない。
入れ替える
,-100→ a1 - | --,
| ~~~ ~~~ ↓
s -| → a2 -100→ t
| ↑
`-130→ a3 - | --'
辺を追加、最小カットが成立しなくなる
,-100→ a1 - | --,
| ↓100 ↓
s -| → a2 -100→ t
| ↑
`-130→ a3 - | --'
この例のように、「同時にやってはいけない2つ」は、一方が左、もう一方が右のリンクである必要がある。
なので、さらに追加条件を加え、どうしてもどれかは同じ行動が同じ側に来ざるを得なくなる場合、カットを阻止するように辺を追加できない。
これは問題依存なので、この解法が適用可能かどうか、確かめないといけない。
追加条件次第で、可能なことも
たとえば、「$a_i$ と $a_j$ を同時に○○してはいけない」という条件があっても、「その条件の時は、必ず $i$ は偶数で $j$ は奇数」などという制約があるなら、$i$ の偶奇によって左右の行動を入れ替えればよい。
N個のノードに対し、この「同じなら罰金」系の制約条件でペアとなった全ての組にリンクを張ったとき、グラフが二部グラフとなっていれば、入れ替えが可能となる
ただ、その場合、今度は「$a_k$ を燃やし $a_h$ を埋めてはいけない」という条件があったら、$k$ と $h$ の偶奇は一致してなきゃいけなくなってくるなど、結構ややこしくなってしまうのは否めない。
一つの例として、「敷き詰められる正方形タイルの色を2色から決定する」「隣り合うタイルの色が同じだとスコアが減点される」「スコアを最大化」みたいな問題では、隣り合うタイル同士を結ぶグラフは必ず二部グラフとなるので、この方法が可能となる。
Google Code Jam World Finals 2008 - Problem E. The Year of Code Jam
負の罰金なら可
追加条件を「$a_1$ と $a_2$ を同時に埋めると賞金100」とすると、適用可能となる。
- まず、無条件で100もらったと仮定
- ダミーノード $a_4$ を追加。燃やすとコスト100、埋めてもコスト0
- $a_4 \rightarrow a_1$ と $a_4 \rightarrow a_2$ に、コスト無限大の辺を追加
こうすると、グラフは以下のようになる。
燃やす 埋める ,- 50→ a1 -100--, | ↑∞ ↓ s -100→ a4 - 0 → t | ↓∞ ↑ `- 60→ a2 -100--' （※a3は省略）
- $a_1$ と $a_2$ を両方埋めると、$a_4$ はコスト0の“埋める”を選択しても最小カットが成立する
- 最初に無条件でもらった100が、賞金となる
- いずれかを燃やすと、コスト∞の辺があるので、$a_4$ はコスト100の“燃やす”を選択せざるを得なくなる
- 最初にもらった100と、増えたコストの100で相殺。賞金がもらえなかったことを意味する
まとめ
グラフ上で、「燃やす」を左側の行動、「埋める」を右側の行動とする
| X を燃やすと罰金 P | s から X にコスト P の辺 |
| X を埋めると罰金 P | X から t にコスト P の辺 |
| X を燃やし、Y を埋めると罰金 P | Y から X にコスト P の辺 |
| Xi も Xj も燃やすと、罰金 P ※ただしi=偶数,j=奇数 ※制約条件はこの形式のみ | 奇数番目のXkの選択肢を左右反転 XjからXiにコストPの辺 |
| Xi も Xj も埋めると、罰金 P ※ただし（同上） | 奇数番目のXkの選択肢を左右反転 XiからXjにコストPの辺 |
| X も Y も燃やすと、賞金 P | あらかじめPもらう ダミーノードZを追加 s→Z=0, Z→t=P, Z→X=∞, Z→Y=∞ の辺 |
| X も Y も埋めると、賞金 P | あらかじめPもらう ダミーノードZを追加 s→Z=P, Z→t=0, Z→X=∞, Z→Y=∞ の辺 |
上に無い条件でも、他の制約次第で工夫の余地はあるようだ。（もちろんどうしても無理なものもある）
ノードがメインか、リンクがメインか
これまで、「リンクを選択肢と見做し、カットすることが選択肢を選ぶことだ」という考え方で進めてきたが、ノードをメインとする考え方もある。
やってることは似ていても、考え方を変えるだけで実際の問題への適用しやすさが異なってくる、かも。
- 全てのノードを、Sグループ と Tグループ に分ける
- s から到達できるノードはSグループ、到達できないノードはTグループとする
- s - t 間を最小カットする
XをSグループにするには、右側の辺をカットすることになるので、行動的には左右が逆転することに注意。
| Xを燃やすと罰金P Xを埋めると罰金Q | s→XにコストQの辺、X→tにコストPの辺 |
| Xを燃やし、Yを埋めると罰金P | X→YにコストPの辺 |
制約条件の辺を追加する方向は、こちらの方が直感的かも？
バリエーション
工夫次第でいろいろできるらしい
「何もしない」の選択肢
※正しく理解できていないので、間違っているかも
続：『燃やす埋める』と『ProjectSelectionProblem』 - とこはるのまとめ
- 「何もしない」の選択肢が追加される
- 制約条件は、「Xを燃やしてYを埋めると罰金P」という形式のみ
選択肢を増やすだけならノードを複製して横に繋げばよいが、単に繋ぐと制約条件の辺が追加できなくなる。
燃やす 埋める 何もしない ,- 50→ a11 -100→ a12 - 0 --, | ↓ s --60→ a21 -100→ a22 - 0-→ t | ↑ `-130→ a31 -100→ a32 - 0 --'
3択の選択肢を、無理矢理2択にする。簡単のため、対象を1個にする。
| A | |
|---|---|
| 燃やす | 100 |
| 埋める | 50 |
| 何もしない | 80 |
下図ようにグラフを作る。ノードを2つに分割する。
燃やす 何もしない(1) ,-100→ A1 - 80 --, s ↑∞ t `- 80→ A2 - 50 --' 何もしない(2) 埋める
「燃やす」と「埋める」を同時に行うのは矛盾なので、最小カットが達成できないよう、A2からA1へ無限大の辺を張る。
- 「燃やす」と「何もしない(2)」をカットしたときは、燃やす
- 「何もしない(1)」と「埋める」をカットしたときは、埋める
- 「何もしない(1)」と「(2)」をカットしたときは、何もしない
どの選択肢も余分に「何もしない」を1つだけカットするので、あらかじめ「何もしない」コストの補償金をもらっておく。
この場合、「何もしない(1)」と「埋める」をカットするのが最小となり、埋めるのがよいとわかる。コストは50+80=130に、あらかじめもらった80を引き、50となる。
対象を2つ以上に増やす。
| A | B | |
|---|---|---|
| 燃やす | 100 | 200 |
| 埋める | 50 | 240 |
| 何もしない | 80 | 500 |
- 制約条件
- Bを燃やし、Aを埋めると罰金100
制約条件を加える前のグラフは、このようになる。
,-100→ A1 - 80 --, | ↑∞ | |- 80→ A2 - 50 --| s t |-200→ B1 -500 --| | ↑∞ | `-500→ B2 -240 --'
この状態で最小カットすると、
,-100→ A1 - | --, | ↑∞ | |- 80→ A2 - | --| s t |- | → B1 -500 --| | ↑∞ | `- | → B2 -240 --'
これでは、Aが埋められ、Bが燃やされているので、罰金が発生する。辺を追加する。
,-100→ A1 - | --, | ↑∞ | |- 80→ A2 - | --| s ↓100 t |- | → B1 -500 --| | ↑∞ | `- | → B2 -240 --'
(埋められる方)の“2”から、(燃やされる方)の“1”へとリンクを張ればよい。
こうすると最小カットは
,-100→ A1 - | --, | ↑∞ | |- | → A2 - 50 --| s ↓100 t |- | → B1 -500 --| | ↑∞ | `- | → B2 -240 --'
となり、Aは何もしないのがよいということがわかる。
参考
Project Selection Problemという、似た考え方の解法もある。
