(36)-2018算法8回溯法算法分析與設(shè)計(jì)

1算法設(shè)計(jì)與分析第八章回溯算法重點(diǎn)回溯法的基本思想使用回溯法設(shè)計(jì)分析算法難點(diǎn)回溯法的框架子集樹、排列樹回溯法的性質(zhì)最優(yōu)子結(jié)構(gòu)性質(zhì)、貪心選擇性質(zhì)2第八章回溯算法第八章回溯算法3描述回溯法是一種選優(yōu)搜索法，按選優(yōu)條件向前搜索，以達(dá)到目標(biāo)。但是，當(dāng)探索到某一步時(shí)，發(fā)現(xiàn)原先選擇并不優(yōu)或達(dá)不到目標(biāo)，就退回一步重新選擇，這種走不通就退回再走的技術(shù)，稱為回溯法。第八章回溯算法4原理回溯法在問題的解空間樹中，按深度優(yōu)先策略，從根結(jié)點(diǎn)出發(fā)搜索解空間樹。算法搜索至解空間樹的任意一點(diǎn)時(shí)，先判斷該結(jié)點(diǎn)是否包含問題的解：若肯定不包含問題的解，則跳過對該結(jié)點(diǎn)為根的子樹的搜索，逐層向其祖先結(jié)點(diǎn)回溯否則，進(jìn)入該子樹，繼續(xù)按深度優(yōu)先策略搜索。第八章回溯算法5基本做法回溯法的基本做法是搜索，是一種組織得井井有條的，能避免不必要搜索的窮舉式搜索法。回溯法適用于解一些組合數(shù)相當(dāng)大的問題。有許多問題，當(dāng)需要找出它的解集或者要求回答什么解是滿足某些約束條件的最佳解時(shí)，往往要使用回溯法。68.1

裝載問題8.2

旅行商問題8.3基本特征第八章回溯算法8.1裝載問題7裝載問題：有n個集裝箱要裝上2艘載重量分別為C1和C2的輪船。其中，第i個集裝箱的重量為wi，且

∑in

wi≤C1+C2。要求確定一個合理的裝載方案，可將集裝箱裝上這2艘輪船例如：當(dāng)n=3，C1=C2=50，如果w=[10,40,40]時(shí)，則可以將集裝箱1和2裝到第1艘輪船上，而將集裝箱3裝到第2艘輪船上；如果w=[20,40,40]，則無法將這3個集裝箱都裝上輪船。8.1裝載問題8例如：當(dāng)n=3，C1=C2=50，w=[10,40,40]時(shí)，則可以將集裝箱1和2裝到第1艘輪船上，而將集裝箱3裝到第2艘輪船上?；舅悸罚喝绻b載問題有解，則采用下面的最優(yōu)裝載策略：(1)首先將第1艘輪船盡可能裝滿；(2)然后，將剩余的集裝箱，裝上第2艘輪船。將第1艘輪船盡可能裝滿，等價(jià)于選取全體集裝箱的一個子集，使該子集中集裝箱重量之和最接近C1

。裝載問題：將n個集裝箱(w1,…,wn)裝上2艘載重為C1和C2的輪船，且

∑in

wi≤C1+C2。要求確定一個合理的裝載方案。第八章回溯算法9裝載問題的解空間可用完全二叉樹表示解向量希望問題的解能夠表示成一個n元式(x1,x2,…,xn)的形式。解空間對于問題的一個實(shí)例，滿足顯式約束條件的所有解向量，構(gòu)成了該實(shí)例的一個解空間。第八章回溯算法10解向量希望問題的解能夠表示成一個n元式(x1,x2,…,xn)的形式。解空間對于問題的一個實(shí)例，滿足顯式約束條件的所有解向量，構(gòu)成了該實(shí)例的一個解空間。顯約束對分量xi

的取值限定。隱約束為滿足問題的解而對不同分量之間施加的約束。求解一個或全部解-搜索問題求解一個或全部最優(yōu)解-優(yōu)化問題例:裝載問題xi={0,1}n=3時(shí)解空間23{(0,0,0),(0,1,0),(0,0,1),(1,0,0),(0,1,1),(1,0,1),(1,1,0),(1,1,1)}組織成樹或圖:根到葉的路徑對應(yīng)解空間的元素ABCDEFGHIKKLMNO11010010110010注意：同一個問題可以有多種表示，有些表示方法更簡單，所需表示的狀態(tài)空間更?。ù鎯α可伲阉鞣椒ê唵危?。第八章回溯算法-問題狀態(tài)生成12擴(kuò)展結(jié)點(diǎn)：正在產(chǎn)生兒子的結(jié)點(diǎn)活結(jié)點(diǎn)：自身已生成，但其兒子還沒有全部生成的結(jié)點(diǎn)死結(jié)點(diǎn)：所有兒子已經(jīng)產(chǎn)生的結(jié)點(diǎn)問題狀態(tài)生成深度優(yōu)先生成法寬度優(yōu)先生成法第八章回溯算法-問題狀態(tài)生成13深度優(yōu)先生成法擴(kuò)展結(jié)點(diǎn)1，一旦產(chǎn)生了它的一個兒子2，就把結(jié)點(diǎn)2當(dāng)做新的擴(kuò)展結(jié)點(diǎn)。在完成以2為根的子樹的窮盡搜索之后，將結(jié)點(diǎn)1重新變成擴(kuò)展結(jié)點(diǎn)，繼續(xù)產(chǎn)生結(jié)點(diǎn)1的下一個兒子寬度優(yōu)先生成法在一個擴(kuò)展結(jié)點(diǎn)變成死結(jié)點(diǎn)之前，它一直是擴(kuò)展結(jié)點(diǎn)第八章回溯算法-問題狀態(tài)生成14生成問題狀態(tài)方法：深度優(yōu)先、寬度優(yōu)先回溯法為避免生成那些不可能產(chǎn)生最佳解的問題狀態(tài)，要不斷地利用限界函數(shù)來處死那些實(shí)際上不可能產(chǎn)生所需解的活結(jié)點(diǎn)，以減少問題的計(jì)算量。具有剪枝函數(shù)的深度優(yōu)先生成法稱為回溯法8.1裝載問題15算法設(shè)計(jì)可行性約束函數(shù)在解空間樹的j+1層的結(jié)點(diǎn)z處，當(dāng)前載重量Cw=∑in

wixi

當(dāng)Cw>C1時(shí)，以結(jié)點(diǎn)z為根的子樹中，所有結(jié)點(diǎn)都不滿足約束條件，因而該子樹中的解均為不可行解，故可將其剪去。該約束函數(shù)可以去除不可行解，得到所有可行解。因此，剪去不滿足約束條件的子樹的函數(shù)，稱為可行性約束函數(shù)裝載問題：將n個集裝箱(w1,…,wn)裝上2艘載重為C1和C2的輪船，且

∑in

wi≤C1+C2。要求確定一個合理的裝載方案。8.1裝載問題16算法設(shè)計(jì)可行性約束函數(shù)裝載問題：將n個集裝箱(w1,…,wn)裝上2艘載重為C1和C2的輪船，且

∑in

wi≤C1+C2。要求確定一個合理的裝載方案。上界函數(shù)當(dāng)前擴(kuò)展結(jié)點(diǎn)z:Cw

是當(dāng)前載重量；bestw是當(dāng)前最優(yōu)載重量；r是剩余集裝箱的重量上界函數(shù)為Cw+r

：在以當(dāng)前擴(kuò)展結(jié)點(diǎn)z為根的子樹中，任一葉結(jié)點(diǎn)所相應(yīng)的載重量均不超過Cw+r。因此，當(dāng)Cw+r

≤bestw

時(shí)，可將z的右子樹剪去。8.1裝載問題17算法設(shè)計(jì)可行性約束函數(shù)剪去不滿足約束條件的子樹。裝載問題：將n個集裝箱(w1,…,wn)裝上2艘載重為C1和C2的輪船，且

∑in

wi≤C1+C2。要求確定一個合理的裝載方案。上界函數(shù)剪去不含最優(yōu)解的子樹，改進(jìn)算法效率。8.1裝載問題18剪枝函數(shù)可行性約束函數(shù)：∑in

wi≤50上界函數(shù)：當(dāng)前載重量Cw+剩余集裝箱的重量r

當(dāng)前最優(yōu)載重量bestw19Cw0W110W240W3408.1裝載問題剪枝函數(shù)可行性約束函數(shù)：∑in

wi≤50上界函數(shù)：當(dāng)前載重量Cw+剩余集裝箱的重量r

當(dāng)前最優(yōu)載重量bestw解空間：子集樹20Cw0Cw1018.1裝載問題W110W240W340剪枝函數(shù)可行性約束函數(shù)：∑in

wi≤50上界函數(shù)：當(dāng)前載重量Cw+剩余集裝箱的重量r

當(dāng)前最優(yōu)載重量bestw解空間：子集樹21Cw0Cw10Cw50118.1裝載問題W110W240W340剪枝函數(shù)可行性約束函數(shù)：∑in

wi≤50上界函數(shù)：當(dāng)前載重量Cw+剩余集裝箱的重量r

當(dāng)前最優(yōu)載重量bestw解空間：子集樹22Cw0Cw10Cw50Cw901118.1裝載問題W110W240W340剪枝函數(shù)可行性約束函數(shù)：∑in

wi≤50上界函數(shù)：當(dāng)前載重量Cw+剩余集裝箱的重量r

當(dāng)前最優(yōu)載重量bestw解空間：子集樹23Cw0Cw10Cw50Cw90111可行性8.1裝載問題W110W240W340剪枝函數(shù)可行性約束函數(shù)：∑in

wi≤50在擴(kuò)展節(jié)點(diǎn)出剪去不滿足約束的子樹上界函數(shù)：當(dāng)前載重量Cw+剩余集裝箱的重量r

當(dāng)前最優(yōu)載重量bestw解空間：子集樹24Cw0Cw10Cw50Cw901118.1裝載問題W110W240W340剪枝函數(shù)可行性約束函數(shù)：∑in

wi≤50上界函數(shù)：當(dāng)前載重量Cw+剩余集裝箱的重量r

當(dāng)前最優(yōu)載重量bestw解空間：子集樹25Cw0Cw10Cw50Cw90Cw501108.1裝載問題W110W240W340剪枝函數(shù)可行性約束函數(shù)：∑in

wi≤50上界函數(shù)：當(dāng)前載重量Cw+剩余集裝箱的重量r

當(dāng)前最優(yōu)載重量bestw解空間：子集樹可行解26Cw0Cw10Cw50Cw90Cw501108.1裝載問題W110W240W340剪枝函數(shù)可行性約束函數(shù)：∑in

wi≤50上界函數(shù)：當(dāng)前載重量Cw+剩余集裝箱的重量r

當(dāng)前最優(yōu)載重量bestw解空間：子集樹可行解27Cw0Cw10Cw50Cw90Cw501108.1裝載問題W110W240W340剪枝函數(shù)可行性約束函數(shù)：∑in

wi≤50上界函數(shù)：當(dāng)前載重量Cw+剩余集裝箱的重量r

當(dāng)前最優(yōu)載重量bestw解空間：子集樹可行解28Cw0Cw10Cw50Cw10Cw90Cw5011008.1裝載問題W110W240W340剪枝函數(shù)可行性約束函數(shù)：∑in

wi≤50上界函數(shù)：當(dāng)前載重量Cw+剩余集裝箱的重量r

當(dāng)前最優(yōu)載重量bestw解空間：子集樹可行解29Cw0Cw10Cw50Cw10Cw90Cw50Cw50111008.1裝載問題W110W240W340剪枝函數(shù)可行性約束函數(shù)：∑in

wi≤50上界函數(shù)：當(dāng)前載重量Cw+剩余集裝箱的重量r

當(dāng)前最優(yōu)載重量bestw解空間：子集樹可行解可行解30Cw0Cw10Cw50Cw10Cw90Cw50Cw50Cw101110008.1裝載問題W110W240W340剪枝函數(shù)可行性約束函數(shù)：∑in

wi≤50上界函數(shù)：當(dāng)前載重量Cw+剩余集裝箱的重量r

當(dāng)前最優(yōu)載重量bestw解空間：子集樹可行解可行解31Cw0Cw10Cw50Cw10Cw90Cw50Cw50Cw101110008.1裝載問題W110W240W340剪枝函數(shù)可行性約束函數(shù)：∑in

wi≤50上界函數(shù)：當(dāng)前載重量Cw+剩余集裝箱的重量r

當(dāng)前最優(yōu)載重量bestw解空間：子集樹可行解可行解328.1裝載問題W110W240W340剪枝函數(shù)可行性約束函數(shù)：∑in

wi≤50上界函數(shù)：當(dāng)前載重量Cw+剩余集裝箱的重量r

當(dāng)前最優(yōu)載重量bestw解空間：子集樹Cw0Cw10Cw50Cw10Cw90Cw50Cw50Cw10111000上界可行解可行解33Cw0Cw10Cw50Cw10Cw90Cw50Cw50Cw10111008.1裝載問題W110W240W340剪枝函數(shù)可行性約束函數(shù)：∑in

wi≤50上界函數(shù)：當(dāng)前載重量Cw+剩余集裝箱的重量r

當(dāng)前最優(yōu)載重量bestw解空間：子集樹可行解可行解34Cw0Cw10Cw50Cw10Cw90Cw50Cw50Cw10111008.1裝載問題W110W240W340剪枝函數(shù)可行性約束函數(shù)：∑in

wi≤50上界函數(shù)：當(dāng)前載重量Cw+剩余集裝箱的重量r

當(dāng)前最優(yōu)載重量bestw解空間：子集樹可行解可行解35Cw0Cw10Cw50Cw10Cw90Cw50Cw50Cw10111008.1裝載問題W110W240W340剪枝函數(shù)可行性約束函數(shù)：∑in

wi≤50上界函數(shù)：當(dāng)前載重量Cw+剩余集裝箱的重量r

當(dāng)前最優(yōu)載重量bestw解空間：子集樹可行解可行解36Cw0Cw10Cw0Cw50Cw10Cw90Cw50Cw50Cw101110008.1裝載問題W110W240W340剪枝函數(shù)可行性約束函數(shù)：∑in

wi≤50上界函數(shù)：當(dāng)前載重量Cw+剩余集裝箱的重量r

當(dāng)前最優(yōu)載重量bestw解空間：子集樹可行解可行解37Cw0Cw10Cw0Cw50Cw10Cw40Cw90Cw50Cw50Cw1011110008.1裝載問題W110W240W340剪枝函數(shù)可行性約束函數(shù)：∑in

wi≤50上界函數(shù)：當(dāng)前載重量Cw+剩余集裝箱的重量r

當(dāng)前最優(yōu)載重量bestw解空間：子集樹可行解可行解38Cw0Cw10Cw0Cw50Cw10Cw40Cw90Cw50Cw50Cw10Cw80111110008.1裝載問題W110W240W340剪枝函數(shù)可行性約束函數(shù)：∑in

wi≤50上界函數(shù)：當(dāng)前載重量Cw+剩余集裝箱的重量r

當(dāng)前最優(yōu)載重量bestw解空間：子集樹可行解可行解39Cw0Cw10Cw0Cw50Cw10Cw40Cw90Cw50Cw50Cw10Cw8011111000可行性8.1裝載問題W110W240W340剪枝函數(shù)可行性約束函數(shù)：∑in

wi≤50上界函數(shù)：當(dāng)前載重量Cw+剩余集裝箱的重量r

當(dāng)前最優(yōu)載重量bestw解空間：子集樹可行解可行解40Cw0Cw10Cw0Cw50Cw10Cw40Cw90Cw50Cw50Cw10Cw4011110000Cw808.1裝載問題W110W240W340剪枝函數(shù)可行性約束函數(shù)：∑in

wi≤50上界函數(shù)：當(dāng)前載重量Cw+剩余集裝箱的重量r

當(dāng)前最優(yōu)載重量bestw解空間：子集樹可行解可行解41Cw0Cw10Cw0Cw50Cw10Cw40Cw90Cw50Cw50Cw10Cw4011110000上界Cw808.1裝載問題W110W240W340剪枝函數(shù)可行性約束函數(shù)：∑in

wi≤50上界函數(shù)：當(dāng)前載重量Cw+剩余集裝箱的重量r

當(dāng)前最優(yōu)載重量bestw解空間：子集樹可行解可行解42Cw0Cw10Cw0Cw50Cw10Cw40Cw90Cw50Cw50Cw10Cw401111000Cw808.1裝載問題W110W240W340剪枝函數(shù)可行性約束函數(shù)：∑in

wi≤50上界函數(shù)：當(dāng)前載重量Cw+剩余集裝箱的重量r

當(dāng)前最優(yōu)載重量bestw解空間：子集樹可行解可行解43Cw0Cw10Cw0Cw50Cw10Cw40Cw90Cw50Cw50Cw10Cw401111000Cw808.1裝載問題W110W240W340剪枝函數(shù)可行性約束函數(shù)：∑in

wi≤50上界函數(shù)：當(dāng)前載重量Cw+剩余集裝箱的重量r

當(dāng)前最優(yōu)載重量bestw解空間：子集樹可行解可行解44Cw0Cw10Cw0Cw50Cw10Cw40Cw0Cw90Cw50Cw50Cw10Cw4011110000Cw808.1裝載問題W110W240W340剪枝函數(shù)可行性約束函數(shù)：∑in

wi≤50上界函數(shù)：當(dāng)前載重量Cw+剩余集裝箱的重量r

當(dāng)前最優(yōu)載重量bestw解空間：子集樹可行解可行解45Cw0Cw10Cw0Cw50Cw10Cw40Cw0Cw90Cw50Cw50Cw10Cw4011110000Cw80上界8.1裝載問題W110W240W340剪枝函數(shù)可行性約束函數(shù)：∑in

wi≤50上界函數(shù)：當(dāng)前載重量Cw+剩余集裝箱的重量r

當(dāng)前最優(yōu)載重量bestw解空間：子集樹可行解可行解46Cw0Cw10Cw0Cw50Cw10Cw40Cw90Cw50Cw50Cw10Cw401111000Cw80Cw08.1裝載問題W110W240W340剪枝函數(shù)可行性約束函數(shù)：∑in

wi≤50上界函數(shù)：當(dāng)前載重量Cw+剩余集裝箱的重量r

當(dāng)前最優(yōu)載重量bestw解空間：子集樹可行解可行解478.1裝載問題剪枝函數(shù)可行性約束函數(shù)：∑in

wi≤50上界函數(shù)：當(dāng)前載重量Cw+剩余集裝箱的重量r

當(dāng)前最優(yōu)載重量bestwCw0Cw10Cw0Cw50Cw10Cw40Cw90Cw50Cw50Cw10Cw401111000Cw80Cw0W110W240W340解空間：子集樹可行解可行解488.1裝載問題剪枝函數(shù)可行性約束函數(shù)：∑in

wi≤50在擴(kuò)展節(jié)點(diǎn)出剪去不滿足約束的子樹上界函數(shù)：當(dāng)前載重量Cw+剩余集裝箱的重量r

當(dāng)前最優(yōu)載重量bestwvoidbacktrack(inti){//搜索第i層結(jié)點(diǎn)

if(i>n)//到達(dá)葉結(jié)點(diǎn),更新最優(yōu)解，并返回r-=w[i];

if(cw+w[i]<=c){//搜索左子樹

x[i]=1; cw+=w[i];

backtrack(i+1); cw-=w[i];}

if(cw+r>bestw){//搜索右子樹 x[i]=0; backtrack(i+1);}r+=w[i];}可行性約束函數(shù)：進(jìn)入左子樹時(shí)檢查只要左兒子是—個可行結(jié)點(diǎn)。搜索就進(jìn)入左子樹。由于可行結(jié)點(diǎn)的右兒子結(jié)點(diǎn)總是可行的，故進(jìn)入右子樹時(shí)不需檢查可行性。限界函數(shù)：剪去不能得到最優(yōu)解的子樹進(jìn)入右子樹時(shí)檢查右子樹可能包含最優(yōu)解時(shí)才進(jìn)入搜索。否則剪去。498.1

裝載問題8.2

旅行商問題8.3

基本特征第八章回溯算法8.2

旅行商問題501234301020645旅行商問題旅行商要到若干城市去賣貨，已知各城市之間的路程，他要選定一條從進(jìn)貨城市(1)出發(fā)，走遍每個城市(2)、(3)、(4)，最后，再回到進(jìn)貨城市(1)的路線，使總的路程最小。8.2

旅行商問題51問題分析用無向帶權(quán)圖表示旅行商問題城市間的路線長度，為圖中邊的權(quán)重。旅行商的一條賣貨路線，為包括圖中每個頂點(diǎn)在內(nèi)的一條回路。1234301020645問題：旅行商要選一條從進(jìn)貨城市X1

出發(fā)，走遍所有城市(X2,X3,X4)，再回到進(jìn)貨城市的最短路線。賣貨路程，為這條路線上所有邊的權(quán)重之和。旅行商問題，需要在帶權(quán)圖中，找出最短的賣貨路線。8.2

旅行商問題52求解---窮舉法列舉所有城市間的排列組合，選取路程最短的路線。12343010206451->2->3->4=551->2->4->3=601->3->2->4=211->3->4->2=36………………問題：旅行商要選一條從進(jìn)貨城市X1

出發(fā)，走遍所有城市(X2,X3,X4)，再回到進(jìn)貨城市的最短路線。8.2

旅行商問題531234301020645時(shí)間復(fù)雜度為O(N!)右圖給出了N個城市的路線數(shù)目計(jì)算機(jī)107/秒，若有20個城市，計(jì)算時(shí)間約為7700年窮舉法的時(shí)間復(fù)雜度太高問題：旅行商要選一條從進(jìn)貨城市X1

出發(fā)，走遍所有城市(X2,X3,X4)，再回到進(jìn)貨城市的最短路線。求解---窮舉法8.2

旅行商問題54問題的解空間旅行商問題的所有解，可以組織成一棵樹，包含了所有城市的排列組合。樹的根結(jié)點(diǎn)到任一葉結(jié)點(diǎn)的路徑，定義了圖的一條周游路線。{1,2,3,4}路程5923036441335440211426214324455159………………問題：旅行商要選一條從進(jìn)貨城市X1

出發(fā)，走遍所有城市(X2,X3,X4)，再回到進(jìn)貨城市的最短路線。解空間：排列樹8.2

旅行商問題55問題的解空間旅行商路線，即根節(jié)點(diǎn)到葉節(jié)點(diǎn)的搜索路徑。窮舉法：根據(jù)所有路線生成完全樹(4!)缺點(diǎn)：樹太大解決策略：邊生成樹，邊修剪樹如何剪枝？問題：旅行商要選一條從進(jìn)貨城市X1

出發(fā)，走遍所有城市(X2,X3,X4)，再回到進(jìn)貨城市的最短路線。{1,2,3,4}路程5923036441335440211426214324455159………………解空間：排列樹8.2

旅行商問題56問題求解---回溯法解決策略：邊生成樹，邊修剪樹如何剪枝？兩結(jié)點(diǎn)間，沒有邊當(dāng)前路程>

已記錄的最小路程bestc解空間：排列樹問題：旅行商要選一條從進(jìn)貨城市X1

出發(fā)，走遍所有城市(X2,X3,X4)，再回到進(jìn)貨城市的最短路線。{1,2,3,4}路程5923036441335440211426214324455159………………8.2

旅行商問題57問題求解---回溯法t=n排列樹搜索到第n層當(dāng)前擴(kuò)展節(jié)點(diǎn)x[n]，即為葉節(jié)點(diǎn)的父節(jié)點(diǎn)剪枝函數(shù)兩結(jié)點(diǎn)間，沒有邊當(dāng)前路程>已記錄最小路程bestc{1,2,3,4}路程5923036441335440211426214324455159………………t=1t=2t=3t=4問題：旅行商要選一條從進(jìn)貨城市X1

出發(fā)，走遍所有城市(X2,X3,X4)，再回到進(jìn)貨城市的最短路線。8.2

旅行商問題58問題求解---回溯法t=n檢查排列樹中是否存在邊?x[n-1]→x[n]、x[n]→x[1]剪枝函數(shù)兩結(jié)點(diǎn)間，沒有邊當(dāng)前路程>已記錄最小路程bestc{1,2,3,4}路程5923036441335440211426214324455159………………t=1t=2t=3t=4問題：旅行商要選一條從進(jìn)貨城市X1

出發(fā)，走遍所有城市(X2,X3,X4)，再回到進(jìn)貨城市的最短路線。8.2

旅行商問題59問題求解---回溯法t=n如果都存在，則找到一條售貨回路判斷

這個路程是否小與已找到的、當(dāng)前最小路程bestc如果是，更新最小路程bestc和最優(yōu)解bestx剪枝函數(shù)兩結(jié)點(diǎn)間，沒有邊當(dāng)前路程>已記錄最小路程bestc{1,2,3,4}路程5923036441335440211426214324455159………………t=1t=2t=3t=4問題：旅行商要選一條從進(jìn)貨城市X1

出發(fā)，走遍所有城市(X2,X3,X4)，再回到進(jìn)貨城市的最短路線。8.2

旅行商問題60問題求解---回溯法剪枝函數(shù)兩結(jié)點(diǎn)間，沒有邊當(dāng)前路程>已記錄最小路程bestc{1,2,3,4}路程5923036441335440211426214324455159………………t=1t=2t=3t=4問題：旅行商要選一條從進(jìn)貨城市X1

出發(fā)，走遍所有城市(X2,X3,X4)，再回到進(jìn)貨城市的最短路線。t=n，排列樹搜索到第n層，當(dāng)前擴(kuò)展節(jié)點(diǎn)x[n]t<

n，排列樹搜索到第t層，當(dāng)前擴(kuò)展節(jié)點(diǎn)x[t]排列樹已全部遍歷，算法終止8.2

旅行商問題61template<classType>voidTraveling<Type>::Backtrack(inti){if(i==n){if(a[x[n-1]][x[n]]!=NoEdge&&a[x[n]][1]!=NoEdge&&(cc+a[x[n-1]][x[n]]+a[x[n]][1]<bestc||bestc==NoEdge)){for(intj=1;j<=n;j++) bestx[j]=x[j]; bestc=cc+a[x[n-1]][x[n]]+a[x[n]][1];}}else{

}}t=n，排列樹搜索到第n層問題：旅行商要選一條從進(jìn)貨城市X1

出發(fā)，走遍所有城市(X2,X3,X4)，再回到進(jìn)貨城市的最短路線。8.2

旅行商問題62template<classType>voidTraveling<Type>::Backtrack(inti){if(i==n){if(a[x[n-1]][x[n]]!=NoEdge&&a[x[n]][1]!=NoEdge&&(cc+a[x[n-1]][x[n]]+a[x[n]][1]<bestc||bestc==NoEdge)){for(intj=1;j<=n;j++) bestx[j]=x[j]; bestc=cc+a[x[n-1]][x[n]]+a[x[n]][1];}}else{for(intj=i;j<=n;j++) if(a[x[i-1]][x[j]]!=NoEdge&&(cc+a[x[i-1]][x[i]]<bestc||bestc==NoEdge)){

//搜索子樹

Swap(x[i],x[j]);cc+=a[x[i-1]][x[i]];Backtrack(i+1);cc-=a[x[i-1]][x[i]];Swap(x[i],x[j]);}}}t<n，排列樹搜索到第t層問題：旅行商要選一條從進(jìn)貨城市X1

出發(fā)，走遍所有城市(X2,X3,X4)，再回到進(jìn)貨城市的最短路線。t=n，排列樹搜索到第n層8.2

旅行商問題63template<classType>voidTraveling<Type>::Backtrack(inti){if(i==n){if(a[x[n-1]][x[n]]!=NoEdge&&a[x[n]][1]!=NoEdge&&(cc+a[x[n-1]][x[n]]+a[x[n]][1]<bestc||bestc==NoEdge)){for(intj=1;j<=n;j++) bestx[j]=x[j]; bestc=cc+a[x[n-1]][x[n]]+a[x[n]][1];}}else{for(intj=i;j<=n;j++) if(a[x[i-1]][x[j]]!=NoEdge&&(cc+a[x[i-1]][x[i]]<bestc||bestc==NoEdge)){

//搜索子樹

Swap(x[i],x[j]);cc+=a[x[i-1]][x[i]];Backtrack(i+1);cc-=a[x[i-1]][x[i]];Swap(x[i],x[j]);}}}t<n，排列樹搜索到第t層復(fù)雜度分析最壞情況：更新當(dāng)前最優(yōu)解需(n-1)!次，每次更新bestx需n

次。整個算法的計(jì)算時(shí)間復(fù)雜性為O(n!)

問題：旅行商要選一條從進(jìn)貨城市X1

出發(fā)，走遍所有城市(X2,X3,X4)，再回到進(jìn)貨城市的最短路線。t=n，排列樹搜索到第n層思考旅行商問題的限界函數(shù)如何改進(jìn)？64658.1

裝載問題8.2

旅行商問題8.3基本特征第八章回溯算法8.3基本特征66解題步驟定義問題的解空間；顯著特征在搜索過程中，動態(tài)產(chǎn)生問題的解空間。------解題步驟8.3基本特征67解題步驟定義問題的解空間；確定易于搜索的解空間結(jié)構(gòu)：子集樹、排列數(shù)旅行商問題：排列樹{1,2,3,4}路程5923036441335440211426214324455159………………裝載問題：子集樹------解題步驟8.3基本特征68解題步驟定義問題的解空間；確定易于搜索的解空間結(jié)構(gòu)：子集樹、排列數(shù)以深度優(yōu)先方式搜索解空間，搜索過程中用剪枝函數(shù)避免無效搜索常用剪枝函數(shù)：約束函數(shù)在擴(kuò)展結(jié)點(diǎn)處，剪去不滿足約束的子樹限界函數(shù)剪去得不到最優(yōu)解的子樹------解題步驟8.3基本特征69解題步驟定義問題的解空間；確定易于搜索的解空間結(jié)構(gòu)：子集樹、排列數(shù)深度優(yōu)先方式搜索解空間，用剪枝函數(shù)避免無效搜索上界函數(shù)Cw+r

bestw------解題步驟8.3基本特征70回溯方式遞歸回溯在一般情況下，用遞歸方法實(shí)現(xiàn)回溯法。voidbacktrack(intt){

if(t>n)output(x);//已到葉子結(jié)點(diǎn)，輸出結(jié)果

else//未到葉子結(jié)點(diǎn)，繼續(xù)深度搜索for(inti=f(n,t);i<=g(n,t);i++){x[t]=h(i);if(constraint(t)&&bound(t)) backtrack(t+1);}}t-遞歸深度n解樹高度f(n,t),g(n,t)當(dāng)前擴(kuò)展結(jié)點(diǎn)處，未搜索過的子樹的起始編號和終止編號。h(i)當(dāng)前擴(kuò)展結(jié)點(diǎn)處x[t]的第i個可選值。------回溯方式迭代回溯8.3基本特征71回溯方式遞歸回溯迭代回溯采用樹的非遞歸深度優(yōu)先遍歷算法，實(shí)現(xiàn)非遞歸迭代回溯。------回溯方式voidbacktrack(intt){

if(t>n)output(x);//已到葉子結(jié)點(diǎn)，輸出結(jié)果

else//未到葉子結(jié)點(diǎn)，繼續(xù)深度搜索for(inti=f(n,t);i<=g(n,t);i++){x[t]=h(i);if(constraint(t)&&bound(t)) backtrack(t+1);}}voiditerative-Backtrack(){intt=1;

while(t>0){

if(f(n,t)<=g(n,t))for(inti=f(n,t);i<=g(n,t);i++){x[t]=h(i);

if(constraint(t)&&bound(t)){

if(solution(t))output(x);

elset++;}}

elset--;}}72算法原理

在問題的解空間樹

(子集/排列樹)中，按深度優(yōu)先策略搜索解空間樹。根據(jù)剪枝函數(shù)（可行性約束函數(shù)、上界函數(shù)）對搜索樹進(jìn)行剪枝。8.3基本特征------效率什么是子集樹、排列樹？

相應(yīng)的算法時(shí)間復(fù)雜度和空間復(fù)雜度是多少？8.3基本特征73子集樹當(dāng)所給的問題是從n個元素的集合S中，找出滿足某種性質(zhì)的子集時(shí)，相應(yīng)的解空間稱為子集樹。例如，裝載問題所相應(yīng)的解空間樹就是子集樹。------效率8.3基本特征74子集樹找出滿足某種性質(zhì)的子集，相應(yīng)的解空間稱為子集樹。節(jié)點(diǎn)數(shù)：通常有2n

個葉節(jié)點(diǎn)，其節(jié)點(diǎn)總個數(shù)為2n+1-1。時(shí)間復(fù)雜度：遍歷子集樹的任何算法，計(jì)算時(shí)間均為O(2n)。voidbacktrack(intt){if(t>n)output(x);elsefor(inti=0;i<=1;i++){x[t]=i;if(legal(t))backtrack(t+1);}}------效率8.3基本特征75排列樹當(dāng)所給問題是確定n個元素滿足某種性質(zhì)的排列時(shí)，相應(yīng)的解空間樹稱為排列樹。例如，旅行商問題所相應(yīng)的解空間樹，就是排列樹。------效率23036441335440211426214324455………………8.3基本特征76排列樹當(dāng)所給問題是確定n個元素滿足某種性質(zhì)的排列時(shí)，相應(yīng)的解空間樹稱為排列樹。節(jié)點(diǎn)數(shù)：通常有n!個葉節(jié)點(diǎn)。時(shí)間復(fù)雜度：遍歷排列樹，需要O(n!)的計(jì)算時(shí)間。------效率23036441335440211426214324455………………voidbacktrack(intt){if(t>n)output(x);elsefor(inti=t;i<=n;i++){swap(x[t],x[i]);if(legal(t))backtrack(t+1);swap(x[t],x[i]);}}778.3基本特征------效率時(shí)間復(fù)雜度

子集樹：結(jié)點(diǎn)數(shù)目mn，計(jì)算時(shí)間O(mn)排列樹：結(jié)點(diǎn)數(shù)目n!，計(jì)算時(shí)間O(n!)子集樹與排列樹遍歷子集樹需O(2n)計(jì)算時(shí)間遍歷排列樹需要O(n!)計(jì)算時(shí)間backtrack(t){if(t>n)thenoutput(x)elsefori=0to1dox[t]=iif(legal(t))thenbacktrack(t+1)}backtrack(t){if(t>n)thenoutput(x)elsefori=ttondo

swap(x[t],x[i])if(legal(t))thenbacktrack(t+1)

swap(x[t],x[i])}8.3基本特征79空間復(fù)雜度在任何時(shí)刻，算法只保存從根結(jié)點(diǎn)到當(dāng)前擴(kuò)展結(jié)點(diǎn)的路徑。如果解空間樹中，從根結(jié)點(diǎn)到葉結(jié)點(diǎn)的最長路徑的長度為h(n)，則回溯法所需的計(jì)算空間通常為O(h(n))。從而，顯式地存儲整個解空間需要的內(nèi)存空間為O(2h(n))或O(h(n)!)。用回溯法解題的一個顯著特征是在搜索過程中動態(tài)產(chǎn)生問題的解空間。------效率808.3基本特征------效率從以上實(shí)例看出，回溯法的效率在很大程度上依賴于以下因素：產(chǎn)生擴(kuò)展結(jié)點(diǎn)x[k]的時(shí)間；滿足顯約束的擴(kuò)展結(jié)點(diǎn)x[k]值的個數(shù)；剪枝時(shí)間：計(jì)算可行性約束函數(shù)和上界函數(shù)的時(shí)間；滿足可行性約束函數(shù)和上界函數(shù)的所有擴(kuò)展結(jié)點(diǎn)x[k]的個數(shù)。好的剪枝函數(shù)，能顯著地減少所生成的結(jié)點(diǎn)數(shù)。但是，這樣的剪枝函數(shù)往往計(jì)算量較大。因此，選擇剪枝函數(shù)時(shí)，通常存在生成結(jié)點(diǎn)數(shù)與剪枝函數(shù)計(jì)算量之間的折衷。思考如何改進(jìn)回溯算法的效率？81思考0/1背包的回溯算法，如何改進(jìn)限界函數(shù)？N后問題的回溯算法，如何改進(jìn)回溯法的效率？82回溯算法通用解題法：系統(tǒng)搜索問題的所有解或部分解.在所有解空間樹中深度優(yōu)先搜索,對肯定不包含解的節(jié)點(diǎn),跳過該節(jié)點(diǎn)為根的子樹,逐層向上回溯.求所有解:回溯至根,且根的所有子樹已搜索過任一解:搜索到一個解即結(jié)束例:0-1背包問題xi={0,1}n=3時(shí)解空間23{(0,0,0),(0,1,0),(0,0,1),(1,0,0),(0,1,1),(1,0,1),(1,1,0),(1,1,1)}組織成樹或圖:根到葉的路徑對應(yīng)解空間的元素ABCDEFGHIKKLMNO11010010110010注意：同一個問題可以有多種表示，有些表示方法更簡單，所需表示的狀態(tài)空間更?。ù鎯α可?，搜索方法簡單）?；厮莘ㄇ蠼鈫栴}的基本思想按深度優(yōu)先策略，從根結(jié)點(diǎn)出發(fā)搜索解空間樹。搜索至解空間樹的任意一點(diǎn)時(shí)，先判斷該結(jié)點(diǎn)是否包含問題的解。如果肯定不包含，則跳過對該結(jié)點(diǎn)為根的子樹的搜索，逐層向其祖先結(jié)點(diǎn)回溯；否則，進(jìn)入該子樹，繼續(xù)按深度優(yōu)先策略搜索。不斷地用修改過的剪枝函數(shù)P（x1，…，xn）去測試正在構(gòu)造中的n-元組的部分向量（x1，…，xi），看其是否可能導(dǎo)致最優(yōu)解。如果判定（x1，…，xi）不可能導(dǎo)致最優(yōu)解，那么就將可能要測試的mi+l…mn個向量一概略去。減少了測試次數(shù)。例:背包W=[16,15,15]P=[45,25,25]C=30(1,1)r<0x3即DH節(jié)點(diǎn)不再搜索ABr=30-16p=45Cr=30p=0D不可行解Er=30-16p=45Fr=15p=25Gp=0非最優(yōu)解HIK不可行解Kp=45LP=50MP=25110100110010搜索策略解空間：子集樹1.用約束函數(shù)在擴(kuò)展節(jié)點(diǎn)出剪去不滿足約束的子樹.0-1背包C=30可行性約束函數(shù)：進(jìn)入左子樹時(shí)檢查只要左兒子是—個可行結(jié)點(diǎn)。搜索就進(jìn)入左子樹。由于可行結(jié)點(diǎn)的右兒子結(jié)點(diǎn)總是可行的，故進(jìn)入右子樹時(shí)不需檢查可行性。

2.用限界函數(shù)剪去不能得到最優(yōu)解的子樹上界函數(shù)：進(jìn)入右子樹時(shí)檢查右子樹可能包含最優(yōu)解時(shí)才進(jìn)入搜索。否則剪去。2.用限界函數(shù)剪去不能得到最優(yōu)解的子樹設(shè)r為當(dāng)前尚未考慮的剩余物品價(jià)值總和cp是當(dāng)前價(jià)值,bestp當(dāng)前最優(yōu)價(jià)值.cp+r<=bestp時(shí)剪去右子樹0-1背包問題按單位價(jià)值排序,以此裝入,裝不下時(shí)裝入一部分

n=4c=7p=[9,10,7,4]w=[3,5,2,1]排序p=[4,7,9,10]w=[1,2,3,5]x=[1,0.2,1,1]上界計(jì)算—bound函數(shù)0-1背包問題上界函數(shù)：r為當(dāng)前尚未考慮的剩余物品價(jià)值總和,范圍太大，能否改進(jìn)？例:背包c(diǎn)=7

p=[4,7,9,10]w=[1,2,3,5]ABw=1p=4Cb=20p=20Dw=3p=11Eb=15p=19Hw=6p=20Ib=4/5*10p=19110100CallknapBacktrack(1)knapbacktrack(i){if(i>n)thenbestp=cpreturnif(cw+w[i])<=c)//x[i]=1cw當(dāng)前重量

thencw+=w[i]cp+=p[i]backtrack(i+1)cw-=w[i]cp-=p[i]if(Bound(i+1)>bestp)thenbacktrack(i+1)//x[i]=0}動態(tài)地生成問題的解空間樹。在每個結(jié)點(diǎn)處算法花費(fèi)O(1)時(shí)間。子集樹中結(jié)點(diǎn)個數(shù)兒O(2n)，backtrack所需的計(jì)算時(shí)間為O(2n)，另外backtrack還需O(n)遞歸棧。0-1背包問題Bound(i){//計(jì)算上界

cleft=c-cw//剩余容量

b=cp//以物品單位重量價(jià)值遞減序裝入物品

while(i<=nandw[i]<=cleft)docleft-=w[i]b+=p[i]i++//裝滿背包if(i<=n)b+=p[i]/w[i]*cleftreturnb}數(shù)組x記錄了解樹從根到擴(kuò)展結(jié)點(diǎn)的路徑，這些信息已包含回溯法所需信息.非遞歸表示可進(jìn)一步省去O(n)?？臻g93N后問題94n后問題在n×n格的棋盤上放置彼此不受攻擊的n個皇后。按照國際象棋的規(guī)則，皇后可以攻擊與之處在同一行或同一列或同一斜線上的棋子。n后問題等價(jià)于在n×n格的棋盤上放置n個皇后，任何2個皇后不放在同一行或同一列或同一斜線上。1234567812345678QQQQQQQQ8-皇后問題：每兩個都不在同一行、同一列及同一條斜角線上。給棋盤的行和列都編上1到8的號碼。假定皇后i將放在行i上。因此，8皇后問題可以表示成8-元組（x1，…，x8），其中xi是放置皇后i所在的列號。使用這種表示的顯式約束條件是Si=｛1，2，3，4，5，6，7，8｝，1≤i≤8。1234567812345678QQQQ