如何找出動態規劃的答案是否是最佳答案？

-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

如何找出動態規劃的答案是否是最佳答案？

回答

相關問題