この記事は何？
- 先日のABC404-G問題において牛ゲーと呼ばれるテクニックを利用した問題が出題されました．正直自身は牛ゲー（特殊な線形計画問題をグラフの最短経路問題として解くテク）がなぜうまくいくのかあまりわかっていなかったので，備忘録も兼ねてまとめておこうと思います．
- この記事では大きく分けて以下の内容に触れていきます
- 双対問題とは何か？
- 牛ゲーと最短経路問題の関係
対象
- 牛ゲーについて調べてみたけど正直よくわからなかったという方
- 最大化問題を解こうとしていたのになんで最短経路問題が現れるのかよくわからないという方
注意
本記事は数学的に頑健でしっかりとした議論というよりは，お気持ちベースでなんとなくわかったつもりになれることを目標に執筆しています．そのため，多少厳密ではない表現を含む場合があります．また，自身も専門家というわけではなく，勉強したての素人です．(明らかな大嘘が書かれていたり誤解を含むような表現がある場合はご指摘いただけると助かります．)
牛ゲーとは
まず初めに牛ゲーとは，「 $n$ 個の変数 $x_1 , \dots , x_n$ について，$x_i-x_j \leq c_k$ という形式をした $m$ 個の制約下で $x_s-x_t$ の値を最大化してください．」という問題を指します．
牛ゲーというネーミングについてはLayout(POJ No.3169)と呼ばれる問題が元ネタになっていて，単一始点最短経路問題の双対問題として有名です🐮．
そもそも双対問題ってなに？
まず，双対とはある二つの概念でお互いに表裏の関係にあるようなものを指します．なんかよくわからないけど立場を入れ替えたらそれっぽく対応してるやつくらいの認識でよいです．
そのなかでも(強)双対問題とは，2つの問題Aと問題Bであって
- Aにある操作をしたらBを作れる．
- 逆にBに同じ操作をしたらAが作れる．
- AとBの答えは同じ
という関係にある問題のことを指します．
具体例として以下の問題について考えてみます．
\displaylines{
max &3x_1+2x_2 \\
\text{s.t.} &x_1+3x_2 \leq 5 \ \ \ \ \cdots (1)\\
&2x_1+x_2 \leq 6 \ \ \ \ \cdots (2)\\
}
要するに下の $(1)$ 〜 $(2)$ を満たすように $x_1$ と $x_2$ を動かして，一番上の式をでかくしてくださいねという問題です．以後ではでかくしたい一番上の式を目的関数と呼びます．
まず，おもむろに $(1)$ と $(2)$ を足し合わせてみます．すると， $3x_1+4x_2 \leq 11$ という式が得られます．目的関数の係数をグッと睨むと「$3x_1+4x_2$ は目的関数よりは大きそう」「目的関数よりちょっと大きそうな値を $11$ までなら大きくできる」「つまり，目的関数は $11$ より大きい値にはならないはずだ」というように上界を見積もることができます．
この考えを応用して，制約式をうまく変形し，目的関数よりちょっと大きそうな関数を作ることで答えの上界を見積もってみます．
まず，新しい変数 $y_1,y_2 \geq 0$ を用意して，$y_1*(1)$ と $y_2*(2)$ を足し合わせてみます (掛け算をするときに不等式がひっくり返らないように $y_1,y_2 \geq 0$ という条件を課しています)．すると，$(y_1+2y_2)x_1 + (3y_1+y_2)x_2 \leq 5y_1+6y_2$ という不等式を作ることができます．この不等式を利用して目的関数のよりよい上界を見積もろうとすると以下のような別の問題が導けます．
\displaylines{
min &5y_1+6y_2 \\
\text{s.t.} &y_1+2y_2 \geq 3 \ \ \ \ \cdots (3)\\
&3y_1+y_2 \geq 2 \ \ \ \ \cdots (4)\\
&y_1 \geq 0 , y_2 \geq 0 \ \ \ \ \cdots (5)
}
まず，目的関数よりちょっと大きいはずの関数が欲しいので，$(3)$ と $(4)$ の式が成り立ちます．そして，よりタイトな上界を求めたいというモチベーションから，不等式の右辺を最小化する問題となっています．
実は，( 2つの問題に解が存在するなら ) 元の最大化問題と変形後の最小化問題の答えは一致することが知られており，元の問題は主問題・変形後の問題は双対問題と呼ばれます．
なお，なぜ一致するのか？という部分についてはこの記事では取り扱わない予定です．メジャーなテーマなので調べてみるとたくさん資料が出てくると思います．
解が存在する条件について
ここまでの説明で例に出してきた問題は目的関数と制約式がすべて1次式で表された形の数理計画問題で，特に線形計画問題と呼ばれます．この節では線形計画問題に解が存在しないパターンを2つ紹介します．
目的関数が非有界な場合
以下のような問題を考えてみましょう．
\displaylines{
max &x_1+2x_2 \\
\text{s.t.} &x_1-3x_2 \leq 5\\
&2x_1-x_2 \leq -1\\
}
この問題では $x_1$ を $1$ 増やした時に，$x_2$ を $2$ 減らしていくと制約式を満たしながら目的関数をいくらでも大きくできることが読み取れます．このように，目的関数をいくらでも大きくできてしまう場合は問題に解が存在しません．
制約を満たす解が存在しない場合
次に，以下のようなパターンを考えてみます．
\displaylines{
max &x_1+2x_2 \\
\text{s.t.} &x_1+3x_2 \leq 5\\
&-x_1-3x_2 \leq -8\\
}
2つ目の制約を-1倍して，1つ目と組み合わせると $8 \leq x_1+3x_2 \leq 5$ という式が得られます．$x_1$ と $x_2$ の値をいくつにしてもこの条件は満たせないので，最大化以前に制約を満たす解がありません．このような場合にも解は存在しません．
では牛ゲーってなんなのか？
今までの内容を踏まえて，改めて牛ゲーの話に戻ります．
牛ゲーとは以下のような形をした線形計画問題の一種でした．
\displaylines{
max &x_t-x_s \\
\text{s.t.} &x_{a_i}-x_{b_i} \leq c_i\ \ (1 \leq i \leq m)\\
}
簡単な例として以下の問題を考えてみます．
\displaylines{
max &x_4-x_1 \\
\text{s.t.} &x_2-x_1 \leq 5\\
&x_3-x_2 \leq -2\\
&x_4-x_3 \leq 4\\
}
さっきの線形計画問題での流れを踏まえ，本問題の制約式をすべて足し合わせると，$x_4-x_1 \leq 7$ という式が得られ，結構自明にこの値が最大値となることがわかると思います．(実際，$x_4$ と $x_1$ を $7$ より大きく引き離そうとしたら制約式のどれかを満たすことが難しくなり，$x_1 = 0$ とおいて各制約を満たすように $x_i$ の値を決めると，$x_4-x_1 \leq 7$ を満たす $x_1 , \dots ,x_4$ を構築できることが手計算でも確認できるはずです．)
ところで，この $x_s-x_u \leq c_1$ と $x_u-x_t \leq c_2$ という式を足し合わせて，$x_s-x_t\leq c_1+c_2$ を導くプロセスが以下のようなグラフの $s$-$t$ パスっぽく見えてきませんか？？
気持ちとしては制約同士を足すという動作と制約を辺に見立てたときのパスって似てるよね〜くらいのお気持ちです．牛ゲーに出てくる「2変数の差型をした制約」は辺に見立てる部分へ効いてくるわけです．
すると先ほど例に出した問題は以下のようなグラフっぽく見えてくるはずです．
つぎに，先ほどの問題に一本制約式を増やした以下の問題を考えてみます．
\displaylines{
max &x_4-x_1 \\
\text{s.t.} &x_2-x_1 \leq 5\\
&x_3-x_2 \leq -2\\
&x_4-x_3 \leq 4\\
&x_3-x_1 \leq 2\\
}
この場合も1,2,3本目の制約式から $x_4-x_1 = 7$ が達成できる...と思いきや今度はうまくいきません．なぜなら，先ほどのように $x_1, \cdots ,x_4$ を配置すると，4番目の制約式を達成できなくなるからです．これをグラフの上で表現すると，以下の図で重み $3$ のパス $1 \rightarrow 2 \rightarrow 3$ を採用すると，よりきつい制約である重み $2$ のパス $1 \rightarrow 3$ が満たせなくなるからというふうに理解できます．
以上を総括すると，最大化問題を考えてたのになんで最短経路問題が生えてくるのだ！？という問いは，「制約をグラフの辺に見立てることができて，さらに制約同士の足し算がグラフ上のパスに見立てることができる」「その中でも一番タイトな制約式を通る $s$ から $t$ へのパス重みが(双対問題を考えると)最大化したい目的関数の良い上界になる」「一番タイトな制約式を通るとは，そのまま $s$ から $t$ への最短経路に対応する」という３点で説明できると思います．
牛ゲーに解が存在する条件について
線形計画問題の場合と同様に，牛ゲーにも解の存在しないパターンが2パターンあります．
目的関数が非有界な場合
以下の問題を考えてみます．
\displaylines{
max &x_4-x_1 \\
\text{s.t.} &x_2-x_1 \leq 5\\
&x_4-x_3 \leq 4\\
}
この場合は $x_1,x_2$ の塊と $x_3,x_4$ の塊に制約がついていないため，$x_4-x_1$ の値をいくらでも大きくできます．これはグラフ上で考えると以下のようになっていて，実は解が非有界となる条件は $s$ から $t$ へのパスが存在しないこととなっています．
制約を満たす解が存在しない場合
次に，以下のようなパターンを考えてみます．
\displaylines{
max &x_4-x_1 \\
\text{s.t.} &x_2-x_1 \leq 4\\
&x_3-x_2 \leq -2\\
&x_4-x_3 \leq 4\\
&x_1-x_3 \leq -3\\
}
1,2本目の制約式を足し合わせると $x_3-x_1 \leq 2$ となり，4本目の制約式を$−1$倍したものと合わせると，$3\leq x_3-x_1\leq2$ という式が得られます．$x_1$ と $x_3$ の値をいくつにしてもこの条件は満たせないので，解は存在しません．これはグラフ上で考えると以下のようになっていて，解が存在しない条件はグラフが負の閉路をもつことになります．
まとめ・反省
特殊な線形計画問題がグラフの最短経路問題に帰着できることのお気持ちをざっくり説明しました．
負辺や負閉路を持つ場合があるので最短経路はベルマンフォード法を使いましょう．
中途半端に線形計画法の話にも触れたので牛ゲーの部分もうちょいしっかり説明すればよかった〜
参考文献