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

Question

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

我试图谷歌在什么时候（什么大小）我应该从动态编程切换到分支和绑定，但我无法得到我想要的结果。

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

谢谢。

Answer 1

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

一些提示：

• 您知道 DP 的运行时间与对象数量乘以背包大小成正比。
• 您知道 B&B 的运行时可能与 2 ^{# 个 objects}一样糟糕，但通常要好得多。试着找出最坏的情况。
• 缓存和其他东西对 DP 来说很重要，所以你需要分段估计它的运行时间。找出断点在哪里。
• DP 占用大量内存。如果它会占用太多，那么你在DP和B&B之间真的没有选择。