查找表和动态规划

Question

6

在旧游戏时代，我们习惯于拥有一个预先计算好的正弦和余弦值等数值表格，因为在那个老版CPU上计算这些值的速度很慢。这是否被视为动态规划技术？或者动态规划必须解决一直被计算或类似地递归的函数？

更新：在动态规划中，关键是要有一个备忘录表，这就是sin、cos查找表的解决方案，那么这种技术的区别是什么呢？

- Ahmed Saleh

3

根据你问题中所描述的，我认为这并不是动态规划。动态规划更注重通过解决较小的子问题，并找到从这些子问题得出问题解决方案的方法来解决问题。 - Roman Pekar

我认为这更像是惰性求值而不是动态规划。 - Roman Pekar

维基百科有关于动态规划的描述：http://zh.wikipedia.org/wiki/动态规划 - Barmar

1

@RomanPekar 不，惰性求值是完全不同的东西。这只是一种空间与时间的权衡，有点像记忆化。 - Barmar

@Barmar 我的错，当然是记忆化。 - Roman Pekar

3个回答

4

根据我在你的问题中所看到的，我认为这不是动态规划。动态规划更多地是通过解决较小的子问题并创建方法从子问题获得问题的解决方案来解决问题。

你的情况看起来更像记忆化。

对我而言，如果您的问题是计算cos N，并且您有公式可以从cos 0、cos 1、...、cos i-1的数组中计算cos i，那么您可以计算cos 1、sin 1，并且从i从0到N运行您的计算。

也许有人会纠正我 :)

还有一句有趣的引用，关于如何将动态规划与分治范例区分开来：

如果一个问题可以通过组合非重叠子问题的最优解来解决，该策略称为“分而治之”，而不是动态规划。因此，归并排序和快速排序不被归类为动态规划问题。要应用动态规划，问题必须具有最优子结构和重叠子问题这两个关键属性。

- Roman Pekar

0

不，我认为这不是动态规划。由于计算能力有限，正弦和余弦的值被作为预先计算的值提供，就像其他数字常量一样。

要使用动态规划技术解决问题，有许多必要条件。其中一个重要条件是我们应该能够将问题分解成可递归求解的子问题，这些子问题的结果可以用作查找表来替换递归中的更高链。因此，它既是递归又是记忆。

有关更多信息，您可以参考维基百科链接。 http://en.wikipedia.org/wiki/Dynamic_programming

- praks411

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Vik · Accepted Answer

动态规划是一种编程技术，通过将一个困难的问题分解成较小的、但并不独立的子问题来解决它（这很重要！）。

即使您可以从cos i-1计算cos i，这仍然不是动态规划，只是递归。

您想用N个物品填满大小为W的背包，每个物品都有其大小和价值。由于您不知道哪种排列方式最好，因此您会“尝试”每一种情况。

递推公式将类似于：

OPT(m,w) = MAX ( OPT(m-1, w), //if I don't take this object
                 OPT(m-1, w - w(m)) //If i take it

加入初始情况，这就是解决问题的方法。当然，您应该从m = 0，w = 0开始构建解决方案，并迭代直到m = N和w = W，这样您就可以重复使用先前计算的值。

使用此技术，您可以在N*W的时间内找到将对象带入背包的最佳组合（这当然不是多项式输入大小，否则P = NP，没有人想要！），而不是指数数量的计算步骤。