- 相關(guān)推薦
用動態(tài)規(guī)劃法與回溯法實現(xiàn)0-1背包問題的比較
1背包問題0-1背包問題：給定n種物品和一背包。物品i的重量是Wi，其價值為Vi，背包的容量為C。問應(yīng)如何選擇裝入背包中物品，使得裝入背包中物品的總價值最大？
對于一個實例：物品種類N=4，背包容量C=10，物品重量數(shù)組W={3，5，2，1}，相應(yīng)價值數(shù)組V={9，10，7，4}。找一個n元0-1向量（x1，x2，x3….xn）xi∈{0,1},1≤i≤n.使得
，
達到最大。下面分別以動態(tài)規(guī)劃法和回溯法來解決這個實例。
2動態(tài)規(guī)劃法
動態(tài)規(guī)劃法的基本思想是將待求解問題分解成若干個子問題，先求解子問題，然后從這些子問題的解得到原問題的解。用一個表來保存記錄所有已解決的子問題的答案，在需要的時候再找出已求得的答案，避免重復(fù)的計算。
動態(tài)規(guī)劃法適用于解最優(yōu)化問題。通�？砂匆韵�4個步驟：
(1)找出最優(yōu)解的性質(zhì)并刻畫其結(jié)構(gòu)特征。
(2)遞歸的定義最優(yōu)解。
(3)以自底向上的方式計算出最優(yōu)值。
(4)根據(jù)計算最優(yōu)值時到得的信息，構(gòu)造最優(yōu)解。
對于所給0-1背包問題的子問題：
，
的最優(yōu)值為m（i，j），即m（i，j）是背包容量為j，可懸著物品為i,i+1,….,n時0-1背包問題的最優(yōu)值。由于0-1背包問題的最優(yōu)子結(jié)構(gòu)性質(zhì)，可以建立計算m（i，j）的如下遞歸式：
�。�1.1）
（1.2）
從上面算法的執(zhí)行過程中可以看出假設(shè)有Q（n）個子問題,每一個子問題最多需要m次決策,則計算的頻率為nm,回溯的頻率為n，那么整個過程的算法的時間復(fù)雜度為T（n）=nm+n，即為Q（nm）。
3回溯法。
回溯法在包含問題的所有解的解空間樹中,按照深度優(yōu)先的策略,從根結(jié)點出發(fā)搜索解空間樹�；厮菟惴ㄋ阉髦两饪臻g樹的任一結(jié)點時,總是先判斷該結(jié)點是否肯定不包含問題的解。如果肯定不包含,則跳過對以該結(jié)點為根的子樹的系統(tǒng)搜索,逐層向其祖先結(jié)點回溯。否則,進入該子樹,繼續(xù)按深度優(yōu)先的策略進行搜索。回溯法在用來求問題的所有解時,要回溯到根,且根結(jié)點的所有子樹都已被搜索遍才結(jié)束。簡單地說就是確定解空間,建立解空間樹,用深度優(yōu)先搜索算法遞歸搜索解空間樹,并同時注意剪枝。
用回溯法解題的步驟：
(1)針對所給問題定義問題的解空間；
(2)確定易于搜索的解空間結(jié)構(gòu)；
(3)以深度優(yōu)先方式搜索解空間,并在搜索過程中用剪枝函數(shù)避免無效的搜索。
根據(jù)上述0-1背包問題的數(shù)學(xué)描述解向量可以表示成X={X,X,...X|X=0或=1}若X=0,表示第i個物品不裝入背包，X=1，表示將第i個物品裝入背包。
可以用樹的形式將解空間表達出來。樹中從第i層到第i+1層的邊上的值表示解向量中X的取值，并假定第i層的左子樹描述第i個物品被裝入背包的情況，右子樹描述第i個物品被拒絕的情況。則該0-1背包問題的狀態(tài)空間樹就表示為一棵高度為n的完全二叉樹。若n=3時則此0-1背包問題的解空間的結(jié)構(gòu)如圖1-1所示。從根結(jié)點到葉子結(jié)點的任一路徑就對應(yīng)解空間中的一個解向量
圖1-1n=3時，0-1背包問題的解空間樹
用回溯法求解0-1背包問題時，可以按照物品的單位價值從大到小排序。計算當前節(jié)點的上界,搜索左子樹。只有當右子樹包含可行解時才搜索右子樹。剪去右子樹的條件是當前價值加上剩余物品的總價值小于當前的最優(yōu)總價值時,不需搜索右子樹,可將右子樹剪去�；厮莘ㄓ靡欢ǖ募糁M行優(yōu)化,算法的時間復(fù)雜度為O(n*2n),n為物品個數(shù)。
4總結(jié)
動態(tài)規(guī)劃算法：動態(tài)規(guī)劃可以把困難得多階段決策變換為一系列相互聯(lián)系比較容易的單階段問題。對于背包問題可以對子過程用枚舉法求解,而且約束條件越多,決策的搜索范圍越小,求解也越容易。但是對于規(guī)模較大的問題它并不是一個理想的算法。最重要的原因就是它的維數(shù)障礙。即計算和存儲量的需要對于狀態(tài)空間和決策空間的維數(shù)的增長呈指數(shù)增長關(guān)系，這樣驚人的增長速度是計算機難以承受的。這就使得直接的動態(tài)規(guī)劃方法求解規(guī)劃較大的背包問題發(fā)生了困難，且目前尚沒有好的解決辦法。
回溯法：回溯法需要為問題定義一個解空間,這個解空間必須至少包含問題的一個解(可能是最優(yōu)的)。使用遞歸回溯法解決背包問題的優(yōu)點在于它算法思想簡單,而且它能完全遍歷搜索空間,肯定能找到問題的最優(yōu)解。但是由于此問題解的總組合數(shù)有2個,因此,隨著物件數(shù)n的增大,其解的空間將以2級增長,當n大到一定程度上,用此算法解決背包問題將是不現(xiàn)實的。
用此兩種方法都能得到問題的最優(yōu)解，從其時間復(fù)雜度來看，兩者的速度都較慢。
【用動態(tài)規(guī)劃法與回溯法實現(xiàn)0-1背包問題的比較】相關(guān)文章：
比較的特殊表達法初探01-08
比較法楷書教學(xué)探索02-25
“聽說法”與“交際法”的比較及啟示08-17
比較法在物理中的應(yīng)用08-17
歐美產(chǎn)品責任法比較及啟示02-20
儒法之比較及其現(xiàn)代意義02-24
運用改換比較法培養(yǎng)語感08-17