【算法分析】实验 4. 回溯法求解0-1背包等问题
目錄
- 實(shí)驗(yàn)內(nèi)容
- 實(shí)驗(yàn)?zāi)康?/li>
- 實(shí)驗(yàn)結(jié)果
- 步驟1：描述與分析
- 步驟2：策略以及數(shù)據(jù)結(jié)構(gòu)
- 步驟3
- 步驟4
- 步驟5
- 步驟6
- 實(shí)驗(yàn)總結(jié)
實(shí)驗(yàn)內(nèi)容
????本實(shí)驗(yàn)要求基于算法設(shè)計(jì)與分析的一般過(guò)程（即待求解問(wèn)題的描述、算法設(shè)計(jì)、算法描述、算法正確性證明、算法分析、算法實(shí)現(xiàn)與測(cè)試），通過(guò)回溯法的在實(shí)際問(wèn)題求解實(shí)踐中，加深理解其基本原理和思想以及求解步驟。求解的問(wèn)題為0-1背包。
作為挑戰(zhàn)：可以考慮回溯法在其他問(wèn)題（如最大團(tuán)問(wèn)題、旅行商、圖的m著色問(wèn)題）。
實(shí)驗(yàn)結(jié)果
步驟1：描述與分析
????給定n種物品和一個(gè)背包。物品\(i\)的重量是\(w_i\) ,其價(jià)值為\(v_i\),背包的容量為W。一種物品要不全部裝入背包，要不不裝入背包，不允許部分物品裝入的情況。裝入背包的物品的總重量不能超過(guò)背包的容量，在這種情況下，問(wèn)如何選擇轉(zhuǎn)入背包的物品，使得裝入背包的物品的總價(jià)值最大？需要采用回溯的方法進(jìn)行問(wèn)題的求解。
分析：
（1）問(wèn)題的解空間：
????將物品裝入背包，有且僅有兩個(gè)狀態(tài)。第\(i\)種物品對(duì)應(yīng)\((x_1,x_2,...,x_n)\),其中\(x_i\)可以取0或1，分別代表不放入背包和放入背包。解空間有\(2^n\)種可能解，也就是\(n\)個(gè)元素組成的集合的所有子集的個(gè)數(shù)。采用一顆滿(mǎn)二叉樹(shù)來(lái)講解空間組織起來(lái)，解空間樹(shù)的深度為問(wèn)題的規(guī)模\(n\)。
（2）約束條件：
\[ \sum_{i=1}^nw_ix_i \le W \]
（3）限界條件：
????0-1背包問(wèn)題的可行解不止一個(gè)，而目標(biāo)是找到總價(jià)值最大的可行解。因此需要設(shè)置限界條件來(lái)加速找出最優(yōu)解的速度。如果當(dāng)前是第t個(gè)物體，那么1-t物體的狀態(tài)都已經(jīng)被確定下來(lái)，剩下就是t+1~n物體的狀態(tài)，采用貪心算法計(jì)算當(dāng)前剩余物品所能產(chǎn)生的最大價(jià)值是否大于最優(yōu)解，如果小于最優(yōu)解，那么被剪枝掉。
步驟2：策略以及數(shù)據(jù)結(jié)構(gòu)
????采用回溯法進(jìn)行問(wèn)題的求解，也就是具有約束函數(shù)/限界條件的深度優(yōu)先搜索算法。
????采用回溯法特有框架：
回溯算法()如果到達(dá)邊界：記錄當(dāng)前的結(jié)果，進(jìn)行處理如果沒(méi)有到達(dá)邊界：如果滿(mǎn)足限界條件：（左子樹(shù)）進(jìn)行處理進(jìn)行下一層的遞歸求解將處理回退到處理之前如果不滿(mǎn)足限界條件：（右子樹(shù)）進(jìn)行下一層遞歸處理步驟3
????描述算法。希望采用源代碼以外的形式，如偽代碼或流程圖等；
偽代碼：
????遞歸式回溯算法：
BACKTRACK-REC(t) //t為擴(kuò)展結(jié)點(diǎn)在樹(shù)中所處的層次if t > n //已到葉子結(jié)點(diǎn)，輸出結(jié)果OUTPUT(x) //檢查擴(kuò)展結(jié)點(diǎn)的每個(gè)分支。s(n,t)與e(n,t)分別為當(dāng)前擴(kuò)展結(jié)點(diǎn)處未搜索過(guò)//的子樹(shù)的起始編號(hào)和終止編號(hào)else for i from s(n,t) to e(n,t)x[t] = h(i) // h[i]: 在當(dāng)前擴(kuò)展結(jié)點(diǎn)處 x[t]的第i個(gè)可選值if CONSTRAINT(t) && BOUND(t) //約束函數(shù)與限界函數(shù)BACKTRACK-REC(t+1) //進(jìn)入t+1層搜索????迭代式回溯算法：
BACKTRACK-ITE()t = 1 //t為擴(kuò)展結(jié)點(diǎn)在樹(shù)中所處的層次while t > 0:if s(n,t) <= e(n,t) for i from s(n,t) to e(n,t) do x[t] = h(i) //h[i]: 在當(dāng)前擴(kuò)展結(jié)點(diǎn)處x[t]的第i個(gè)可選值if CONSTRINT(t) && BOUND(t) //滿(mǎn)足約束限界條件if t > n //已到葉子結(jié)點(diǎn)，輸出結(jié)果OUTPUT(x);else t ++ //前進(jìn)到更深層搜索elset -- //回溯到上一層的活結(jié)點(diǎn)步驟4
????算法的正確性證明。需要這個(gè)環(huán)節(jié)，在理解的基礎(chǔ)上對(duì)算法的正確性給予證明
????回溯算法適用條件：多米諾性質(zhì)
????假設(shè)解向量是n維的，則下面的k滿(mǎn)足：\(0<k<n ，P(x_1,x_2,x_3,…,x_{k+1})\)為解的部分向量可以推得\(P(x_1,x_2,x_3,…,x_k)\)也為解的部分向量
????在0-1背包問(wèn)題中，解空間為：\((x_1,x_2,...,x_n)\), 如果當(dāng)前結(jié)果\(P_1 = (x_1,x_2,...,x_n)\)是最優(yōu)解，那么\(P_2=(x_1,x_2,...,x_{n-1})\)的時(shí)候，也就是減少一個(gè)物品但不改變背包容量的時(shí)候，可以想到\(P_2\)依然是該問(wèn)題的最優(yōu)解。從子集樹(shù)角度來(lái)看，也就是最后一層結(jié)點(diǎn)全部去掉后的結(jié)果，那么當(dāng)前結(jié)果也是最優(yōu)的。
步驟5
????算法復(fù)雜性分析，包括時(shí)間復(fù)雜性和空間復(fù)雜性；
算法的復(fù)雜性分析：
????時(shí)間復(fù)雜度：\[ T(n)=O(2^n)+O(n2^n)+O(nlog(n)) = O(n2^n)\]
????空間復(fù)雜度：\[O(nlog(n))\]
步驟6
????算法實(shí)現(xiàn)與測(cè)試。附上代碼或以附件的形式提交，同時(shí)貼上算法運(yùn)行結(jié)果截圖;
# -*- coding: utf-8 -*- """ Created on Mon Oct 22 08:49:13 2018 @author: pprp """ BV=0 # best value CW=0 # current weight CV=0 # current value BX=None # best x resultdef output(x):for i in x:print(" ",i,end="")print()class node(object):def __init__(self,v,w):self.v = vself.w = wself.per = float(v)/float(w)def Bound(t):print("bound:",t)LC = c-CW # left CB = BV # best value#sortnodes = []for i in range(n):nodes.append(node(v[i],w[i]))nodes.sort(key=lambda x:x.per,reverse=True)# 裝入背包while t < n and w[t] <= LC:LC -= w[t]B += v[t]t += 1if t < n:B += float(v[t])/float(w[t]) * LCreturn Bdef backtrack(t,n):"""當(dāng)前在第t層"""print("current:",t)global BV,CV,CW,x,BXif t >= n:if BV < CV:BV=CVBX=x[:]else:if CW+w[t] <= c: # 搜索左子樹(shù)，約束條件x[t]=TrueCW += w[t]CV += v[t]backtrack(t+1,n)CW -= w[t]CV -= v[t]if Bound(t) > BV: # 搜索右子樹(shù)x[t]=False backtrack(t+1,n)if __name__ == "__main__":n=10c=10x=[False for i in range(n)]w=[2,2,6,5,4,4,3,4,6,3]v=[6,3,5,4,6,2,8,3,1,7]backtrack(0,n)print("Best Value :",BV)print("Best Choice:",BX)運(yùn)行結(jié)果：
驗(yàn)證：6+3+8+7=24
實(shí)驗(yàn)總結(jié)
回溯法的思想：
????能進(jìn)則進(jìn)，不進(jìn)則換，不換則退.
回溯算法的框架：
????以DFS的方式進(jìn)行搜索，在搜索的過(guò)程中用剪枝條件（限界函數(shù)）避免無(wú)效搜索。約束函數(shù)，在擴(kuò)展結(jié)點(diǎn)處剪去得不到可行解的子樹(shù)；限界函數(shù)：在擴(kuò)展結(jié)點(diǎn)處剪去得不到最優(yōu)解的子樹(shù)。
回溯算法求解問(wèn)題的一般步驟：
1、 針對(duì)所給問(wèn)題，定義問(wèn)題的解空間，它至少包含問(wèn)題的一個(gè)（最優(yōu)）解。
2 、確定易于搜索的解空間結(jié)構(gòu),使得能用回溯法方便地搜索整個(gè)解空間 。
3 、以深度優(yōu)先的方式搜索解空間，并且在搜索過(guò)程中用剪枝函數(shù)避免無(wú)效搜索。
常用剪枝函數(shù)：
????用約束函數(shù)在擴(kuò)展結(jié)點(diǎn)處剪去不滿(mǎn)足約束的子樹(shù)；
????用限界函數(shù)剪去得不到最優(yōu)解的子樹(shù)。
子集樹(shù)、滿(mǎn)m叉樹(shù)、排列樹(shù)區(qū)別：
????子集樹(shù)：從n個(gè)元素的集合S中找到滿(mǎn)足某種性質(zhì)的子集時(shí)，相應(yīng)的解空間樹(shù)就成為了子集樹(shù)（典型問(wèn)題：01背包問(wèn)題）
????滿(mǎn)m叉樹(shù)：所給問(wèn)題中每一個(gè)元素均有m中選擇，要求確定其中的一種選擇，使得對(duì)這n個(gè)元素的選擇結(jié)果組成的向量滿(mǎn)足某種性質(zhì)（經(jīng)典問(wèn)題：圖的m著色問(wèn)題）
????排列樹(shù)：從n個(gè)元素的排列樹(shù)中找出滿(mǎn)足某種性質(zhì)的一個(gè)排列的時(shí)候，相應(yīng)的解空間樹(shù)稱(chēng)為排列樹(shù)（經(jīng)典問(wèn)題：TSP問(wèn)題，n皇后問(wèn)題）
轉(zhuǎn)載于:https://www.cnblogs.com/pprp/p/9880073.html
總結(jié)
以上是生活随笔為你收集整理的【算法分析】实验 4. 回溯法求解0-1背包等问题的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。
- 上一篇： 1837Balance
- 下一篇： PDO的使用