貪心法和動態規劃演算法的比較分析

❶ 動態規劃和貪心法有什麼區別有什麼聯系

動態規劃和貪心演算法都是一種遞推演算法
均有局部最優解來推導全局最優解

不同點：
貪心演算法：
1.貪心演算法中，作出的每步貪心決策都無法改變，因為貪心策略是由上一步的最優解推導下一步的最優解，而上一部之前的最優解則不作保留。
2.由（1）中的介紹，可以知道貪心法正確的條件是：每一步的最優解一定包含上一步的最優解。

動態規劃演算法：
1.全局最優解中一定包含某個局部最優解，但不一定包含前一個局部最優解，因此需要記錄之前的所有最優解
2.動態規劃的關鍵是狀態轉移方程，即如何由以求出的局部最優解來推導全局最優解
3.邊界條件：即最簡單的，可以直接得出的局部最優解

註：給我你電子郵箱，我把詳細資料發過去

❷ 貪心演算法——活動安排問題

•貪心演算法的特點是每個階段所作的選擇都是局部最優的，它期望通過所作的局部最優選擇產生出一個全局最優解。

貪心與動態規劃： 與動態規劃不同的是，貪心是 鼠目寸光 ；動態規劃是 統攬全局 。

–動態規劃：每個階段產生的都是全局最優解

•第i階段的「全局」： 問題空間為(a1, … , ai)

•第i階段的「全局最優解」：問題空間為 (a1, … , ai)時的最優解

–貪心：每個階段產生的都是局部最優解

•第i階段的「局部」：問題空間為按照貪心策略中的優先順序排好序的第i個輸入ai

•第i階段的「局部最優解」： ai

•貪心選擇性質：所求問題的全局最優解可以通過一系列局部最優的選擇（即貪心選擇）來達到。

–這是貪心演算法與動態規劃演算法的主要區別。

•最優子結構性質：當原問題的最優解包含子問題的最優解時，稱此問題具有最優子結構性質。

最優子結構性質是該問題可用動態規劃演算法或貪心演算法求解的關鍵特徵

•要求高效地安排一系列爭用某一公共資源（例如會議室）的活動（使盡可能多的活動能兼容使用公共資源）。

–設有n個活動的集合E={e1,e2…en}，其中每個活動都要求使用同一資源，而在同一時間內只有一個活動能使用這一資源。每個活動i都有一個要求使用該資源的起始時間si和一個結束時間fi，且si<fi。如果選擇了活動i，則它在半開時間區間[si,fi)內佔用資源。

–若區間[si,fi)與區間[sj,fj)不相交，則稱ei和ej是相容的。也就是說，當si≥fj或sj≥fi時，活動i和活動j相容。

•活動安排問題就是要在所給的活動集合中選出最大的相容活動子集合。

❸ 大學課程《演算法分析與設計》中動態規劃和貪心演算法的區別和聯系

對於，大學課程《演算法分析與設計》中動態規劃和貪心演算法的區別和聯系這個問題，首先要來聊聊他們的聯系：1、都是一種推導演算法；2、將它們分解為子問題求解，它們都需要有最優子結構。這兩個特徵師門的聯系。

拓展資料：

貪婪演算法是指在解決問題時，它總是在當前做出最佳選擇。也就是說，在不考慮全局優化的情況下，該演算法在某種意義上獲得了局部最優解。貪婪演算法不能得到所有問題的全局最優解。關鍵是貪婪策略的選擇。

動態規劃是運籌學的一個分支，是解決決策過程優化的過程。20世紀50年代初，美國數學家R·貝爾曼等人在研究多階段決策過程的最優化問題時，提出了著名的最優化原理，建立了動態規劃。動態規劃在工程技術、經濟、工業生產、軍事和自動控制等領域有著廣泛的應用，在背包問題、生產經營問題、資金管理問題、資源分配問題、最短路徑問題和復雜系統可靠性問題上都取得了顯著的成果。

❹ 分析用動態規劃和貪心演算法求解背包問題的差異

動態規劃本質是以空間換時間，算出了所有可行解的值域。

而貪心演算法，每次選則最優的，而結果未必最優。
舉個簡單例子。
背包能裝8kg,有3個物品，分別為3kg,4kg,5kg
動態規劃，是計算，3+4， 3+5，得出解，最大的是3+5=8kg
貪心演算法，是選擇，第一次選最大的：5kg<8kg，第二次選則剩下的最大的4kg，4+5>8,故而解為5kg。