差分
このページの2つのバージョン間の差分を表示します。
| 両方とも前のリビジョン前のリビジョン次のリビジョン | 前のリビジョン最新のリビジョン両方とも次のリビジョン | ||
| programming_algorithm:dynamic_programming:branch_and_bound [2019/11/06] – [ナップサック問題] ikatakos | programming_algorithm:dynamic_programming:branch_and_bound [2019/11/06] – [部分問題の探索順序] ikatakos | ||
|---|---|---|---|
| 行 3: | 行 3: | ||
| * [[wpjp> | * [[wpjp> | ||
| * [[http:// | * [[http:// | ||
| + | * [[https:// | ||
| 「分枝操作」と「限定操作」を行うことで、効率的に問題を解く方法。 | 「分枝操作」と「限定操作」を行うことで、効率的に問題を解く方法。 | ||
| 行 9: | 行 10: | ||
| * 部分問題へ分割する | * 部分問題へ分割する | ||
| * 限定操作 | * 限定操作 | ||
| - | * その部分問題から得られる最適解の上限(下限)見積もりが、現在の暫定ベストより悪ければ、そこで打ち切る | + | * 「緩和問題」: |
| + | * 緩和問題の最適解は、必ず元の問題の最適解より大きい | ||
| + | * 緩和問題から得られる上限見積もりが、現在の暫定ベストより悪ければ、そこで打ち切る | ||
| + | |||
| + | （※「上限」「大きい」というのは最大化問題の場合で、最小化問題なら「下限」「小さい」となる） | ||
| + | |||
| + | 近い概念に動的計画法があるが、動的計画法は、分枝操作が可能で同じ部分問題を何回も要求される問題に対して、同じ部分問題を解かないようにする。 | ||
| + | |||
| + | 分枝限定法は、同じ部分問題が要求されるかは重要ではなく、最適解が得られないことがわかった問題を切り捨てて調べる空間を減らす、というような理解。 | ||
| - | 動的計画法は分枝操作が可能な問題に対して同じ計算を行わないようにするが、 | ||
| - | そこに「限定操作」を加えて、最適解が得られないことがわかった問題を切り捨てる、というような理解。 | ||
| =====適用できる問題の条件===== | =====適用できる問題の条件===== | ||
| * 部分問題に分割できること | * 部分問題に分割できること | ||
| - | * 部分問題の上限(下限)見積もりが（高速に）できること | + | * 緩和問題が高速に解けること |
| - | 上限/ | + | 緩和問題は適切な唯一の方法があるわけでは無い。 |
| - | 見積もりが誤っている（推定上限より実際の解が大きくなるなど）でない限り、正しい解は求まる。 | + | 前提が誤っている（緩和問題の解より実際の解が大きくなるなど）でない限り、正しい解は求まる。 |
| - | より実際の解に近い見積もり方法を採用すれば、より無駄な探索空間を除外でき、効率的になる。 | + | より実際の解に近い上限を推定できる緩和問題を採用すれば、より効率的に無駄な探索空間を除外できる。 |
| - | しかし、見積もりは部分問題毎に毎回計算するので、これに時間がかかるようでは本末転倒。削減できる探索空間とのトレードオフとなる。 | + | しかし、緩和問題は部分問題毎に毎回計算するので、これに時間がかかるようでは本末転倒。削減できる探索空間とのトレードオフとなる。 |
| =====適用例===== | =====適用例===== | ||
| 行 42: | 行 49: | ||
| * 容量 $W$ のナップサックに価値が $v_2, | * 容量 $W$ のナップサックに価値が $v_2, | ||
| - | ===評価関数=== | + | ===緩和問題=== |
| もし品物が1個単位でなく、「3/ | もし品物が1個単位でなく、「3/ | ||
| 行 65: | 行 72: | ||
| $\frac{v_i}{w_i}$ の高い方から取る/ | $\frac{v_i}{w_i}$ の高い方から取る/ | ||
| - | 1～3番目を取って4～6番目を取らなかった時に、価値が22となるという暫定解が得られたとする。これを暫定最大値とする。 | + | 1～3番目を取って4～6番目を取らなかった時に、価値が22となるという結果が得られたとする。これを暫定最大値とする。 |
| ではここで、1番目を取り2番目を取らなかった場合の、3～6番目からなる部分問題を考える（いきなりここに飛ぶわけでは無く、探索の過程で訪れたとする）。 | ではここで、1番目を取り2番目を取らなかった場合の、3～6番目からなる部分問題を考える（いきなりここに飛ぶわけでは無く、探索の過程で訪れたとする）。 | ||
| - | 上限を計算すると、 | + | 緩和問題を計算すると、 |
| W = 13-3 = 10 | W = 13-3 = 10 | ||
| 行 77: | 行 84: | ||
| これに、確定済みの1番目を合わせて 21.875 | これに、確定済みの1番目を合わせて 21.875 | ||
| - | これがこの部分問題から達成できる価値の上限となる。 | + | これが緩和問題の解で、現在の部分問題から達成できる価値の上限となる。 |
| この時点でどうやっても今の暫定最大値22を超えられないので、 | この時点でどうやっても今の暫定最大値22を超えられないので、 | ||
| - | 「3番目を取った場合/ | + | 「3番目を取った場合/ |
| - | + | 現在の部分問題は切り捨ててよいとわかる。 | |
| - | この時点でこの部分問題は切り捨ててよいとわかる。 | + | |
| ===実装例=== | ===実装例=== | ||
| - | DPをlistで持つと、Wの上限が大きい場合とか、Vの上限が大きい場合とかで別の実装が必要となるので、dictで持つと楽（計算はほんの少し遅い？） | + | ==途中結果を保持するデータ構造== |
| + | |||
| + | listで持つと、Wの上限が大きい場合とか、Vの上限が大きい場合とかで別の実装が必要となるので、dictで持つと楽（計算はほんの少し遅い？） | ||
| + | |||
| + | ==緩和問題の計算== | ||
| - | 上限の計算では連続した品物を選択するので、累積和+二分探索で1個丸ごと取れる境界を得た後、端数を計算する。 | + | 緩和問題では |
| 重さの累積和配列を $w_{acc}$、価値の累積和配列を $v_{acc}$ とする。 | 重さの累積和配列を $w_{acc}$、価値の累積和配列を $v_{acc}$ とする。 | ||
| - | $i$ 番目までをそれぞれ取る/ | + | $i$ 番目までのそれぞれ取る/ |
| ナップサックの総容量は取らないと仮定している品物の分だけ水増しして考えて、$W + w_{acc}[i] - w_t$ と見なせる。 | ナップサックの総容量は取らないと仮定している品物の分だけ水増しして考えて、$W + w_{acc}[i] - w_t$ と見なせる。 | ||
| - | これを超えない最大のindexを $w_{acc}$ から得る。$j$ とする。 | + | これを超えない最大のindexを二分探索などで |
| その時の上限価値は、仮定済みの $v_t$ に $v_{i+1}～v_j$ の累積和を合わせたものなので、$v_t + v_{acc}[j] - v_{acc}[i]$、 | その時の上限価値は、仮定済みの $v_t$ に $v_{i+1}～v_j$ の累積和を合わせたものなので、$v_t + v_{acc}[j] - v_{acc}[i]$、 | ||
| 行 100: | 行 110: | ||
| これに $j+1$ 番目の品物（あれば）の端数分をあわせたものが、上限価値となる。 | これに $j+1$ 番目の品物（あれば）の端数分をあわせたものが、上限価値となる。 | ||
| - | $i$ まで仮定済みの中で $w_t$ が大きい方から処理していく限り、$j$ が戻ることは無いので、二分探索の部分は尺取りの方がいいかも。 | + | 同じ |
| <sxh python> | <sxh python> | ||
| 行 145: | 行 155: | ||
| return best | return best | ||
| </ | </ | ||
| + | |||
| + | |||
| + | ====部分問題の探索順序==== | ||
| + | |||
| + | ナップサックの実装例では、品物毎に入れる/ | ||
| + | |||
| + | | ||
| + | 入れる/ | ||
| + | ○ ○ | ||
| + | /\ /\ | ||
| + | | ||
| + | / | ||
| + | |||
| + | これは、動的計画法の実装を流用しやすかったためだが、一方でデメリットもある。 | ||
| + | |||
| + | というのも、限定操作により切り捨てて良いかを判断するには、とりあえず1つ、基準となる暫定解が必要だが、 | ||
| + | このように全ての枝の深さが均等なナップサック問題では、暫定解を得る（＝下まで降りきる）のに時間がかかる。 | ||
| + | |||
| + | （実装例では、最後まで探索しなくてもとりあえずちょっと粗めの暫定解をすぐに得られるようにしているが） | ||
| + | |||
| + | 部分問題の探索順序は他にもあって、 | ||
| + | |||
| + | * 深さ優先探索 | ||
| + | * とりあえずの暫定解を得るのは速い | ||
| + | * 実装が簡単 | ||
| + | * 早めに真の最適解ルートをたどれれば速いが、評価の悪い方から順に探索してしまうと全然減らない | ||
| + | * 運任せな面がある。とはいえ、通常は期待値的には十分効果がある | ||
| + | * 最良優先探索 | ||
| + | * 何らかの方法で「大元の問題の推定値」がよい方から順に探索 | ||
| + | * ナップサックでは「入れると仮定済みの品物の価値 + 残りの部分問題の上限値」など | ||
| + | * 良い推定値関数を使えば、とても効率的 | ||
| + | * 経路探索のDijkstraを拡張した、A*というアルゴリズムに採用されている | ||
| + | * 最良上界探索（最良下界探索） | ||
| + | * 「緩和問題の解」がよい方から順に探索 | ||
| + | |||
