分而治之，動態規劃和貪婪算法！

當我遇到最佳子結構問題並且沒有子問題共享子子問題時，我可以使用分而治之算法來解決它嗎？分而治之，動態規劃和貪婪算法！

但是，當子問題共享子子問題（重疊的子問題）時，我可以使用動態編程來解決問題？

這是正確的嗎？

貪心算法與動態規劃類似嗎？

來源

2011-05-28 Guest

當我有最佳 substructur無子問題股 subsubproblems問題，那麼我可以用一個分而治之算法來解決呢？

是的，只要您可以找到每種子問題的最佳算法。

但是，當子問題股 subsubproblems（重疊子問題），那麼我可以使用動態編程來解決這個問題？

這是正確的嗎？

是的。動態規劃基本上是Divide &征服算法的一個特例，其中所有子問題都是相同的。

如何貪婪算法類似動態編程？

它們不同。
動態編程爲您提供最佳解決方案。
貪婪算法通常在少量時間內提供良好/合理的解決方案，但不能保證達到最佳效果。

它是，我們說，類似，因爲它通常將解決方案構造分爲幾個階段，在這幾個階段中選擇局部最優。但是，如果階段不是原始問題的最佳子結構，那麼通常不會導致最佳解決方案。

編輯：

正如@rrenaud指出的，存在已經被證明是最佳的一些貪婪算法（例如Dijkstra算法，採用Kruskal，的Prim等）。
因此，更正確的說，貪婪和動態編程的主要區別在於，前者在解決問題的空間上並不詳盡，後者則是解決方案的空間。實際上貪婪算法在這個空間上是短視的，在解決方案構建過程中做出的每個選擇都不會被重新考慮。

來源

2011-05-28 15:26:59 digEmAll

某些貪婪算法是最優的。考慮Dijkstra的最短路徑算法或最大子數組求和問題。貪婪算法往往不支持不同的可能性，因爲動態編程算法傾向於爲不同的可能最優選擇而分支，然後確定哪個選擇最好。 – 2011-05-28 21:27:26

@rrenaud：correct，edited;） – digEmAll 2011-05-29 07:28:01

能否請你解釋一下_「動態規劃基本上是分治算法家族的一個特例，其中所有子問題都是相同的。」_我不明白這一點。子問題同樣意味着什麼？ – saplingPro 2012-11-24 04:58:52

-2

貪婪的方法以自上而下的方式工作，但動態以自下而上的方式工作。如此貪婪的方法可能會給出一個不是最優的解決方案，它可以是次優的（接近最優）如果我們使用動態方法，我們必須保留所有以前的解決方案，但是在貪婪的情況下，我們在每個時刻都會做出最佳選擇沒有關於前一個這裏的區別... 這就是爲什麼我們可以得到一個不是最優的解決方案。

看到鏈接 http://en.wikipedia.org/wiki/File:Greedy-search-path-example.gif

來源

2012-03-14 18:01:48

請用戶使用適當的標點符號和大寫字母，並儘可能少用俚語。這很難閱讀和無益。此外，與最佳答案相比，您的答案不會提供任何新信息。刪除它或改進它。 – 2012-10-26 06:26:50

-2

動態程序採用自下而上的方法，節省了以前的解決方案，並參考它，這將使我們能夠使所有可用的解決方案中最佳的解決方案，而貪婪的方法是使用自頂向下方法，因此它採用本地可用解決方案的最佳解決方案，不會採用先前的解決方案，從而導致較少優化的解決方案。動態=自下而上，最優解貪婪=自上而下，欠佳，耗時更少

來源

2013-01-10 07:01:03 PRIIYANCA

分而治之，動態規劃和貪婪算法！

回答

相關問題