牛ゲーが最短経路問題で解けることの説明

牛ゲーが最短経路問題で解けることの説明

本記事では、牛ゲーが最短経路問題に帰着できることを説明したいと思います。
「こうすれば解けるのはわかったけど、なんで？」という人向けの説明になっています。
数理最適化の言葉を使って記述します。

対象読者

• 数理最適化についての基礎を知っている人
  • 使う定理のステートメントは記載します
• 牛ゲーという言葉は知っている人
• 蟻本の牛ゲーの説明がピンとこなかった人

準備

牛ゲーとは

牛ゲーという言葉はPOJ 3169 - Layoutという問題が起源となっているようです。
問題文から数理的な構造だけを取り出すと以下のようになります。説明のため元の問題から記号を置き換えている部分があります。

数直線上に $N$ 個の点 $d_i \ (i = 1, \ldots, N)$ を順番に配置することを考えます。
このとき以下の制約を満たす必要があります。

• $d_i \leq d_{i+1} \ (i = 1, \ldots, N-1)$
• 三つ組 $(u,v,c)$ (但し $u < v$ )で表現される以下の $M$ 個の制約を満たす。
  • $d_v - d_u \leq c$
• 三つ組 $(u,v,c)$ (但し $u < v$ )で表現される以下の $L$ 個の制約を満たす。
  • $d_v - d_u \geq c$

以上のもと、$d_N - d_1$ を最大値を出力してください。
そのような配置が存在しない場合は $-1$ 、いくらでも大きくできる場合は $-2$ を出力してください。

ここでは、この問題を定式化すると現れる線形計画問題のことを牛ゲーと呼称することとします。

定式化

上で与えられた制約を少し整理します。
$(u,v,c)$で与えられる二つの制約は、$u,v$の大小関係の制約を外し、$c$の符号を適切に付け替えることで全て $d_v - d_u \leq c$ と表現できます。
また、$d_i \leq d_{i+1}$ も $d_{i+1} - d_{i} \leq 0$ と書けば $(i,i+1,0)$ という制約が与えられたと解釈できます。

以上のことから、牛ゲーの制約式は $N + M + L$ 個の以下のような形式によって表現されることが分かります。

• $d_{v_i} - d_{u_i} \leq c_i \ \ (i = 1, \ldots, N+M+L)$

ここまでの議論を元に、線形計画問題の形で牛ゲーを表現します。
そのために、改めて$M := N + M + L$と置きなおします。更にいくつか文字を定義します。

• ${\bf d} := (d_1, d_2, \ldots, d_{N-1}, d_N)^{\mathrm{T}} \in \mathbb{R}^N$
• ${\bf b} := (-1, 0, \ldots, 0, 1)^{\mathrm{T}} \in \mathbb{R}^N$
• ${\bf c} := (c_1, c_2, \ldots, c_M)^{\mathrm{T}} \in \mathbb{R}^M$

但し、$c_i$ とは $d_{v_i} - d_{u_i} \leq c_i$ の形になるように置きなおした後の$c_i$のことです。
最後に行列 ${\bf A} \in \mathbb{R}^{M \times N}$ を以下のように定義します。

$$a_{ij} = \begin{cases} 1 & (v_i = j) \\ -1 & (u_i = j) \\ 0 & (\mathrm{otherwise}) \\ \end{cases}$$

これらを使うことで、牛ゲーは以下のように表現されます。変数は $\bf d$ です。

$$\begin{equation*} \begin{aligned} & \text{maximize} & { \bf b}^{\mathrm{T}} { \bf d } \\ & \text{subject to} & \bf{ Ad } \leq \bf{c} \\ \end{aligned} \end{equation*}$$

牛ゲーの双対問題

上で作った問題は線形計画問題と呼ばれる問題です。線形計画問題には自身に対応する双対問題と呼ばれる問題が必ず存在します。これは数理最適化において重要な概念です。ここでは必要以上に深くは触れませんが、気になる方は調べてみてください。
ちなみにそのような双対問題に対して、元となる問題のことを主問題と呼びます。

というわけで、先ほど作った問題の双対問題を作ろうと思います。主問題が与えられれば双対問題は機械的に導出できます。具体的にはこのPDFが参考になります。
以下がその問題です。今度の変数は ${\bf e } \in \mathbb{R}^M$ になっています。

$$\begin{equation*} \begin{aligned} & \text{minimize} & { \bf c}^{\mathrm{T}} { \bf e } \\ & \text{subject to} & \bf{ A }^{\mathrm{T}} { \bf e } = \bf{b} \\ & & \bf{e} \geq \bf{0} \end{aligned} \end{equation*}$$

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

双対問題の意味づけ

準備の項では牛ゲーを線形計画問題として記述し、その双対問題を導きました。

実は、この双対問題こそが最短経路問題になっているのです。具体的には以下のような問題設定の最短経路問題になっています。

$N$頂点$M$辺の有向グラフが与えられる。各頂点は$1, 2, \ldots, N-1, N$と番号づけられている。各辺は$u_i$から$v_i$に向かって伸びており、コストは$c_i$である。
頂点$1$から頂点$N$までの最小コストはいくつか？

これだけ言われても「本当？」という気持ちがぬぐえないと思うので、ここからは数式と照らし合わせて見ていきましょう。

まず目的関数を見ます。${ \bf c}^{\mathrm{T}} { \bf e }$ とありますね。$\bf e$ は各辺を使った回数を記録していると思ってください。$e_3 = 1$ なら、$3$ 番目の制約の辺を $1$ 回使ったということです。
$\bf c$は上で定義したもので、元をたどれば $d_{v_i} - d_{u_i} \leq c_i$ から得られたものです。$d_i$ を $d_0$ からの距離だと思うとコストを表しているように見えますよね。
そして最小化すべきは $\bf c$ と $\bf e$ の内積です。これは使ったコストの総和を表現しています。

---

2021-12-29追記

上の議論では ${\bf e}$ が整数しかとらない保障はしていませんが、実際には解が存在するなら整数ベクトルの最適解が存在しています。
具体的にはこのPDFで挙げられている定理 $3$ がその保障になります。

正確な記述はPDFを見てほしいのですが、ざっくりとしたステートメントは 線形計画問題の係数行列が完全単模行列で、定数項ベクトルが整数ならば、整数ベクトルによる最適解が存在する、というものです。
完全単模行列とは任意の小行列式の値が $1$ もしくは $-1$ となる行列のことです。

今回の問題に合わせると $\bf{ A }^{\mathrm{T}}$ が完全単模行列であり、 $\bf{b}$ が整数ベクトルであるため、 整数最適解が存在します。

追記ここまで。noshi91さんにご指摘いただきました。ありがとうございました。

---

次に制約を見ていきます。 $\bf{ A }^{\mathrm{T}} { \bf e } = \bf{b}$ についてです。
これは $N$ 個の等式制約をまとめて表現したものです。 $i$ 行目に着目してみましょう。
$\bf{ A }^{\mathrm{T}}$ の第 $i$ 行目は、定義より 頂点 $i$ についての情報を表しています。$i$ が $j$ 番目の制約式に $v_i = i$ として現れるなら $a_{ji} = 1$ が、$u_i = i$ として現れるなら $a_{ji} = -1$が入っています。接続行列の正負が逆のもの、というと分かりやすいかもしれません。

それと $\bf e$ の内積が表すものは何かというと、$\bf e$ の表現する経路における各頂点の(入次数 - 出次数)です。$i$ 番目の辺を使ったのならば $u_i$ から出て $v_i$ に入ったはずなので、頂点 $u_i$ における出次数は $1$ 増え、$v_i$に置ける入次数も $1$ 増えます。 $\bf A$ によってこのことがうまく表現されているわけですね。

最後に右辺側の $\bf b$ ですが、これは第 $1$ 成分が $-1$、第 $N$ 成分が $1$、それ以外が $0$ のベクトルでした。左辺の $i$ 行目は頂点 $i$ の入次数と出次数の差であることを踏まえると、これはつまり、頂点 $1$ では出次数が入次数よりちょうど $1$ 多くて、頂点 $N$ では入次数が出次数よりちょうど $1$ 大きいことを示しています。

それが制約として課されているため、$\bf e$ が表現できる経路というのは頂点 $1$ から出て頂点 $N$ に到達するようなパスを含んでいます。

---

2021-12-29追記

$1$ から出て $N$ に到達するような経路に加え、全く関係のない閉路を含んでいるようなものも $\bf e$ の制約を満たします。
そのため厳密にはこれは最短経路問題にはなっていませんが、実用上は最短経路問題と考えてよいです。以下でそのことについて説明します。

後述しますが、この問題の最適値が必要になるケースでは負閉路が存在しないと仮定してよいです。（負閉路を持つ場合は牛ゲーの解は存在しません）

実行可能解は必ず $1$ から出て $N$ に到達するような経路を含んでいます。このパスを取り除くと閉路しか残りませんが、負閉路を持たないことからこの閉路のコストの和は必ず $0$ 以上であり、取り除いても損をしません。従って、閉路を含まないようなパスによって最適解を構築できます。

以上のことから、牛ゲーの文脈でこの問題を最短経路問題だと考えても問題ないことが分かります。

追記ここまで。noshi91さんにご指摘いただきました。ありがとうございました。

---

${\bf e} \geq {\bf 0}$ は、辺の向きを逆にたどることはできないことに対応しています。

以上のことをまとめると、上の双対問題が最短経路問題であることがわかっていただけると思います。

なぜ牛ゲーが最短経路問題に帰着できるのか

この項ではなぜ牛ゲーが最短経路問題に帰着されるのか、ということについて述べていきます。

帰着できるのを示すために双対定理という強い定理を使います。
これは、主問題が最適解を持つならば双対問題も最適解を持ち、その最適値は等しいという強力な定理です。
つまり牛ゲーの双対問題が最短経路問題であることから、最短経路問題の最適値が牛ゲーの最適値にもなります。

双対定理の結果は主問題が最適解を持たなければ使えません。そのため、最適解を持たない場合については別個考える必要があります。
数理最適化において最適解を持たない場合というのは二つあります。一つは実行不可能な場合で、解となるような要素が一個もない場合です。もう一つは最適値が非有界な場合で、いくらでも解を大きく(最小化問題の場合は小さく)できる場合です。

最短経路問題が非有界の場合

主問題が非有界ならば双対問題は実行不可能である、という定理があります。双対問題の双対問題は主問題なので、双対問題が非有界ならば主問題は実行不可能であることも言えます。
最短経路問題の解が無限に大きくなる場合は負閉路がある場合です。このとき牛ゲーの解は存在せず、実行不可能になります。

最短経路問題が実行不可能な場合

最短経路問題が実行不可能である場合、つまり頂点$N$にたどり着けない場合、牛ゲーは非有界、もしくは実行不可能になります。
最適解を持つことはありえません。これは双対定理から言えます。

少し考えてみたのですが、この二つを最短経路問題だけを考えて識別するのは無理な気がします。
実際に牛ゲー側の問題で一つ解を構築できれば実行不可能ではないことが分かり、識別ができます。

2021-12-29追記

noshi91さんに教えていただきました。

https://twitter.com/noshi91/status/1475817929463984134

主問題の目的関数を置き換えることで双対問題の制約を少し変更し、主問題の実行不可能性を導いています。
こちらでもう少し詳しく説明します。${\bf b } = {\bf 0}$ とおいて目的関数を変更した主問題を $P'$ とし、そのときの双対問題を $D'$ とします。
$D'$ が ${\bf e} = {\bf 0}$ で実行可能なのは明らかです。$D'$ の他の解はいくつかのサイクルで構成されたもののみです。このため、 $D'$ が有界かどうかは負閉路があるかないかのみに依存します。

もし負閉路を含めば $D'$ は非有界となるので $P'$ の実行不可能性が言えます。
実行可能性は制約にのみ依存し、$P'$ と元の主問題の制約は一致するため、もとの主問題も実行不可能です。

また、 $D'$ が負閉路を持つならば、グラフの形が変化しないことから元の双対問題も負閉路を持ちます。当然これは逆も成立しています。
これによって 最短経路問題におけるグラフが負閉路を持つならば元の主問題が実行不可能であることがわかりました。

以上のことを踏まえると、最短経路問題が実行不可能な場合の牛ゲーの状態は以下のようになります。

• 負閉路を持つならば実行不可能
• 持たなければ非有界

まとめ

https://twitter.com/noshi91/status/1475818895395401728

noshi91さんのこのツイートの通りです。
上のツイートが消えたときのためにも簡単にまとめておくと、以下のようなことが言えます。逆も成立しています。

• 双対問題におけるグラフが負閉路を持てば主問題は実行不可能
• 双対問題におけるグラフが負閉路を持たず、1-Nパスが存在しなければ主問題は非有界
• 双対問題におけるグラフが負閉路を持たず、1-Nパスが存在すれば主問題も最適解を持つ

(おまけ)最短経路問題の言葉で牛ゲーを説明する

さて、牛ゲーが解けることはわかりました。ただ、双対定理という超強力な道具でぶん殴っただけなのでどうも気持ち悪いですね。牛ゲーは最短経路問題の双対問題なわけですから、牛ゲーの条件式も最短経路問題において意味を持つ形になっているはずです。

元の問題は"到達可能な時間の最小化"でした。これの双対ということなので、直感的には"到達不可能な時間の最大化"を表していると思えます。例えば最短経路のコストが $10$ のときに、どう頑張っても $9$ では到達できないですよね。このような到達できない時間のうちで最も大きい値はいくつか、と尋ねているのが牛ゲーです。これなら最大化することで最短経路問題に帰着するというのも自然です。

まとめ

久々に（Zennでは初めて）記事を書きました。数学をバリバリ使ったのも久しぶりなので、何か変なところ等があればご指摘ください。
お読みいただきありがとうございました。

参考文献

• 双対問題と双対定理
• 整数計画と LP の整数性