動的計画法高速化テクニック（オフライン・オンライン変換）

以下の問題を考えます．

１次元の直線上に地点 $x[0] < x[1] < \cdots < x[n-1]$ がある．我々は車を用いて地点 $x[0]$ から地点 $x[n-1]$ まで移動したい．途中の地点で休憩することができるが，頻繁な休憩も過剰な運転も避けたいので，休憩を挟まずに移動する距離がおよそ $a$ 程度になるようにしたい．具体的には休憩を挟まずに距離 $b$ だけ移動したとき，ペナルティとして $(b - a)^2$ がかかるとし，全体のペナルティが最小になるように移動したい．どのようにすればよいか．

この問題は以下の動的計画法 (Dynamic Programming; DP) で $O(n^2)$ 時間で解けます．

$$ D(j) = \min \{ D(i) + (x[j] - x[i] - a)^2 : i \in [0,j) \}, \ \ (j \in [0,n)) $$

ところが，この問題に対しては，より効率的な $o(n^2)$ 時間アルゴリズムが複数知られています．本稿ではこのタイプのDPを高速化する比較的適用範囲の広いテクニック [1] を紹介します．

オフラインDP / オンラインDP

DPの漸化式を

$$
D(j) = \min \{ F(i,j) : i \in [0, j) \}, \ \ (j \in [0,n))
$$

とします．$F(i,j)$ が $D(i)$ に依存するときオンラインDP，依存しないときオフラインDPといいます¹．オフラインDPでは $D(j)$ はどの順番に計算してもよいので，様々な高速化テクニックが利用できます．

オフラインDPの例：区間を k 分割する DP

最も典型的なオフラインDPは2次元のDP

$$ D(k,j) = \min \{ D(k-1,i) + w(i,j) : i \in [0,j) \} $$

です．$D(k-1,*)$ がすべて計算されていれば右辺の値はすべて事前に得られるので，$k = 1,
2, \ldots$ を順番にオフラインDPとして解いていくことになります．冒頭に述べた問題で，休憩回数 $k$ が入力として指定されている場合はこのクラスに該当します．

オフラインDPに対する代表的な高速化法は単調最小値DP (aka. 分割統治DP) です．上の式の右辺の min を達成する $i$ が「$j$ を大きくすると $i$ も大きくなる」という性質を満たすとき，全体を $O(n \log n)$ で計算できます．

オンラインDPの例：区間を任意個に分割する DP

上の問題で $k$ の制約を外した問題

$$ D(j) = \min \{ D(i) + w(i,j) : i \in [0,j) \} $$

がオンラインDPの典型的な例です．冒頭に述べた問題はこのクラスに該当します．

オフライン・オンライン変換

オフライン問題に対して $O(M(n))$ 時間アルゴリズムが存在するとき，オンライン問題に対する $O(M(n) \log n)$ 時間アルゴリズムを構築できます．これを本稿ではオフライン・オンライン変換と呼ぶことにします．

計算範囲をパラメタにしたDP

$$ E(j) = \min \{ F(i,j) : i \in [l,r) \}, \ \ (j \in [l,r)) $$

を考えます．ただし $F(i,j) = \infty$ for $i \ge j$ とします．これをすべて計算する関数 $\texttt{solve}(l,r)$ を設計しましょう．$\texttt{solve}(0,n)$ を呼べば，本来欲しかった値がすべて計算されます．

$m = \lfloor (l+r)/2 \rfloor $ とおき，$\texttt{solve}(l,m)$ を呼ぶことで，$j \in [l,m)$ について $E(j)$ をすべて計算しておきます．この状態で $j \in [m,r)$ について $E(j)$ を計算する方法を考えます．

漸化式を $m$ で分割して

$$
\begin{align}
E(j) &= \min \{ E'(j), \min \{ F(i,j) : i \in [m,r) \} \}, \ \ (j \in [m,r)) \\
E'(j) &= \min \{ F(i,j) : i \in [l,m) \}, \ \ (j \in [m,r))
\end{align}
$$

とします．このとき，$E'(j)$ の計算範囲とmin範囲が交わらないことから，$E'(j)$ はオフラインDPになります．これを効率的なオフラインDPアルゴリズムを用いて計算します．その後 $E(j)$ を計算するためには $\texttt{solve}(m,r)$ を再帰的に呼べば OK です．

計算量は

$$ T(n) \le 2 T(n/2) + M(n) $$

を解いて $T(n) = O(M(n) \log n)$ となります．

実際の実装では，全体を計算する $\texttt{solve}(l,r)$，オフラインDPを計算する $\texttt{induce}(l,m,r)$ をそれぞれ

$$ \begin{align}
\texttt{solve}(l,r): \quad & E(j) \leftarrow \min \{ F(i,j) : i \in [l,r) \}, \ \ (j \in [l,r)) \\
\texttt{induce}(l,m,r): \quad & E(j) \leftarrow \min \{ F(i,j) : i \in [l,r) \}, \ \ (j \in [m,r))
\end{align} $$

と破壊的に代入するように実装し，初期値 $E(j) = \infty$ を与えることにすると，以下の擬似コードのように非常にシンプルに実装できます．

E = [inf for j in range(n)]
def solve(l,r)
  if l+1 == r:
    E[l] = F(l,r)
  else:
    m = (l+r)/2
    solve(l,m)
    induce(l,m,r)
    solve(m,r)

冒頭の問題＆関連研究

冒頭の問題に対して，単調最小値DPをオフライン・オンライン変換すると $O(n \log^2 n)$ 時間アルゴリズムが作れます．オフラインDPとして SMAWK [2] を使うと $O(n \log n)$ 時間となります．キューを用いた $O(n \log n)$ 時間もあります [3]．実は SMAWK を直接オンラインに変換したアルゴリズムが知られており，$O(n)$ が達成できます [4]．

参考文献

[1] Marvin Kunnemann, Ramamohan Paturi, and Stefan Schneider (2017): "On the fine-grained complexity of one-dimensional dynamic programming", ICALP'2017. https://arxiv.org/pdf/1703.00941.pdf
[2] https://en.wikipedia.org/wiki/SMAWK_algorithm
[3] Zvi Galil and Raffaele Giancarlo (1989): "Speeding up dynamic programming with applications to molecular biology", Theoretical Computer Science. https://pdfs.semanticscholar.org/dfdb/3899ece542b27bc039a0f7b20ef3c661af14.pdf
[4] Amotz Bar-Noy, Mordicai J. Golin, and Yan Zhang (2009): "Online dynamic programming speedups", Theory of Computing Systems. https://www.researchgate.net/profile/Amotz_Bar-Noy/publication/225439706_Online_Dynamic_Programming_Speedups/links/55176dac0cf29ab36bc15860.pdf