如何找出动态规划的答案是否是最佳答案？

-1

我应该用什么样的算法来找出动态规划的问题答案是否是最优答案？你可以推荐一些文件来帮助我找出答案吗？如何找出动态规划的答案是否是最佳答案？

2012-01-28 ePezhman

我认为你首先必须定义问题和“最优”。 – 2012-01-28 00:46:04

你可以举一个例子，你怀疑动态编程会给你一个非最优的答案吗？我不完全明白你的问题，因为根据定义，我相信如果你的问题可以说是一个动态编程问题，那么动态编程会给你一个最佳答案（假设你可以计算它）。 – Mathias 2012-01-28 06:53:42

对问题的动态规划方法通常会得到正确答案 - 即找到真正的最小成本答案 - 但通常不能保证是解决使用最少量cpu或内存的问题的方法。

在很多情况下，我们不知道我们解决问题的方法是否使用尽可能少的cpu。例如，动态程序是已知的更有效的方法之一，但未被证明是最有效的可能方法是http://en.wikipedia.org/wiki/Knapsack_problem。

来源

2012-01-28 05:26:54 mcdowella

没有算法告诉您给定的动态编程解决方案是否最优。

查看Halting Problem研究密切相关的问题。

来源

2012-01-28 00:37:18

虽然在我看来，这个问题本身是有缺陷的。如果一个问题可以说是一个动态规划问题，那么这个动态规划的解决方案将是最优的吗？我能看到的唯一问题是DP问题，但可能无法解决，因为它不会终止（这可能是您的停机问题意味着什么）的情况。 – Mathias 2012-01-28 06:48:13

如果你的问题是你的意思：“我如何发现我的动态编程是否正确实施？”您也可以通过回溯来解决问题，这很容易实现，并始终提供最佳解决方案。对于相同的小数据输入，您可以尝试回溯和动态编程，如果输出相同，那么您可以强烈怀疑您的动态编程实现是正确的。否则动态规划总是给出最佳答案，但并非所有问题都可以通过DP来解决，当然并不是所有DP规划都可以使用相同的状态和/或recure解决。

来源

2012-01-28 08:16:37

如何找出动态规划的答案是否是最佳答案？

回答

相关问题