2012-01-28 53 views
-1

我應該用什麼樣的算法來找出動態規劃的問題答案是否是最優答案?你可以推薦一些文件來幫助我找出答案嗎?如何找出動態規劃的答案是否是最佳答案?

+1

我認爲你首先必須定義問題和「最優」。 – 2012-01-28 00:46:04

+0

你可以舉一個例子,你懷疑動態編程會給你一個非最優的答案嗎?我不完全明白你的問題,因爲根據定義,我相信如果你的問題可以說是一個動態編程問題,那麼動態編程會給你一個最佳答案(假設你可以計算它)。 – Mathias 2012-01-28 06:53:42

回答

3

對問題的動態規劃方法通常會得到正確答案 - 即找到真正的最小成本答案 - 但通常不能保證是解決使用最少量cpu或內存的問題的方法。

在很多情況下,我們不知道我們解決問題的方法是否使用盡可能少的cpu。例如,動態程序是已知的更有效的方法之一,但未被證明是最有效的可能方法是http://en.wikipedia.org/wiki/Knapsack_problem

2

沒有算法告訴您給定的動態編程解決方案是否最優。

查看Halting Problem研究密切相關的問題。

+0

雖然在我看來,這個問題本身是有缺陷的。如果一個問題可以說是一個動態規劃問題,那麼這個動態規劃的解決方案將是最優的嗎?我能看到的唯一問題是DP問題,但可能無法解決,因爲它不會終止(這可能是您的停機問題意味着什麼)的情況。 – Mathias 2012-01-28 06:48:13

0

如果你的問題是你的意思:「我如何發現我的動態編程是否正確實施?」您也可以通過回溯來解決問題,這很容易實現,並始終提供最佳解決方案。對於相同的小數據輸入,您可以嘗試回溯和動態編程,如果輸出相同,那麼您可以強烈懷疑您的動態編程實現是正確的。 否則動態規劃總是給出最佳答案,但並非所有問題都可以通過DP來解決,當然並不是所有DP規劃都可以使用相同的狀態和/或recure解決。