燃やす埋める問題
問題設定(例題)
$a_1,a_2,\ldots,a_N$ の $N$ 個の廃棄物がある。全て燃やすか埋めるかして処分する。それぞれにコストがかかる。
| $a_1$ | $a_2$ | … | $a_N$ | |
|---|---|---|---|---|
| 燃やすコスト | 50 | 60 | … | 130 |
| 埋めるコスト | 100 | 120 | … | 90 |
さらに、「$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つ」は、一方が左、もう一方が右のリンクである必要がある。
なので、さらに追加条件を加え、どうしても同じ行動が同じ側に来ざるを得なくなる場合、カットを阻止するように辺を追加できない。
これは問題依存なので、この解法が適用可能かどうか、確かめないといけない。
この条件を満たすかどうか、どう確かめられるかは未学習。（一筋縄ではいかなそう）
追加条件が二部グラフっぽければ可能
ただ、追加条件の与えられ方に特徴があると、比較的明快に可能とわかる場合がある。
たとえば2部グラフとなる場合。
- 「$a_i$ と $a_j$ を同時に燃やしてはいけない」という条件のみからなる
- ただし、全体を2グループ $A,B$ に分けることができ、$a_i$ は $A$ から、$a_j$ は $B$ からしか選ばれない
この場合、$B$ グループだけ、燃やすと埋めるの意味する辺を入れ替えればよい。
一つの例として、グリッドにドミノを敷き詰めて、その敷き詰め方でスコアが決定される、みたいな問題では、 隣り合うタイル同士を結ぶグラフは必ず二部グラフとなるので、この方法が可能となる。
負の罰金なら可
追加条件を「$a_1$ と $a_2$ を同時に埋めると賞金100」とすると、適用可能となる。
辺の張り方が結構変わってくる。追加条件も1つの頂点として表す。
- まず、無条件で100もらったと仮定
- ダミーノード $b_1$ を追加。燃やすとコスト100、埋めてもコスト0
- $b_1 → a_1$ と $b_1 → a_2$ に、コスト無限大の辺を追加
こうすると、グラフは以下のようになる。
燃やす 埋める ,- 50→ a1 -100--, | ↑∞ ↓ s -100→ b1 - 0 → t | ↓∞ ↑ `- 60→ a2 -100--' （※a3は省略）
- $a_1$ と $a_2$ を両方埋めると、$b_1$ はコスト0の“埋める”を選択しても最小カットが成立する
- 最初に無条件でもらった100が、賞金となる
- いずれかを燃やすと、コスト∞の辺があるので、$b_1$ はコスト100の“燃やす”を選択せざるを得なくなる
- 最初にもらった100と、増えたコストの100で相殺。賞金がもらえなかったことを意味する
この場合は、頂点が3個以上でもよい。賞金を得るために同時に満たさなければならない頂点全てに辺を張るとよい。
- 「$a_1,a_2,a_3$ を同時に埋めると賞金100」→「$b_1$ から $a_1,a_2,a_3$ にコスト∞の辺」
また、追加条件が逆に「$a_1$ と $a_2$ を同時に燃やすと賞金100」だった場合は、辺の張り方は以下のようになる。
燃やす 埋める ,- 50→ a1 -100--, b1の、燃やす辺が0, 埋める辺が100 と逆転 | ↓∞ ↓ a1,a2 から b1 へと、辺の方向が逆転 s - 0→ b1 -100→ t | ↑∞ ↑ `- 60→ a2 -100--'
まとめ
グラフ上で、「燃やす」を左側の行動、「埋める」を右側の行動とする
| $a_i$ を燃やすと罰金 $P$ | $s$ から $a_i$ にコスト $P$ の辺 |
| $a_i$ を埋めると罰金 $P$ | $a_i$ から $t$ にコスト $P$ の辺 |
| $a_i$ を燃やし、$a_j$ を埋めると罰金 $P$ | $a_j$ から $a_i$ にコスト $P$ の辺 |
| $a_i$ も $a_j$ も燃やすと、罰金 $P$ ※ただし$a_i,a_j$は二部グラフ上の別グループの頂点 | いずれかの選択肢を反転（$a_j$ とする） $a_j$ から $a_i$ にコスト $P$ の辺 |
| $a_i$ も $a_j$ も埋めると、罰金 $P$ ※ただし（同上） | いずれかの選択肢を反転（$a_j$ とする） $a_i$ から $a_j$ にコストPの辺 |
| $a_i,a_j,\ldots$ を全て燃やすと、賞金 $P$ | あらかじめ $P$ もらう ダミーノード $b$ を追加 $s→b=0, b→t=P, a_i→b=∞, a_j→b=∞,\ldots$ の辺 |
| $a_i,a_j,\ldots$ を全て埋めると、賞金 $P$ | あらかじめ $P$ もらう ダミーノード $b$ を追加 $s→b=P, b→t=0, b→a_i=∞, b→a_j=∞,\ldots$ の辺 |
上に無い条件でも、他の制約次第で工夫の余地はあるようだ。（もちろんどうしても無理なものもある）
ノードがメインか、リンクがメインか
これまで、「リンクを選択肢と見做し、カットすることが選択肢を選ぶことだ」という考え方で進めてきたが、ノードをメインとする考え方もある。
やってることは似ていても、考え方を変えるだけで実際の問題への適用しやすさが異なってくる、かも。
- 全てのノードを、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という、似た考え方の解法もある。
劣モジュラ関数という概念を使って、どんな問題なら可能かを説明されている。
