noshi91のメモ

データ構造のある風景

最小カット問題の k 値への一般化

アルゴリズム

概要

最小カットを用いると、 \alpha \in \mathbb{R},\ \theta _ i : \lbrace 0, 1 \rbrace \to \mathbb{R} 及び劣モジュラな \phi _ {i, j} : \lbrace 0, 1 \rbrace ^ 2 \to \mathbb{R} について

\begin{align} \text{Minimize}&\quad \alpha + \sum _ i \theta _ i (x _ i) + \sum _ {i \lt j} \phi _ {i, j}(x _ i, x _ j) \cr \text{subject to}&\quad x \in \lbrace 0, 1 \rbrace ^ n \end{align}

という問題が解けます。[2]

これを一般化して、 \alpha \in \mathbb{R},\ \theta _ i : k \to \mathbb{R} 及び Monge な \phi _ {i, j} : k ^ 2 \to \mathbb{R} について

\begin{align} \text{Minimize}&\quad \alpha + \sum _ i \theta _ i (x _ i) + \sum _ {i \lt j} \phi _ {i, j}(x _ i, x _ j) \cr \text{subject to}&\quad x \in k ^ n \end{align}

は最小カットを用いて解けます。

本記事は [1] の内容を定式化し、表現可能な条件を明示的に記述します。

グラフの作り方

各変数 x _ i に対して、 \lbrace 0, 1 \rbrace の値を取る k - 1 個の変数 \lbrace x _ i ^ d \rbrace _ {d = 1} ^ {k - 1} を作ります。 さらに、 x _ i ^ d = 1 \land x _ i ^ {d + 1} = 0 の場合 + \infty のコストが掛かることにします。 これにより \lbrace x _ i ^ d \rbrace _ {d = 1} ^ {k - 1} は丁度 k 種類の状態を取るようになり、 x _ i ^ d = 1 \leftrightarrow x _ i \lt d と対応させられます。

\theta _ i : k \to \mathbb{R} が表現可能なことを示します。 x _ i ^ d に対する 1 変数関数は常に表現可能であったことを思い出し、 x _ i ^ d = 1 のとき \theta _ i (d - 1) - \theta _ i (d) のコストを掛けます。 さらに無条件で \theta _ i (k - 1) のコストを掛けると、 \theta _ i が表現されます。

下図は上述の方法で表現した後、さらにグラフでの表現に直したものです。

f:id:noshi91:20210629043614j:plain

\phi _ {i, j} : k ^ 2 \to \mathbb{R} が Monge ならば表現可能なことを示します。 \alpha と \theta _ i, \theta _ j を使うことで、 \phi _ {i, j} (0, d) = \phi _ {i, j} (d, 0) = 0 \ (\forall \ d) としてよいです。 x _ i ^ d = x _ j ^ e = 0 のとき \phi _ {i, j} (d, e) - \phi _ {i, j} (d, e - 1) - \phi _ {i, j} (d - 1, e) + \phi _ {i, j} (d - 1, e - 1) のコストを掛けます。 \phi _ {i, j} の Monge 性から、このコストは劣モジュラです。

yukicoder No.119 旅行ツアーの問題

この節は [3] の内容を前節の内容を通して捉え直します。

各国 i について 0: 国に行かない, 1: 国には行くがツアーに行かない, 2: ツアーに行く, の 3 つの選択肢を選ぶ問題であり、 k = 3 とした場合の前節の問題の枠組みで解釈できます。 B _ i, C _ i に関係する部分は 1 変数関数になるため、常に表現可能です ( B _ i, C _ i が負であっても)。 2 変数が関係する部分は、「国 i のツアーに行き国 j に行くならば、国 j のツアーに行かなければならない」です。 これを図示すると以下のようなコストになります。

f:id:noshi91:20210629043658j:plain

このままでは Monge でないので、 0, 1, 2 を 1, 0, 2 の順に並び替えます。すると以下のようになります。

f:id:noshi91:20210629043940j:plain

これは Monge なので、最小カットで解くことができます。 k = 2 の場合 0, 1 を全ての変数で一斉に入れ替えても劣モジュラ性は変化しませんでしたが、 k \geq 3 の場合は Monge 性に影響を与えるということになります。

問題例

出題場所 コンテスト名 問題名
0
KUPC
KUPC2019
123パズル
1
ARC
ARC 107
Sum of Abs

その他

  • グラフの作り方から明らかなように、 k の値は変数ごとに異なっても構いません。

参考文献