貪心算法與動態(tài)規(guī)劃的比較

1、貪心算法與動態(tài)規(guī)劃的比較1=1【摘要】介紹了計算機算法設計的兩種常用算法思想：貪心算法與動態(tài)規(guī)劃算法。通過 介紹兩種算法思想的基本原理，比較兩種算法的聯(lián)系和區(qū)別。通過背包問題對比了兩種算法 的使用特點和使用范圍?！娟P鍵字】動態(tài)規(guī)劃；貪心算法；背包問題1、引言為了滿足人們對大數(shù)據(jù)量信息處理的渴望，為解決各種實際問題，計算機算法學得到了 飛速的發(fā)展，線性規(guī)劃、動態(tài)規(guī)劃、貪心策略等一系列運籌學模型紛紛運用到計算機算法學 中，產(chǎn)生了解決各種現(xiàn)實問題的有效算法。雖然設計一個好的求解算法更像是一門藝術而不 像是技術，但仍然存在一些行之有效的、能夠用于解決許多問題的算法設計方法，你可以使 用這些方法來設計算

2、法，并觀察這些算法是如何工作的。一般情況下，為了獲得較好的性能， 必須對算法進行細致的調整。但是在某些情況下，算法經(jīng)過調整之后性能仍無法達到要求， 這時就必須尋求另外的方法來求解該問題。本文針對部分背包問題和0/ 1背包問題進行分 析，介紹貪心算法和動態(tài)規(guī)劃算法的區(qū)別。2、背包問題的提出給定n種物品（每種物品僅有一件）和一個背包。物品i的重量是wi，其價值為p i， 背包的容量為M。問應如何選擇物品裝入背包，使得裝入背包中的物品的總價值最大每件 物品i的裝入情況為x廠得到的效益是p i*xi。部分背包問題在選擇物品時，可以將物品分割為部分裝入背包，即0 xi 1 （貪心 算法）。0/ 1背包問

3、題。和部分背包問題相似，但是在選擇物品裝入時要么不裝，要么全裝 入，即x i = 1或0。（動態(tài)規(guī)劃算法）。3、貪心算法3.1貪心算法的基本要素能夠使用貪心算法的許多例子都是最優(yōu)化問題，每個最優(yōu)化問題都包含一組限制條件和 一個優(yōu)化函數(shù)，符合限制條件的問題求解方案稱為可行解；使優(yōu)化函數(shù)取得最佳值的可行解 稱為最優(yōu)解。此類所求問題的整體最優(yōu)解可以通過一系列局部最優(yōu)的選擇，即貪心選擇來達 到（這是貪心算法與動態(tài)規(guī)劃的主要區(qū)別）。3.2貪心策略的定義貪心策略是指從問題的初始狀態(tài)出發(fā)，通過若干次的貪心選擇而得出最優(yōu)值（或較優(yōu)解） 的一種解題方法。貪心策略總是做出在當前看來是最優(yōu)的選擇，也就是說貪心策略并

4、不是從 整體上加以考慮，它所做出的選擇只是在某種意義上的局部最優(yōu)解，而許多問題自身的特性 決定了該問題運用貪心策略可以得到最優(yōu)解或較優(yōu)解。（注：貪心算法不是對所有問題都能 得到整體最優(yōu)解，但對范圍相當廣泛的許多問題它能產(chǎn)生整體最優(yōu)解。但其解必然是最優(yōu)解 的很好近似解。）采用自頂向下的、以迭代的方法做出相繼的貪心選擇，每做一次貪心選擇就將所求問題 簡化為一個規(guī)模更小的子問題。對于一個具體問題，要確定它是否具有貪心選擇的性質，我 們必須證明每一步所作的貪心選擇最終導致問題的最優(yōu)解。通常可以首先證明問題的一個整 體最優(yōu)解，是從貪心選擇開始的，而且作了貪心選擇后，原問題簡化為一個規(guī)模更小的類似 子問題

5、。然后用數(shù)學歸納法證明，通過每一步貪心選擇，最終可得到問題的一個整體最優(yōu)解。 3、3貪心算法的實際應用例子貪心法的基本思路。從問題的某一個初始解出發(fā)逐步逼近給定的目標，以盡可能快地求得更好的解。當達到 某算法中的某一步不能再繼續(xù)前進時，算法停止。該算法存在的問題。不能保證求得的最后解是最佳的；不能用來求最大或最小解問題；只能求滿足某些約束條件的可行解的范圍。實現(xiàn)該算法的過程。從問題的某一初始解出發(fā)；當能朝給定總目標前進一步時，求出可行解的一個解元素；由所有解元素組合成問題的一個可行解。背包問題分析實例（部分背包問題）。有一個背包，容量是M = 150，有7個物品，物 品可以分割成任意大小，要求

6、盡可能讓裝入背包中的物品總價值最大，但不能超過總容量。 其重量和價值如下。物品ABCDEFG重量35306050401025價值10403050354030其中目標函ZPg.最大。約束條件是裝入的物品總重量不超過背包容量：E W . M（M=150）根據(jù)貪心的策略，每次選取單位容量價值最大的物品，成為解本題的策略。可以證明得 到最優(yōu)解為x = 0，1，0，1，7/ 8，1，1總價值為：190. 6。3、4貪心算法不適于解0/ 1背包問題0/ 1背包問題有好幾種貪婪策略，每種貪婪策略都要多個步驟來完成，每一步都利用 貪婪準則選擇一個物品裝入背包。一種貪婪準則為：從剩余的物品中，選出可以裝入背包的

7、 價值最大的物品，利用這種規(guī)則，價值最大的物品首先被裝入（假設有足夠容量），然后是 下一個價值最大的物品，如此繼續(xù)下去。這種策略不能保證得到最優(yōu)解。例如，考慮n= 2, w = 100，10，10，p = 20，15，15，c = 105。當利用價值貪婪準則時，獲得的解為x = 1，0，0，這種方案的總價值為20。而最優(yōu)解為0，1，1，其總價值為30。另一種方 案是重量貪婪準則：從剩下的物品中選擇可裝入背包的重量最小的物品。雖然這種規(guī)則對 于前面的例子能產(chǎn)生最優(yōu)解，但在一般情況下則不一定能得到最優(yōu)解?？紤]n =2, w = 10， 20，p = 5, 100，c = 25。當利用重量貪婪策略時

8、，獲得的解為x = 1，0，比最優(yōu)解0， 1要差。還可以利用另一方案，價值密度pi / Wj貪婪算法，這種選擇準則為：從剩余物品 中選擇可裝入包的pi / wi值最大的物品，這種策略也不能保證得到最優(yōu)解。4、動態(tài)規(guī)劃4、1動態(tài)規(guī)劃的定義動態(tài)規(guī)劃是運籌學的一個分支，與其說它是一種算法，不如說它是一種思維方法更貼切。 因為動態(tài)規(guī)劃沒有固定的框架，即便是應用到同一道題上，也可以建立多種形式的求解算法。 許多隱式圖上的算法，例如求單源最短路徑的Dijkstra算法、廣度優(yōu)先搜索算法，都滲透著 動態(tài)規(guī)劃的思想。還有許多數(shù)學問題，表面上看起來與動態(tài)規(guī)劃風馬牛不相及，但是其求解 思想與動態(tài)規(guī)劃是完全一致的。

9、因此，動態(tài)規(guī)劃不像深度或廣度優(yōu)先那樣可以提供一套模式， 需要的時候，取來就可以使用。它必須對具體問題進行具體分析、處理，需要豐富的想象力 去建立模型，需要創(chuàng)造性的思想去求解。4、2動態(tài)規(guī)劃適于解決的問題適用動態(tài)規(guī)劃的問題必須滿足最優(yōu)化原理和無后效性。狀態(tài)必須滿足最優(yōu)化原理。作為整個過程的最優(yōu)策略具有如下性質：無論過去的狀態(tài) 和決策如何，對前面的決策所形成的當前狀態(tài)而言，余下的諸決策必須構成最優(yōu)策略。可以 通俗地理解為子問題的局部最優(yōu)將導致整個問題的全局最優(yōu)，即問題具有最優(yōu)子結構的性質， 也就是說一個問題的最優(yōu)解只取決于其子問題的最優(yōu)解，非最優(yōu)解對問題的求解沒有影響。狀態(tài)必須滿足無后效性。所謂無

10、后效性是指：過去的決策只能通過當前狀態(tài)影響未來 的發(fā)展，當前的狀態(tài)是對以往決策的總結。它說明動態(tài)規(guī)劃適于解決當前決策和過去狀態(tài)無 關的問題。狀態(tài)出現(xiàn)在策略的任何一個位置，它的地位都是相同的，都可以實施同樣的決策， 這就是無后效性的內涵。4、3動態(tài)規(guī)劃問題的特征動態(tài)規(guī)劃算法的有效性依賴于問題本身所具有的兩個重要性質:最優(yōu)子結構性質和子問 題重疊性質。最優(yōu)子結構。當問題的最優(yōu)解包含了其子問題的最優(yōu)解時，稱該問題具有最優(yōu)子結 構性質。重疊子問題。在用遞歸算法自頂向下解問題時，每次產(chǎn)生的子問題并不總是新問題， 有些子問題被反復計算多次。動態(tài)規(guī)劃算法正是利用了這種子問題的重疊性質，對每一個子 問題只解一

11、次，而后將其解保存在一個表格中，在以后盡可能多地利用這些子問題的解。4、4設計動態(tài)規(guī)劃法的步驟找出最優(yōu)解的性質，并刻畫其結構特征；遞歸地定義最優(yōu)值（寫出動態(tài)規(guī)劃方程）；以自底向上的方式計算出最優(yōu)值；根據(jù)計算最優(yōu)值時得到的信息，構造一個最優(yōu)解。步驟1- 3是動態(tài)規(guī)劃算法的基本步驟。在只需求出最優(yōu)值的情形下，步驟4可以省略， 步驟3中記錄的信息也較少；若需要求出問題的一個最優(yōu)解，則必須執(zhí)行步驟4,步驟3中 記錄的信息必須足夠多，以便構造最優(yōu)解。4、5動態(tài)規(guī)劃算法0/ 1背包問題在該問題中需要決定氣,七的值。假設按i=1，2，.，n的次 序來確定xi的值。如果置xi= 0，則問題轉變?yōu)橄鄬τ谄溆辔锲?/p>

12、（即物品2, 3, .，n）， 背包容量仍為c的背包問題。若置xi=1，問題就變?yōu)殛P于最大背包容量為c-wi的問題?，F(xiàn) 設r& Icirc； c-w1為剩余的背包容量。在第一次決策之后，剩下的問題便是考慮背包容量為 r時的決策。不管xi是0或是1，x2, .，xn必須是第一次決策之后的一個最優(yōu)方案， 如果不是，則會有一個更好的方案y2, .，y：，因而，y2, .，yn是一個更好的方 案。假設 n=3，w= 100，14，10，p= 20，18，15，c=116。若設 x1=1，則在本次決策 之后，可用的背包容量為r =116- 100= 16。 x2, x3= 0, 1符合容量限制的條件，所

13、得值為 15,但因為x2, x3 = 1, 0同樣符合容量條件且所得值為18,因此x2, x3 = 0, 1并 非最優(yōu)策略。即x= 1, 0, 1可改進為x = 1, 1, 0。若設x1=0，則對于剩下的兩種物品 而言，容量限制條件為116?？傊?，如果子問題的結果x2, x3不是剩余情況下的一個最優(yōu) 解，則x1，x2, x3也不會是總體的最優(yōu)解。5、小結和貪心算法一樣，在動態(tài)規(guī)劃中，可將一個問題的解決方案視為一系列決策的結果。不 同的是，在貪婪算法中，每用一次貪心準則便做出一個不可撤回的決策，而在動態(tài)規(guī)劃中， 還要考察每個最優(yōu)決策序列中是否包含一個最優(yōu)子序列。當一個問題具有最優(yōu)子結構時，我 們會想到用動態(tài)規(guī)劃法去解它，但是有些問題存在著更簡單、有效的方法，只要我們總是做 出當前看來最好的選擇就可以了。貪心算法所作的選擇可以依賴于以往所作過的選擇，但決 不依賴于將來的選擇，也不依賴于子問題的解，這使得算法在編碼和執(zhí)行的過程中都有著一 定的速度優(yōu)勢。如果一個問題可以同時用幾種方法解決，貪心算法應該是最好的選擇之一。 但是貪心算法并不是對所有的問題都能得到整體最優(yōu)解或最理想的近似解，與回溯法等比較， 它的適用區(qū)域