とこはるのまとめ

多分考えたことがまとまっているはずです。きっと。おそらく。

続:『燃やす埋める』と『ProjectSelectionProblem』

http://tokoharuland.hateblo.jp/entry/2017/11/12/234636の続きです。
煽り気味な記事を書いたのは反省中です。気を悪くされた方がいましたら申し訳ありません。
こういうのは無駄に人の心を煽っても仕方なくて、ACできたら正義なのでどちらを選んでも問題はない、と考えた方がよかったかと思います。
また、前回の記事で抜けていた点として燃やす埋めるは最小化問題で、ProjectSelectionProblemは最大化というところも大きな違いでした。これは先ほど少しだけ追記しました。

ところで、今日は続きの話題を書きます。

いろはちゃんから上のような疑問をいただきました。

答えはできます、が、従来と比べて思考量が減るかは判断できないのでどっちでもいい気がします、というところです。

3つに分けるタイプの問題?

いろはちゃんの問題ですが、要するに次の問題だと認識しています。

これの解法ですが、まず2N個のProjectを用意します。
次にはじめのN個には次の意味を持たせます
B(ベース)にいる <=> iは何もしない
Aにいる <=> iを燃やす

残りのN個には次の意味を持たせます
B(ベース)にいる <=> i を埋める
Aにいる <=> iは何もしない

このとき、禁止制約は 『iを燃やすかつiを埋める』、と、『iを燃やすかつjを埋める』という形の制約になります。
この条件は結局『iを燃やすならばjは何もしない』とすれば回避でき、これはProjectの世界で『iをAにおけば、(j+N)はAに置かないといけない = 罰金INF』ということなので、めでたくProjectSelectionで書けました。

総コストについてですが、まず最初B(ベース)にいることを考えるため、埋める利得の総和を事前に足しておきます。
次に、ProjectSelectionProblemの答えにおける総和部分はBから見てAのスコアが相対的によいプロジェクトでのスコアの総和なので、これは結局燃やす利得の総和です。
最後に、ProjectSelectionProblemの答えにおけるmaxflowの値を引けば、これがもともと知りたかった3つに分けるタイプの問題の答えになります。

結局反転は登場せざるを得ないし、3択を2択にするのがトリッキーなので、そこのややこしさは回避できないでしょう。また、できるグラフは従来の考え方と大差ないはずです。
ただ、もともと最大化問題のフレームワークなので、minとmaxがごっちゃになるリスクは減るんじゃないかとは思います。

そう考えると、最小化問題だと燃やす埋めるで考える方がやりやすいのか、気になります。意見などありましたらお寄せください。

今日のまとめ

前回の記事のごめんなさい
3つに分ける問題も扱えます