差分
このページの2つのバージョン間の差分を表示します。
両方とも前のリビジョン前のリビジョン | 最新のリビジョン両方とも次のリビジョン | ||
programming_algorithm:dynamic_programming:branch_and_bound [2019/11/06] – [部分問題の探索順序] ikatakos | programming_algorithm:dynamic_programming:branch_and_bound [2019/11/06] – [部分問題の探索順序] ikatakos | ||
---|---|---|---|
行 168: | 行 168: | ||
/ | / | ||
- | これは、動的計画法の実装を流用しやすかったことと、緩和問題を解くのに累積和を利用して高速化しやすかったためだが、一方でデメリットもある。 | + | これは、動的計画法の実装を流用しやすかったためだが、一方でデメリットもある。 |
というのも、限定操作により切り捨てて良いかを判断するには、とりあえず1つ、基準となる暫定解が必要だが、 | というのも、限定操作により切り捨てて良いかを判断するには、とりあえず1つ、基準となる暫定解が必要だが、 |