差分
このページの2つのバージョン間の差分を表示します。
両方とも前のリビジョン前のリビジョン次のリビジョン | 前のリビジョン | ||
programming_algorithm:dynamic_programming:branch_and_bound [2019/11/06] – ikatakos | programming_algorithm:dynamic_programming:branch_and_bound [2019/11/06] (現在) – [分枝限定法] ikatakos | ||
---|---|---|---|
行 16: | 行 16: | ||
(※「上限」「大きい」というのは最大化問題の場合で、最小化問題なら「下限」「小さい」となる) | (※「上限」「大きい」というのは最大化問題の場合で、最小化問題なら「下限」「小さい」となる) | ||
- | 近い概念に動的計画法があるが、動的計画法は、分枝操作が可能で同じ部分問題を何回も要求される問題に対して、同じ部分問題を解かないようにする。 | + | 近い概念に動的計画法があるが、動的計画法は、分枝操作が可能で同じ部分問題を何回も要求される問題に対して、記録して同じ問題を解かないようにする。 |
分枝限定法は、同じ部分問題が要求されるかは重要ではなく、最適解が得られないことがわかった問題を切り捨てて調べる空間を減らす、というような理解。 | 分枝限定法は、同じ部分問題が要求されるかは重要ではなく、最適解が得られないことがわかった問題を切り捨てて調べる空間を減らす、というような理解。 | ||
行 168: | 行 168: | ||
/ | / | ||
- | これは、動的計画法の実装を流用しやすかったことと、緩和問題を解くのに累積和を利用して高速化しやすかったためだが、一方でデメリットもある。 | + | これは、動的計画法の実装を流用しやすかったためだが、一方でデメリットもある。 |
というのも、限定操作により切り捨てて良いかを判断するには、とりあえず1つ、基準となる暫定解が必要だが、 | というのも、限定操作により切り捨てて良いかを判断するには、とりあえず1つ、基準となる暫定解が必要だが、 | ||
行 180: | 行 180: | ||
* とりあえずの暫定解を得るのは速い | * とりあえずの暫定解を得るのは速い | ||
* 実装が簡単 | * 実装が簡単 | ||
- | * 早めに真の最適解ルートをたどれれば速いが、評価の悪いルートばかりたどってしまうとあまり減らない | + | * 早めに真の最適解ルートをたどれれば速いが、評価の悪い方から順に探索してしまうと全然減らない |
* 運任せな面がある。とはいえ、通常は期待値的には十分効果がある | * 運任せな面がある。とはいえ、通常は期待値的には十分効果がある | ||
* 最良優先探索 | * 最良優先探索 |