木上のナップサック問題

はじめに

背景・動機

ナップサック問題は以下の組合せ最適化問題です．

ナップサック問題
アイテムの集合を $V$ とする．各アイテム $i \in V$ には価値 $p_i \in \mathbb{N}$ と重さ $w_i \in \mathbb{N}$ が設定されている．総予算 $C \in \mathbb{N}$ が与えられたとき，予算内で最も合計価値が大きくなるアイテムの組み合わせを求めよ．

この問題はよく知られているように動的計画法で $O(n C)$ 時間で解けます ($n = |V|$)．

いま，（根付き）木の頂点にアイテムが 1 つずつ置いてあり，選んでよいアイテムが「木から定まる制約」を満たさないといけない場合を考えましょう．このような問題を一般に 木上のナップサック問題 と呼ぶことにします．木から定まる制約には様々なものがあり，代表的なものとして独立集合制約があります．

独立集合制約木ナップサック問題
木 $T = (V, E)$ が与えられる．木の各頂点 $i \in V$ には価値 $p_i \in \mathbb{N}$ と重さ $w_i \in \mathbb{N}$ が設定されている．総予算 $C \in \mathbb{N}$ が与えられたとき，予算内で最も合計価値が大きくなるアイテムの組み合わせを求めよ．ただし木上で隣り合う頂点を同時に選ぶことはできない．

この問題もよく知られているように動的計画法で解けます．TreeDP(i) を設計するアルゴリズム（再帰関数）とします．(Xs, Xf) = TreeDP(i) のとき，Xs[c] は i を含む合計容量 c の最適値，Xf は i を含まない合計容量 c の最適値をあらわすものとすると，アルゴリズムは以下のように実装できます．

def TreeDP(i):
  Xs = Xf = [0, -infty, ..., -infty]
  for j in i.children():
    (Ys, Yf) = TreeDP(j)
    Xs[c] = max { Xs[c_1] + Yf[c_2] : c_1 + c_2 = c } for all c 
    Xf[c] = max { Xf[c_1] + max { Ys[c_2], Yf[c_2] } : c_1 + c_2 = c } for all c
  Xs[c] = Xs[c-w_i] + p_i for all c
  return (Xs, Xf)

この手法の計算量は $O(n C^2)$ 時間となります．

さて，ここからが本ノートの本題です．もし入力が $n = 100$, $C = 100000$ などで $O(n C^2)$ が間に合わない場合はどうすればよいでしょうか．このような状況は実用的にはしばしば出現しますし，競技プログラミングでも出現します（cf: ICPC'18国内予選 H）．また、ナップサックアルゴリズムに対する FPTAS を構成する際に $C^2$ が許せない場合があります（精度 $\epsilon$ に対する依存性が $C$ の次数に対応する）．

成果

本ノートでは，この手の問題に対して $O(\text{poly}(n) C)$ 時間アルゴリズムを導出する「再帰動的計画法」というテクニックを紹介します．本ノートでは独立集合問題に限定して説明しますが，かなり広いクラスについて使用可能なテクニックです．

このテクニックはごく最近我々が提案したものです．原稿が http://arxiv.org/abs/1807.04942 にあります．興味のある方は原稿を参照してください．

再帰動的計画法

上述の TreeDP のような「普通の DP」は，部分解をマージするために max-plus convolution と呼ばれる操作が必要となります．この操作を適当な $\epsilon > 0$ について $O(C^{2-\epsilon})$ で行う手法は無いだろうと予想されているので，$O(\text{poly}(n)C)$ 時間アルゴリズムを作るためには本質的に発想を変えなければいけません．

提案手法は「各部分木について複数回順番に解く」ことでマージを代用します．簡単のため，まずは木が平衡，すなわち，自分の子が張る部分木のサイズが自分のサイズの半分以下である場合に多項式時間で動くアルゴリズムを説明します．

設計するアルゴリズム RecDP(i, X) は頂点 i のほかに配列 X を引数にとります．X は「途中までナップサックにアイテムを詰め込んだときのナップサックの状態」であり，動的計画法の初期値に相当します．(Xs, Xf) = RecDP(i, X) のとき Xs[c] は X に加えて i 以下の頂点を i を含むという条件で合計容量 c になるよう最適に詰め込んだときの最適値，Xf[c] は X に加えて i 以下の頂点を i を含まないという条件で合計容量 c になるよう最適に詰め込んだときの最適値とします．するとアルゴリズムは以下のように実装できます．

RecDP(i, X)
  Xs = X
  Xf = X
  for j in i.children():
    (Ys, Yf) = RecDP(j, Xs)
    (Zs, Zf) = RecDP(j, Xf)   
    Xs = Yf
    Xf = max { Zs, Zf }
  Xs[c] = Xs[c-w_i] + p_i for all c
  return (Xs, Xf)

アルゴリズムは i を含む最適値テーブル Xs と i を含まない最適値テーブル Xf を更新します．Xs は自分の子を含んではいけないので再帰的に呼んで得られた解のうち Yf に順次更新していき，最後に i を追加します．Xf は自分の子を含んでも含まなくてもよいので再帰的に呼んで得られた解の max に順次更新していきます．

計算量を評価しましょう．各頂点 $i$ に注目すると，各子は２回ずつ再帰呼び出しをうけます．そのため $n$ を $i$ 以下の頂点数，$n_1, \ldots, n_d$ を $i$ の子以下の頂点数とすると，計算量 $f$ は以下の式を満たします．

$$ f(n) \le 2 \left( f(n_1) + \cdots + f(n_d) \right) + O(C) $$

これを解きましょう．一般性を失わず $f$ は $n$ に関して凸としてよいです（$\because$ 次数 $1$ 以上の多項式は凸なので）．もしすべての子が $n_i \le n/2$ を満たすのであれば（すなわち木が平衡しているのであれば），$f$ の凸性から

$$ f(n) \le 4 f((n-1)/2) + O(C) $$

と変形できます（$\because$ $n_1 \le n_2$ のとき $f(n_1) + f(n_2) \le f(n_1-1) + f(n_2+1)$ であることを繰り返し使って大きい側が $n/2$ に張り付くようにする）．これを解いて $f(n) = O(n^2 C)$ を得ます．

重軽再帰動的計画法

上の解析では，複数回呼ばれる部分木の頂点数がもとの木の頂点数よりも定数倍小さくなっていることが重要でした（これがあると再帰深さが $O(\log n)$ になり，$O(1)^{O(\log n)} = n^{O(1)}$ から多項式時間になる）．これが保証されない場合にはどうすればよいでしょうか．

アルゴリズム RecDP(i, X) を観察すると，じつは一番最初の子に対する２回の再帰は引数が共通であることがわかります．したがって一番最初の子に限っては再帰呼び出し回数を１回にできます．そこで再帰を呼び出す最初の頂点を最も部分木の頂点数が多いもの，すなわち heavy child にとる以下の実装が考えられます．

HLRecDP(i, X)
  h = heavy child of i
  (Zs, Zf) = RecDP(h, X)
  Xs = Zf
  Xf = max { Zs, Zf }
  for j in i.children():
    if j == h: continue
    (Ys, Yf) = HLRecDP(j, Xs)
    (Zs, Zf) = HLRecDP(j, Xf)   
    Xs = Yf
    Xf = max { Zs, Zf }
  Xs[c] = Xs[c-w_i] + p_i for all c
  return (Xs, Xf)

計算量を評価しましょう．先と同じ記号を使うと

$$ f(n) \le f(n_1) + 2 \left( f(n_2) + \cdots + f(n_d) \right) + O(C) $$

となります．ただし $n_1$ は heavy child の頂点数です．定義から $n_j \le n_1$ なので $n_j \le n/2$ が成立します ($j = 2, \ldots, d$) ．これが最大を達成するのは $n_1 = n_2 = (n-1)/2$, $n_3 = ... = n_d = 0$ のときなので

$$ f(n) \le 3 f((n-1)/2) + O(C) $$

となり，これを解いて $f(n) = O(n^{\log_2 3} C) \approx O(n^{1.58} C)$ を得ます．

応用

ここで述べたテクニックを使うと「i が含まれるなら i の親も含まれる」という先行制約について $O(n C)$ 時間アルゴリズムを導出できます（この場合重軽は不要）．この方法で導出されるアルゴリズムは Left-Right Dynamic Programming や Depth-First Dynamic Programming と呼ばれる先行制約用アルゴリズムと本質的に等価となっています．また，これらのアルゴリズムを参考にすると ICPC'18 国内予選 H が解けます．

余談

ICPC'18国内予選 H の作問者はわたしではありません．上にリンクを示した原稿（論文）を書いている中で別の方が「どんぴしゃ」な問題を提案したので冷や汗をかきました．論文の主著者氏が ICPC 引退していてよかったですね．

追記 (2018/10/25)

この論文がアルゴリズム分野の査読付き国際会議 WALCOM'19 に通りました．