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