分枝限定法

「分枝操作」と「限定操作」を行うことで、効率的に問題を解く方法。

分枝操作
- 部分問題へ分割する
限定操作
- その部分問題から得られる最適解の上限(下限)見積もりが、現在の暫定ベストより悪ければ、そこで打ち切る

動的計画法は分枝操作が可能な問題に対して同じ計算を行わないようにするが、そこに「限定操作」を加えて、最適解が得られないことがわかった問題を切り捨てる、というような理解。

適用できる問題の条件

部分問題に分割できること
部分問題の上限(下限)見積もりが（高速に）できること

上限/下限見積もりに適切な唯一の手段があるわけでは無い。見積もりが誤っている（推定上限より実際の解が大きくなるなど）でない限り、正しい解は求まる。

より実際の解に近い見積もり方法を採用すれば、より無駄な探索空間を除外でき、効率的になる。

しかし、見積もりは部分問題毎に毎回計算するので、これに時間がかかるようでは本末転倒。削減できる探索空間とのトレードオフとなる。

適用例

ナップサック問題

大元の問題
- 容量 $W$ のナップサックに価値が $v_1,v_2,v_3,v_4$、重さが $w_1,w_2,w_3,w_4$ の品物を出来るだけ詰めて、価値を最大化する

分枝操作

1つめの品物を入れた場合と入れない場合に分割

入れた場合
- 容量 $W-w_1$ のナップサックに価値が $v_2,v_3,v_4$、重さが $w_2,w_3,w_4$ の品物を詰めて、価値$+v_1$ を最大化
入れない場合
- 容量 $W$ のナップサックに価値が $v_2,v_3,v_4$、重さが $w_2,w_3,w_4$ の品物を詰めて、価値を最大化

評価関数

もし品物が1個単位でなく、「3/5個入れる」ようなことができる場合、解くのは簡単である。

重さあたりの価値 $\frac{v_i}{w_i}$ が高い方から順に、貪欲に詰めていけばよい。

W = 13
v  8  5  9  4  7  1  (v/wの大きい順)
w  3  2  5  4  8  2

3番目まで選んで、重さ 3+2+5=10、価値 8+5+9=22
4番目を"3/4個"選んで、価値 22+(4 * 3/4)=25

そして、1個単位でしか詰められない元の問題は、この解より大きくなることは無い。（どれかを諦めなければならず、空いたスペースに代わりの品物を入れられるとしてもそれは重さあたりの価値効率がより低いため）

つまり上限となる。

限定操作

ここで、元の問題の探索に戻る。

$\frac{v_i}{w_i}$ の高い方から取る/取らない場合に分割して探索していく。 1～3番目を取って4～6番目を取らなかった時に、価値が22となるという暫定解が得られたとする。これを暫定最大値とする。

ではここで、1番目を取り2番目を取らなかった場合の、3～6番目からなる部分問題を考える（いきなりここに飛ぶわけでは無く、探索の過程で訪れたとする）。上限を計算すると、

W = 13-3 = 10
v  9  4  7  1
w  5  4  8  2

3,4番目と、5番目を"1/8個" 詰めるとちょうど一杯になり、価値は 9+4+7/8=13.875
これに、確定済みの1番目を合わせて 21.875

これがこの部分問題から達成できる価値の上限となる。

この時点でどうやっても今の暫定最大値22を超えられないので、「3番目を取った場合/取らなかった場合」……などに更に分割しても、暫定よりいい解が得られることは無い。

この時点でこの部分問題は切り捨ててよいとわかる。

実装例

DPをlistで持つと、Wの上限が大きい場合とか、Vの上限が大きい場合とかで別の実装が必要となるので、dictで持つと楽（計算はほんの少し遅い？）

上限の計算では連続した品物を選択するので、累積和+二分探索で1個丸ごと取れる境界を得た後、端数を計算する。重さの累積和配列を $w_{acc}$、価値の累積和配列を $v_{acc}$ とする。

$i$ 番目までをそれぞれ取る/取らないを仮定したケースの上限を考えるとき、ある仮定について合計重さ $w_t$、合計価値 $v_t$ とすると、

ナップサックの総容量は取らないと仮定している品物の分だけ水増しして考えて、$W + w_{acc}[i] - w_t$ と見なせる。これを超えない最大のindexを $w_{acc}$ から得る。$j$ とする。

その時の上限価値は、仮定済みの $v_t$ に $v_{i+1}～v_j$ の累積和を合わせたものなので、$v_t + v_{acc}[j] - v_{acc}[i]$、

これに $j+1$ 番目の品物（あれば）の端数分をあわせたものが、上限価値となる。

$i$ まで仮定済みの中で $w_t$ が大きい方から処理していく限り、$j$ が戻ることは無いので、二分探索の部分は尺取りの方がいいかも。

from bisect import bisect
from collections import defaultdict
from itertools import accumulate


def knapsack(n, W, items):
    """
    :param n: number of items
    :param W: capacity of knapsack
    :param items: list of items (value, weight)
    :return:
    """
    weights = defaultdict(lambda: 0)
    weights[0] = 0

    items.sort(key=lambda a: a[0] / a[1], reverse=True)
    val_list, wei_list = map(list, zip(*items))
    acc_val_list = [0] + list(accumulate(val_list))
    acc_wei_list = [0] + list(accumulate(wei_list))
    acc_val_list.append(acc_val_list[-1])

    best = acc_val_list[bisect(acc_wei_list, W) - 1]
    for i, (v, w) in enumerate(items):
        search_weight = W + acc_wei_list[i]
        ignore_values = acc_val_list[i]
        for weight, value in list(weights.items()):
            if weight + w > W:
                continue
            upi = bisect(acc_wei_list, search_weight - weight) - 1
            full_best = value + acc_val_list[upi] - ignore_values
            if upi < n - 1:
                partial_best = val_list[upi] \
                               * (search_weight - weight - acc_wei_list[upi]) / wei_list[upi]
            else:
                partial_best = 0
            if full_best + partial_best <= best:
                weights.pop(weight)
                continue
            best = max(best, full_best)
            weights[weight + w] = max(weights[weight + w], value + v)
    return best

目次