我應該用什麼樣的算法來找出動態規劃的問題答案是否是最優答案?你可以推薦一些文件來幫助我找出答案嗎?如何找出動態規劃的答案是否是最佳答案?
-1
A
回答
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解決。
相關問題
- 1. 給出的答案
- 2. 如何拒絕一個答案,如果前面的答案和目前的答案是等於
- 3. 如何劃分輸入答案?
- 4. 答案是:6÷2(1 + 2)=?
- 5. sort_values與排序給出不同的答案,但sort_values是正確的答案
- 6. Xtend「電影例子」最佳答案
- 7. 評論與投票和「最佳答案」
- 8. 檢查答案是否正確
- 9. 100%條形圖SQL - 是/否答案
- 10. 整數線性規劃是否提供最佳解決方案?
- 11. 如何等待用戶答案並保留選擇的答案
- 12. 如何訪問Movilizer答案中選定答案項的標籤
- 13. 如何滿足學生的答案,實際答案
- 14. 動態MVC RadioButton組選擇的答案
- 15. 打印兩個雙打答案給出了答案0.00
- 16. 如何顯示答案一旦答案超過2位小數
- 17. 驗證答案
- 18. 間隔答案
- 19. 打印答案
- 20. 顯示答案
- 21. Randomise LuisDialog答案
- 22. Handle AuthorizeAttribute答案
- 23. 減少功能給出否定答案
- 24. MATLAB不會給出答案
- 25. HttpURLConnection:如何閱讀答案
- 26. ReSTful webservice真的是我的答案嗎?
- 27. 簡單劃分答案無小數位
- 28. 明確的答案
- 29. 不同的答案
- 30. 伯爵的答案是88:爲什麼?
我認爲你首先必須定義問題和「最優」。 – 2012-01-28 00:46:04
你可以舉一個例子,你懷疑動態編程會給你一個非最優的答案嗎?我不完全明白你的問題,因爲根據定義,我相信如果你的問題可以說是一個動態編程問題,那麼動態編程會給你一個最佳答案(假設你可以計算它)。 – Mathias 2012-01-28 06:53:42