Aliens DP で辺の本数が区間で指定される場合

概要

Monge グラフ上の $d$-辺最短路長を計算するアルゴリズム | Kyopro Encyclopedia of Algorithms

この記事においてラグランジュ双対などで説明した部分を凸共役の観点から解釈し、「 $a$ 本以上 $b$ 本以下使う最短路」も同じように解くことができることを解説します。

本文

合成積

関数 $f _ 1, f _ 2: \mathbb{R} \to \mathbb{R} \lbrace + \infty \rbrace$ の合成積 $f _ 1 \square f _ 2$ は \begin{align} (f _ 1 \square f _ 2)(x) &= \inf _ {x _ 1 + x _ 2 = x} (f _ 1(x _ 1) + f _ 2(x _ 2)) \end{align} で定義されます。 $f _ 1, f _ 2$ が凸で $f _ 1 \square f _ 2$ が $- \infty$ にならなければ、 $f _ 1 \square f _ 2$ は凸です。

凸共役関数

関数 $f: \mathbb{R} \to \mathbb{R} \cup \lbrace + \infty \rbrace, ~ ~ \exists x. ~ f(x) \neq + \infty$ に対して、その凸共役関数 $f ^\bullet: \mathbb{R} \mapsto \mathbb{R} \cup \lbrace +\infty \rbrace$ を \begin{align} f ^\bullet (p) &= \sup _ x (px - f(x)) \end{align} で定義します。本記事では $\displaystyle f ^ \bullet (p) = - \min _ x (f(x) - px)$ と思っても差し支えありません。凸共役関数は本来もっと広いクラスの関数に対して定義されますが、本記事ではこれで十分です。

凸共役関数に対していくつかの良い性質が成り立ちます。

$f ^ \bullet$ は凸関数
$f$ が凸で特定の条件を満たすと $f ^ {\bullet \bullet} = f$
$f _ 1, f _ 2$ が凸で特定の条件を満たすと $(f _ 1 \square f _ 2) ^ \bullet = f _ 1 ^ \bullet + f _ 2 ^ \bullet$

これらの条件は少し複雑なので、本記事では特に確認せずに使用します。 [1] などを確認してください。

問題の整理

$f(x)$ を、辺を $x$ 本使うという条件下での最短距離と定義します。すると、

$f$ は凸
任意の $p$ に対し、 $\displaystyle \min _ x (f(x) - px) = - f ^ \bullet (p)$ が高速に評価できる
$f(d)$ を求めよ

という問題であると整理できます。

$f(d)$ の求め方

\begin{align} f(d) &= f ^ {\bullet \bullet} (d) \cr &= - \min _ {p} (f ^ \bullet (p) - dp) \cr \end{align}

$f ^ \bullet$ は凸なので $p \mapsto f ^ \bullet (p) - dp$ も凸であり、その最小化は三分探索で行えます。 $f ^ \bullet (p)$ が高速に評価できるので、目的が達成されました。

$\displaystyle \min _ {a \leq x \leq b} f(x)$ の求め方

$\delta _ {\lbrack a , b \rbrack}: \mathbb{R} \to \mathbb{R} \cup \lbrace +\infty \rbrace$ を \begin{align} \delta _ {\lbrack a , b \rbrack} (x) &= \begin{cases} 0 & \quad (a \leq x \leq b) \cr +\infty & \quad (\text{otherwise}) \end{cases} \end{align} で定義します。このとき \begin{align} \min _ {a \leq x \leq b} f(x) &= (f \square \delta _ {\lbrack -b , -a \rbrack}) (0) \cr &= (f \square \delta _ {\lbrack -b , -a \rbrack}) ^ {\bullet \bullet} (0) \cr &= - \min _ {p} ((f \square \delta _ {\lbrack -b , -a \rbrack}) ^ \bullet (p) - 0p) \cr &= - \min _ {p} (f ^ \bullet + {\delta _ {\lbrack -b , -a \rbrack}} ^ \bullet) (p) \end{align} $f ^ \bullet, \delta _ {\lbrack -b , -a \rbrack} ^ \bullet$ は凸関数なのでその和も凸であり、その最小化は三分探索で行えます。 ${\delta _ {\lbrack -b , -a \rbrack}} ^ \bullet$ は非常に単純な形になるので高速に評価でき、目的が達成されます。実際、 \begin{align} {\delta _ {\lbrack -b , -a \rbrack}} ^ \bullet (p) &= \begin{cases} -bp &\quad (p \leq 0) \cr -ap &\quad (p \geq 0) \end{cases} \end{align} です。