Edited at 2018-02-07

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

以下の問題を考えます．

１次元の直線上に地点 $x [0] < x [1] < \dots < 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, \dots$ を順番にオフライン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 \geq j$ とします．これをすべて計算する関数 $solve (l, r)$ を設計しましょう． $solve (0, n)$ を呼べば，本来欲しかった値がすべて計算されます．

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

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

\begin{aligned} 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{aligned}

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

計算量は

T (n) \leq 2 T (n / 2) + M (n)

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

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

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

と破壊的に代入するように実装し，初期値 $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

[1] では static と読んでいますが，DP業界では伝統的に online/offline と呼ばれています． ↩

オフラインDP / オンラインDP
- オフラインDPの例：区間を k 分割する DP
- オンラインDPの例：区間を任意個に分割する DP
オフライン・オンライン変換
冒頭の問題＆関連研究
参考文献

@tmaehara

Toot

If you already have a Qiita account log in.