Zenn
🦁

Max Closure Problem の説明

2023/03/27に公開
アルゴリズム
グラフ
tech

ゴール

Max Closure Problem がなぜ Max-flow/Min-cut で解けるのかよくわからず、私が見つけた中では一番わかりやすい資料を見ても最終的に腑に落ちるまで時間を要したので、また忘れた時に同じことをしなくてもいいように自分のレベルに噛み砕いて記録を残します。上記のリンクは Jeff Erickson 氏によるイリノイ大学の授業をベースにした本で、この 11.7 を読んですんなり理解できる場合は特にこの先を読む必要はないです。

Max Closure Problem とは

これもどうせ忘れると思うので後で読んだ時に思い出しやすいように簡単にまとめます。

英語 Wikipedia の Closure Problem の説明をそのまま借ります。Directed Graph の Closure とは、あるグラフの頂点の集合のうち、特にその集合から外向きのエッジが存在しない集合のことを指しているそうです。(問題のカテゴリーではなくもっと具体化された問題に直接出会ったので Closure とはなんなのかこれを読むまでそもそも知らなかった) Max Closure Problem とは vertex-weighted directed graph から max-weight / min-weight となる Closure を探す問題です。

具体的には以下のような問題です。

  • t_1,...,t_i の i 個のタスクがある
  • それぞれのタスクをこなすとそれそれのタスクに応じた報酬が得られる
  • 報酬は正の値であるとは限らず、負の値もあり得る
  • 一部のタスク間には prerequisite の関係があり、指定されたタスクを先にこなさなければそのタスクを実行することはできない
  • どのタスク群を選択すれば最終的な報酬を最大化できるだろうか？

余談ですが、こうしてみると確かに問題のセットアップとしてはコストは頂点に紐づいているので vertex-weighted directed graph なのですが問題を解くときはエッジに weight をつけるのでちょっと混乱するような気もします。

Max-flow / Min-cut とは

これもどうせ忘れると思うので後で読んだ時に思い出しやすいように簡単にまとめます (2 回目) 。ただしこのコンセプト自体は難しいとかではなく覚えているか覚えてないかだと思うのでゆるっとまとめます。将来の自分、忘れたら Lecture16 のスライドか Lecture note でも読み直してください。(受講生でなくてもスライドは見られたと思うので元々ご存じでない方もこちらでどうぞ)

  • グラフ (のエッジ) に対してキャパシティとフローを設定する
  • フローはコストに近い概念で、キャパシティ以上のフローを指定することはできない
  • source (s, 始点) ノードと sink (t, 終点) ノードを除き、全てのノードの incoming edges のフローと outgoing edges のフローの合計は一致していなければならない (入った分出ていく)
  • s から出ていくフローと t に入るフローは等しくなければいけない
  • s から t に対して一度にできるだけ多くのフローを送りたいとして、最大化できる割り振り方を Max-flow と呼ぶ
  • Max-flow (状態の割り振り方) のフローは、グラフ上のノードを s を含む頂点の集合 S と t を含む頂点の集合 T にグラフの頂点を分けたとき、S から T に向かうエッジ (⚠️ 反対方向のエッジのフローはカウントしない) のフローの合計が最小になる分け方の値で評価する
  • なんでそうやって評価するかというと、それが一度に送ることができるフローのボトルネックになっているから
  • この値を Min-cut という (cut はある頂点の集合から他の頂点の集合へまたがるエッジ群のこと)

Max-flow / Min-cut で Max Closure Problem を解く

最初に解法を一気にまとめます。

  • s と t を準備する
  • s から正の報酬 c_r をもつタスク t_r に対してエッジを追加する。この時、キャパシティは c_r で初期フローは 0
  • 負の報酬 c_v をもつタスク t_v から t に対してエッジを追加する。この時、キャパシティは -c_v で初期フローは 0 (つまりキャパシティは正の値になる)
  • タスク t_v が t_u の prerequisite である場合、t_u から t_v にキャパシティ及びフローともに \infty のエッジを追加する
  • 完成したグラフで Max-flow / Min-cut を求める
  • Max-flow 状態の S から s を引くと、報酬を最大化できるタスクの集合が得られる (s は問題を解くためだけの存在なので実際のタスクではない)

完成したグラフのイメージは最初にご紹介した資料の Figure 11.9 をみるとわかりやすいです。

なんでこれでとけるのか

ここが当初つまっていたところです。始めに、理論上可能な限り最大の報酬は正の報酬のタスクの報酬を合計した値 P となリます。実際はここにタスク間の依存という制約が入り、得られる報酬は

P - (取れなかった正のタスクの報酬の合計) + (取ることにした負のタスクの報酬の合計)
と考えることができます。これを式変形すると、
P - (取れなかった正のタスクの報酬の合計 - 取ることにした負のタスクの報酬の合計)
といえます。

上記のグラフに戻ります。ここで S から T に向かうエッジ (つまり Min-cut 上のエッジ) は S から正のタスクへのエッジと負のタスクから T へのエッジの２種類になります。これはまさしく上記の P から引いている値と一致します。当然、この値が小さくなればなるほど多くの報酬が残るので報酬を最大化できるというわけです。

依存間のエッジを \infty に設定する目的は、そうすることで Max-flow / Min-cut を求めた時に依存を無視してタスクを取ってしまうことを防ぐためです。間で S と T に分けられることがなくなるので、タスク t_v が t_u の prerequisite である場合、t_v だけをとるか、t_v と t_u を両方とるかの２択になり、t_u だけを取ることがなくなります。

Discussion