分枝限定法

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

分枝操作
- 部分問題へ分割する
限定操作
- 「緩和問題」: 部分問題から、制約条件を緩めて最適解の上限を簡単に計算できるようにしたもの
- 緩和問題の最適解は、必ず元の問題の最適解より大きい
- 緩和問題から得られる上限見積もりが、現在の暫定ベストより悪ければ、そこで打ち切る

（※「上限」「大きい」というのは最大化問題の場合で、最小化問題なら「下限」「小さい」となる）

近い概念に動的計画法があるが、動的計画法は、分枝操作が可能で同じ部分問題を何回も要求される問題に対して、記録して同じ問題を解かないようにする。

分枝限定法は、同じ部分問題が要求されるかは重要ではなく、最適解が得られないことがわかった問題を切り捨てて調べる空間を減らす、というような理解。

適用できる問題の条件

部分問題に分割できること
緩和問題が高速に解けること

緩和問題は適切な唯一の方法があるわけでは無い。前提が誤っている（緩和問題の解より実際の解が大きくなるなど）でない限り、正しい解は求まる。

より実際の解に近い上限を推定できる緩和問題を採用すれば、より効率的に無駄な探索空間を除外できる。

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

適用例

ナップサック問題

大元の問題
- 容量 $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番目を取った場合/取らなかった場合」……などに更に分割しても無駄であり、現在の部分問題は切り捨ててよいとわかる。

実装例

途中結果を保持するデータ構造

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

緩和問題の計算

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

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

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

その時の上限価値は、仮定済みの $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

部分問題の探索順序

ナップサックの実装例では、品物毎に入れる/入れないに分割して、上から順番に探索していた。これは幅優先探索である。

       ○            元の問題
入れる/  \入れない
    ○    ○         1番目を仮定
    /\    /\
   ○○  ○○        2番目を仮定
   /\/\  /\/\ ...

これは、動的計画法の実装を流用しやすかったためだが、一方でデメリットもある。

というのも、限定操作により切り捨てて良いかを判断するには、とりあえず1つ、基準となる暫定解が必要だが、このように全ての枝の深さが均等なナップサック問題では、暫定解を得る（＝下まで降りきる）のに時間がかかる。

（実装例では、最後まで探索しなくてもとりあえずちょっと粗めの暫定解をすぐに得られるようにしているが）

部分問題の探索順序は他にもあって、

深さ優先探索
- とりあえずの暫定解を得るのは速い
- 実装が簡単
- 早めに真の最適解ルートをたどれれば速いが、評価の悪い方から順に探索してしまうと全然減らない
  - 運任せな面がある。とはいえ、通常は期待値的には十分効果がある
最良優先探索
- 何らかの方法で「大元の問題の推定値」がよい方から順に探索
  - ナップサックでは「入れると仮定済みの品物の価値 + 残りの部分問題の上限値」など
- 良い推定値関数を使えば、とても効率的
- 経路探索のDijkstraを拡張した、A*というアルゴリズムに採用されている
最良上界探索（最良下界探索）
- 「緩和問題の解」がよい方から順に探索

目次