はじめに

こんにちは，株式会社Acompanyインターン生の堀内です。
普段は名古屋大学で修士の学生をしています。研究とインターンシップの2足のわらじで頑張っています。

本記事はOPTIMIND x Acompany Advent Calendar 2021の10日目の記事となります。

本記事の内容

今回は，タイトルにも書いてある通り，巷で話題（？）の牛ゲーを扱います。

具体的には以下の内容をお送りいたします。

牛ゲーとは
牛ゲーと最短経路問題の関係
牛ゲーの解が存在しない時

この記事を読めば，牛ゲーがなぜ最短経路問題に帰着するのかをふんわりと理解できるようになります。

とはいえ，牛ゲーの解説というよりは，最短経路問題を線形計画問題にするということに主眼を置いています。

対象者

本記事は「牛ゲーを履修したいがそもそも何かわからん」という人や「最短経路問題が線形計画問題にできるだと！？」という人を対象としています。この記事を読み終えることには，牛ゲーを見つけ次第，最短経路問題で解くことができるようになるでしょう。

注意

私の線形計画問題に関する知識は，大学の授業で一タームの期間触れた程度しかありません。もしかしたら頓珍漢なことを書いているかもしれませんが，ご了承ください。

牛ゲーとは

まず牛ゲーの説明をします。

牛ゲーは，$N$ 個の変数 $d_i$，$M$個の差分制約式 $d_j−d_i \leq c_k$ の元で，2つの変数からなる式 $d_t−d_s$を最大化する線形計画問題を指します。

問題文をそのまま言うようですが，数直線上に点を置いたとき，各点同士に何らかの距離制限があるとした場合の点の位置の話です。
単に$d_t-d_s$を求めるだけでなく，sを固定して，すべての点$i$に対して$d_i-d_s$の値を最大化したときの値を出すこともあります。

名前の由来はLayout (POJ No.3169)の問題で扱われている牛さん（🐄<モーモー）から持ってこられているようです。

この線形計画問題の特徴は差分制約式が2変数で表されているところです。
蟻本の受け売りにもなりますが，線形計画問題なので単体法で解くこともできます。
しかし，この2変数間の差分制約式のみで成り立つ制約の場合，特殊な条件を除けばすべて単純な最短経路問題に帰着します。

牛ゲーと最短経路問題の関係

なぜ，牛ゲーが最短経路問題に帰着するのかを考えましょう。

最短経路問題の線形計画問題の説明

まず最短経路問題を線形計画問題にした時の話をします。

以下蟻本からの抜粋になります，

任意の2点 $i$ ，$j$ で $i$ → $j$ への(有向) 辺がある時、$ d_j \leq d_i+c(i,j) $ (d は始点s からの各頂点の最短距離) が成り立ちます。これらの制約をすべて満たす$d$ における $d_i$ の最大値が $s$ と頂点 $i$ 最短距離です

不等式制約である，$ d_j \leq d_i+c(i,j) $を見ると $ d_j - d_i \leq c(i,j) $ の形をしていることが分かります。これは牛ゲーとまるっきり同じ形をしています。
つまり線形計画問題が一致しています。これで最短経路問題=牛ゲーであることがわかりました。
あとは，牛ゲーの差分方程式をもとに$i$ → $j$ にコスト $c(i,j)$ の辺を張ったグラフ$G$を作成してこれの最短経路問題を解けばいいわけですね。
終わりです。ありがとうございました。

問題点

で，理解できたらうれしいですが，少なくとも私には理解できませんでした。
具体的には，最短経路は小さいものを求めているのになぜ$d_i$が最大値！？という考えになりました。
結論から言ってしまえば，最短経路の理解を深めると，この理解につながります。

最短経路で求めたものがなぜ最大値なのかの説明

最短経路問題をもう少し深掘ります。

グラフ$G=(V, E, C)$に対して，$s,i \in V$で$d_i$を「頂点sから頂点iへの最短経路の長さ」とします。また，辺$(i→j) \in E$ の長さ（重み）を$c(i,j) \in C$とします。

このとき，任意の頂点jに対して$$d_j = min\{ (i→j) \in E; d_i+c(i,j) \} $$ が成り立っています。

これはダイクストラ法の気持ちを考えるとわかりますが，$s$ から頂点 $j$ への最短経路のうち，$j$ の一歩手前で到達する頂点を $i$ とするならば，$d_j$ は必ず $d_j = d_i + c(i,j)$ を満たしているというわけです。

さて，$d_j = min \{ (i→j) \in E; d_i+c(i,j) \} $ は何を意味しているのでしょうか？
$d_j$が満たすべき各制約 $ d_j - d_i \leq c(i,j) $ は$d_j$の値のうち取ることのできる上界（言葉の使い方違うかも）をそれぞれで与えていることになります。
直感的に言えば，**$d_j$に対する上界を組み合わせた時，上界のうち一番強い上界になる最小値を$d_j$としていることに他なりません。**その値よりも小さければ$d_j$に対するすべての制約を満たしていることになります。これは結局 $d_j$ の最大値です。

よって，最短経路問題を解くことは，$d_i$ が各制約を満たす中でとることのできる最大値を求めることになっていることが分かりました。

牛ゲーの解が存在しない時

最短経路で牛ゲーが解けるときが分かりましたが，逆に最短経路が存在しないとき，つまりグラフ$G$に負閉路が存在しているとき，どうなるのでしょうか？（連結なグラフってことでお願いします。）
結論から言えばこのとき，不等式制約を満たす解は存在しません。
なので，グラフを構築して負閉路があれば即解なしを出力してしまえばいいわけです。

負閉路があると解が存在しない理由の説明

グラフ $G$ に負閉路がある時，閉路 $i_0→i_1→⋯i_k→i_0$ の距離合計を $c<0$ だとします。
もし，解が存在しているならば，閉路上の各点に対して $d_{i_{j+1}} - d_{i_j} \leq c(i_j,i_{j+1})$ が成り立っていることになります（$j=k$の時は$j+1$が$0$）（辺があるところには不等式制約があるのでね）。
ここで成り立っている不等式を足し合わせます。
すると
$$ 0 = d_{i_1} - d_{i_0} + d_{i_2} - d_{i_1} + d_{i_3} … + d_{i_k} - d_{i_{k-1}} + d_{i_0} - d_{i_k} \leq c(i_0,i_1) + c(i_1, i_2) + ・・・ + c(i_k, i_0) = c $$ が成り立つことになります。
しかしこれは $ c < 0$ に矛盾します。
つまり解が存在していると仮定したことが間違っていることになるので，解は存在しない方が正しかったわけです。

おわりに

本記事では牛ゲーが最短経路問題になる理由を説明しました。
最短経路問題の制約をしっかり数式化することで，牛ゲーの線形計画問題と一致することがわかりました。

厳密証明するならばもう少ししっかり同値性を示す必要がありますが，ふんわりとこんな感じなんだなと理解してもらえると嬉しいです。

謝辞

本記事を作成するにあたって，大学の後輩君にアイディアをもらいました。ありがとうございました。

参考

牛ゲーが何故グラフの最短経路に帰着できるのか
 最短路長で解ける線形計画問題 (牛ゲー)
牛ゲー(最短経路問題の双対問題が線形計画問題)

グラフに負辺があるとき
ポテンシャル法入門 (1) 〜ポテンシャルとダイクストラ法
 ダイクストラとポテンシャルのはなし