optimization - 何时从动态规划(二维表)切换到分支定界算法？

Question

我正在做一个涉及动态规划和分支定界的背包优化问题。我注意到，当问题的容量和项目变大时，填充动态规划算法的二维表会呈指数级变慢。在某些时候，我会假设我应该根据问题的大小切换算法(因为讲座给出了两种类型的优化)？

我试图用谷歌搜索我应该在什么时候(什么大小)从动态编程切换到分支定界，但我无法得到我想要的结果。

或者，是否有另一种看待背包问题的方法，我可以将动态规划和分支定界结合为一种算法，而不是根据问题的大小切换算法？

谢谢。

Answer 1

通常，当您有多种算法来解决问题但它们的运行时间具有不同的特征时，您可以确定(根据经验，而不是理论上)一种算法何时变得比另一种更快。这高度依赖于实现和机器。所以同时测量DP算法和B&B算法，然后找出哪个更好。

几个提示:

你知道 DP 的运行时间与元素数量乘以背包大小成正比。

您知道 B&B 的运行时可能与 2# 对象一样糟糕，但通常要好得多。尝试找出最坏的情况。

缓存和其他东西对 DP 很重要，所以你需要分段估计它的运行时间。找出断点在哪里。

DP 占用了过多的内存。如果它会占用太多，你真的没有在DP和B＆B之间选择。