差分

この文書の現在のバージョンと選択したバージョンの差分を表示します。

この比較画面にリンクする

両方とも前のリビジョン 前のリビジョン
次のリビジョン
前のリビジョン
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つ、基準となる暫定解が必要だが、
programming_algorithm/dynamic_programming/branch_and_bound.txt · 最終更新: 2019/11/06 by ikatakos
CC Attribution 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0