最小カット勉強会
2021-03-19 サイボウズラボ勉強会
ある種の最適化問題を解くときに使える「最小カット問題に帰着させて解く」を解説する
簡単な最適化問題
二択の選択肢がN個ある
選択肢を1つ選ぶと100円もらえる
しかし選ぶのにCi円のコストが掛かる
利益を最大にする選択は？
解答
利益 100 - Ci が正のものを選ぶ
簡単な最適化問題2
二択の選択肢がN個ある
選択肢を1つ選ぶと100円もらえる
しかし選ぶのにCi円のコストが掛かる
選択肢をM個選ぶ場合の利益を最大にする選択は？
解答
ソートして利益の大きい方からM個取る
一歩進んだ問題
二択の選択肢がN個ある(N=20)
選択肢を1つ選ぶと100円もらえる
しかし選ぶのにCi円のコストが掛かる
ある選択肢iを選んで選択肢jを選ばなかった場合、追加でDijのコストが掛かる
非ゼロのコストはM個(M=100)
利益を最大にする選択は？
解答
$ 2^N通り全探索する
$ 2^{20} = 1048576 \approx 10^6 で、Dijの計算に * 100 だから $ 10^8回くらいの計算
Python3 11.3 s ± 173 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
PyPy3 1.1 s ± 37 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
今回解く問題
二択の選択肢がN個ある(N=100) ←🤔
選択肢を1つ選ぶと100円もらえる
しかし選ぶのにCi円のコストが掛かる
ある選択肢iを選んで選択肢jを選ばなかった場合、追加でDijのコストが掛かる
非ゼロのコストはM個(M=100)
利益を最大にする選択は？
全探索だとどうなる？
$ 2^{100} \approx 10^{30}
仮に1秒で$ 10^{10}回の計算ができる機械を使ったとしても$ 3\times 10^{12}年かかる
解答
最小カット問題に帰着し、最大フロー最小カット定理で最大フロー問題に変換してDinicアルゴリズムで解く
かなり速い
N=M=100の時は1ミリ秒未満だった
1000回繰り返した時間
Python3 858 ms ± 222 ms per loop (mean ± std. dev. of 5 runs, 1000 loop each)
PyPy3 214 ms ± 139 ms per loop (mean ± std. dev. of 7 runs, 1000 loop each)
N=M=10000でも0.2秒くらい
Python3 243 ms ± 40 ms per loop (mean ± std. dev. of 5 runs, 1 loop each)
PyPy3 114 ms ± 45 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
N=M=100000で、PyPyなら1〜2秒ぐらい
PyPy3 1.4 s ± 172 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
カットとは
グラフ G(V, E) の頂点 V の 2 分割 (S, T) をカットとよぶ。
https://gyazo.com/43aabb7d6bc127d28e6a30af2587f230
「頂点の集合」を二つに分けるだけ
物理的なイメージとしては「二色に塗り分ける」がフィットする
カットという言葉に釣られて「グラフを二つに切る」と考えるのは混乱の元
辺は関係ない
これもカットです
https://gyazo.com/bef1cd4eb2267d237c915778a1bbcedb
世の中にはここで「フローがどうこう」と言っちゃう説明文もあるけど、フローを考えるのはもっと後の「最小カットを最大フローに対応づける」フェーズで良いので、ここでは気にしない
この段階でフローのことを考えるのも混乱の元。上記のカットに対応するフローはないので。
最小カット問題とは
(今回は有向グラフの話しかしない)
有向グラフ$ G = (V, E) のカット $ (S, T) が与えられた時、Gの辺 $ (u, v) \in E のうち $ u \in S, v \in T であるものをカットエッジという。
https://gyazo.com/359c47fe470936b043715e30d037e816
カットエッジの重みの和をカットのサイズといい、サイズが最小のカットを最小カットという。
しばしば「Sに必ず入る頂点s」「Tに必ず入る頂点t」を考えると都合がいい。sとtがそうなるようなカットを「s-tカット」と呼んだりする。
Q: 根本がTで先がSであるような辺はカットエッジではない？
A: 良い質問、次のスライドで理解の確認をする
最小カットの理解の確認
このグラフのs-t最小カットはどうなるでしょう？
https://gyazo.com/168b48ffc582651499fb4f302efeb396
(注釈: 元々の図では頂点を大文字で書いていたが、頂点集合Sと頂点sを区別するために小文字に変えた)
解答
$ a \in T, b \in Sのときカットサイズが3で最小になる
https://gyazo.com/995e58aae1d3cb623ed98988226a491e
カットを「グラフを切る」とイメージしてると「真ん中の5の辺」を切らないでいいのかとか混乱しがち
根本がTで先がSであるような辺なので、カットのサイズに無関係である
頂点を二色で塗り分ける方法がsとtは固定なので4通りある
$ a \in S, b \in Tの時は15
https://gyazo.com/7fc7471991992121307a80ca0a58899e
両方Sや、両方Tの時は6
なので3が最小
再掲
最小カット問題に帰着し、最大フロー最小カット定理で最大フロー問題に変換してDinicアルゴリズムで解く
「最小カット問題とは何か」の説明が終わった
次は下記の問題をどうやって最小カット問題に帰着するか説明する
二択の選択肢がN個ある(N=100) ←🤔
選択肢を1つ選ぶと100円もらえる
しかし選ぶのにCi円のコストが掛かる
ある選択肢iを選んで選択肢jを選ばなかった場合、追加でDijのコストが掛かる。非ゼロのコストはM個(M=100)
利益を最大にする選択は？
利益を最大にしたい=コストを最小にしたい
コストを辺の重みにすると、最小カットでコスト最小化できる
「選択肢iを選ぶ」を「頂点iをSに入れる」とした場合
「選ぶとコストCi」とは
頂点iから頂点tに重みCiの辺を引く
https://gyazo.com/524e99154d4027721faf1f2af574617a
「選ぶと報酬100」とは
報酬は負のコストなので、頂点iから頂点tに重み-100の辺を引く
https://gyazo.com/b2661c356bfd0ec6c234db5bde167683
(後で負辺の除去が必要になるが今は考えなくて良い)
「iを選んでjを選んでないとコストDij」
頂点iから頂点jに重みDijの辺を引く
https://gyazo.com/ccff2a4b41fcc2c2762313d0efd2635a
このグラフの最小カットを求めれば、得たい答えが得られる
具体例
3つの二択選択肢a,b,cがある
選択すると100の報酬がある
選択することにそれぞれ10,70,150のコストが掛かる
aを選んだ時にcを選ばないと追加コスト40が掛かる
構築されるグラフ
https://gyazo.com/33e4fbbd0f7a27cc4e6044c398f4be2b
Q: 「sが分離してていいのか？自明にそこが最小カットになる？」
A: 負の重みの辺があるのでそれが最小解とは限らない
この混乱は「カット」を「グラフを2つに分ける」と混同していることが原因
次のスライドからこの最小カット問題を最大フロー問題に変換する。その過程でsがつながってフローを考えるのに適したグラフになる
次は何をやる？
再掲
最小カット問題に帰着し、最大フロー最小カット定理で最大フロー問題に変換してDinicアルゴリズムで解く
最小カット問題に帰着できた
次は最大フローに変換する
最大フロー問題
辺の重みが非負のグラフ$ G=(V,E)が与えられたとする
この重みをフローの文脈では「容量」と呼ぶ
このグラフの二頂点s, tの間のフローを考える
sからtに水を流すイメージ
最大限流したときにいくら流れるか？が最大フロー問題
https://gyazo.com/8758e36faec9134793d689cb4a264558
G上のフローとは重み付きグラフ$ (V,F)であって:
各辺の重みはGでの容量を超えない: $ F_{ij} \le E_{ij}
s,t以外の頂点iについて入るフローと出るフローが一致する: $ \sum_j F_{ji} = \sum_j F_{ij}
最大フロー最小カット定理
辺の重みが非負のグラフのs-t最小カットのサイズと、sからtへの最大フローの流量は一致することが知られている
今回は証明はしない
ざっくりしたイメージ
https://gyazo.com/c8d058721468b3e5e979c138c46398d0
sからtへの最大フローFの流量をGの容量から減らしたグラフ(残余ネットワーク)を考えると、これは必ず2つ以上の連結成分に別れている
もしそうでないならさらにフローを増やすことができて前提に矛盾する(図中のe)
「グラフの頂点を二つに分ける」はカットで、フローを最大化すると、最小のカットの部分がボトルネックになる
負辺の除去
最小カット問題を最大フロー問題に変換して解く
最大フロー問題では辺の容量は非負である必要があるので、負の辺を取り除く必要がある
ある頂点iに注目すると、その頂点はSに入るかTに入るかのどちらか
https://gyazo.com/7b1dc6c9b05f46514a98a792ac9c34c1
なのでSに入ったときにもTに入ったときにも同額の追加コストcが掛かるようにする
https://gyazo.com/d492c8b93c3c6a738e72feb7f74f30a1
これで負辺が消える
変更後のグラフの最小カットサイズはc増える
負辺除去の過程で足した値の和(offset)を記録しておいて、答えが出てから引く
実例
https://gyazo.com/070b43a35881de73f82f59ef008cf290
負辺の除去
https://gyazo.com/3ac01c8a8e471f03a7c9d8d987883e90
最小カットは-80
https://gyazo.com/c25e7a10f970b57f811c98482084fd7f
(自由な頂点間の負辺の除去は後述)
グラフの最大フローを求める効率の良いアルゴリズム
古典的なFord-Fulkersonを少し改良したもの
(といってもDinicも1970年なので古典の域か)
辺の重みが非負の有向グラフと始点s終点tを入れるとs-t最大フローが出てくる
これが最小カットのサイズに一致する
最大フロー計算後に内部に持ってる残余ネットワーク上で探索して各頂点のsから到達可能な頂点を求めればそれが最小カットのSになる
Dinicの計算量
Dinicの計算量はO(V^2E)とされている
しかし探索ベースの手法なので10^4頂点10^4辺でも必ず10^12回計算するわけではない
先程の問題でN=M=10000の時、グラフは10002頂点、20000辺になる
これが114msで計算できた
どのくらいのサイズの問題まで解けるのか？
N=10000固定で、Mを増やして試したもの(横軸M、縦軸ms) data https://gyazo.com/d8cbd60649437758dbe21e1879792551
この範囲ではほぼ線形(ちょっと悪い？)
これはV固定でEを増やしてるので線形なのは理屈通り
https://gyazo.com/d1c993d547f697e4c28d1e7493af4eef
計算量的にはN^3なのだが、実測は線形に見える
おそらく「この最適化問題から作られるグラフ」が「Dinicに都合の良い特徴」を持ってるのだろう
この実験では各コストを「1から200のランダムな整数」としているので辺の重みが整数でかつ上限がある
この場合、上限をCとして$ O(CV^{2/3}E)
応用
「iを選んだ時、jを選ばなければならない」型の制約
i→jを十分大きなコストにすればよい
https://gyazo.com/a36987a1132e4c91363ac279fc885823
and: 「iを選んだなら、jとkを選ばなけれはならない」
https://gyazo.com/1a4707c9a418f24645f793d329639594
or: 「iまたはjが選ばれたなら、kを選ばなければならない」
https://gyazo.com/931213f2a1843b8e75140af39990962e
ここまでの知識でProject Selection Problemと呼ばれるタイプの問題が解ける
N個のプロジェクトがある
プロジェクトiをやると収入$ r_iが得られる
M個の機械がある
機械jを買うとコスト$ c_jが掛かる
プロジェクトをやるためにはそのプロジェクトに必要な機械を買わなければならない
利益=収入-コストを最大化するにはどのプロジェクトを選べば良いか？
https://gyazo.com/052e99dda764a20363b0fea423f5cf79
応用の続き
not
「iを選んだ時、jを選んではいけない」
これは一般にいつでもできるわけではない
iを選ぶことをiをSに入れることで表現し、jを選ぶことをjをTに入れることで表現する
こうすれば上記の制約を表現できるが、事前に「選択されたときにどちらに入るのか」を決める必要がある
この時、上記の制約は「選択されたときにSに入る頂点」と「選択された時にTに入る頂点」の間にしかかけられない
一言で言えば「二部グラフ」
1列に並んだものや2次元のマス目の隣接関係
交互にSとTにすればよい
マス目を塗る問題で、隣り合うマス目を塗るとコストが発生するケースなどにこれを使う
二択以上の選択肢
できる
三択の例
https://gyazo.com/25b91d664ab124974644d9b1ddcff4e2
同様にN択を、N-1個の頂点を並べて表現できる
同様に実数値の変数に対して「iがx以上なら、jはy以上でなければならない」もできる
https://gyazo.com/72ecfe85ce3e414d2a0e00f5c3fd4b7a
自由な頂点間の負辺除去
こういうタイプの負辺はどう除去するのか
https://gyazo.com/10039fd078d02c20d1146ff98eec2658
多分このままだと無理
jを「選んだときにT」の頂点j'に変える
https://gyazo.com/4cc6a94cbf16b1eeeac29997edad9df8
逆向きに無限大辺がついてる場合はもっと簡単
https://gyazo.com/0e17acaac7437f7a2b7e5cf93268f9a8
「十分に大きな重み」をもっと大きくしても問題がないため
https://gyazo.com/d6313aacf7e7bf0b63ab598d7a99d51e
まだ僕がわかってないこと
「iとjがSなら、kもS」という形のandはできるか？
「iがSなら、jまたはkがS」という形のorはできるか？
n択を表現するのに使ったような方法で中間レイヤーを挟んで解決できないのか？
たとえばN個の対象に二択の選択肢(0/1)が二つ(A, B)あるケースで、「Ai=1かつBi=0ならコストc」「Ai=1かつBi=1ならコストd」「Ai=0ならコストe」というパターン
これを2つの二択だと考えているとandをどう実現するかで悩む
1つの三択として扱えば素直にそれぞれの選択肢でのコストの形になる
おそらく論理式による表現に慣れた我々が問題を見てまず論理式で表現してしまい、それから最小カットに変換しようとするところに問題がある
一般の論理式から最小カットへの変換は存在しないと思う
そうではなく問題を最初から最小カットで表現する必要がある
これは「論理式を考えてからそれをニューラルネットにするのではない」「論理式を考えてからそれをハミルトニアンにするのではない」ににた構図