計算復雜性之回溯法

回溯法回溯法1.概要回溯法是一種選優(yōu)搜索法，按選優(yōu)條件向前搜索，以達到目標。但當探索到某一步時，發(fā)現(xiàn)原先選擇并不優(yōu)或達不到目標，就退回一步重新選擇，這種走不通就退回再走的技術為回溯法，而滿足回溯條件的某個狀態(tài)的點稱為“回溯點”?；厮莘ㄕ豪梅种畏ǖ姆椒ǜF舉搜索，分治法將一個問題分解成幾個類似的小規(guī)模問題，再將子問題的解合成原問題的解?？偩V：1.二進制字符串回溯法2.K-ary字符串回溯法3.修剪與刪除4.如何編寫回溯法算法應用于：1.背包問題2.漢密爾頓路徑問題3.旅行推銷員問題窮舉搜索窮舉搜索，顧名思義，就是嘗試所求問題的所有可能性。窮舉搜索的時間往往很慢，但也有一些關于標準的工具來幫助我們使用：生成基本項目的算法，比如：1.長度為n的二進制字符串共有2n個字符。2.長度為n的k-ary字符串有kn個字符3.n!種排列方式4.在n樣事物中選取r件事物，共有n!/r!(n-r)!種組合。回溯法可以通過“優(yōu)化修剪”的方法加速窮舉搜索?；厮莼締栴}1、位串問題問題：生成含有n個字符的所有字符串。解題思路：使用分治法。用數(shù)組A[1..n]來保存當前的二進制字符串。目的是調用process(A)一次，用數(shù)組A[1..n]保存每個二進制字符串。偽代碼：Procedurebinary(m)commentprocessallbinarystringsoflengthmifm=0thenprocess(A)elseA[m]:=0;binary(m?1)A[m]:=1;binary(m?1)正確性證明要求：對任意的m≥1,binary(m)調用process(A)一次，數(shù)組A[1..n]包含每個有m個字符的字符串。證明：證明關于m使用歸納法。上述要求對于m=0明顯成立?，F(xiàn)在假設binary(m-1)調用process(A)一次，數(shù)組A[1..m-1]保存每個有m-1個字符的字符串.首先，binary(m)1.將A[m]值設為0；2.調用binary(m-1)由歸納假設，這會調用process(A)一次，數(shù)組A[1..m]包含每個有m個字符的字符串，以0結束。然后，binary(m)1.將A[m]值設為1；2.調用binary(m-1).由歸納假設，這會調用process(A)一次，數(shù)組A[1..m]包含每個有m個字符的字符串，以1結束。因此，binary(m)調用process(A)一次，數(shù)組A[1..n]包含每個有m個字符的字符串。分析設T(n)為binary(m)的運行時間.假設程序進程消耗時O(1),則因此，由上式的遞推公式推導出此式子，T(n)=(c+d)2n-1?d.因而,T(n)=O(2n),這意味著生成字符串的算法是最優(yōu)的。k-ary字符串問題：生成所有來自0..k-1,n個數(shù)字的字符串.解決方案：用數(shù)組A[1..n]來保存當前的k-ary字符串。目的是調用process(A)一次用數(shù)組A[1..n]保存每個k-ary字符串。偽代碼：procedurestring(m)commentprocessallk-arystringsoflengthmifm=0thenprocess(A)elseforj:=0tok?1doA[m]:=j;string(m?1)正確性證明：與二進制案例相似。分析：與二進制案例相似，算法最優(yōu)回溯法則回溯通過一個樹形結構來尋找解空間。舉例來說長度為3的二進制字符串：回溯法會在這樹上進行前序遍歷，處理葉子。通過修剪法來減少計算時間：跳過沒有用的樹葉的節(jié)點。找到的是錯誤的則回到父節(jié)點k-ary字符串的剪切應用字符串數(shù)組填充過程從右到左,string(m,k)可以刪除那些對A[m]而言不容于A[m+1,..n]的選擇。procedurestring(m)commentprocessallk-arystringsoflengthmifm=0thenprocess(A)elseforj:=0tok?1doifjisavalidchoiceforA[m]thenA[m]:=j;string(m?1)創(chuàng)造一個回溯算法創(chuàng)造一個回溯算法的步驟：選擇一個基本對象，如：字符串，排列組合(在本輪文中將是字符串)用分而治之代碼來生成這些基本對象用這個代碼測試其性能關于基本的遞歸在每一次遞歸調用前優(yōu)化代碼算法一般形式的生成算法:一般形式的回溯算法:proceduregenerate(m)proceduregenerate(m)ifm=0thenprocess(A)ifm=0thenprocess(A)elseforeachofabunchofelseforeachofabunchnumbersjdoofnumbersjdoA[m]:=j;generate(m?1)ifjconsistentwithA[m+1..n]thenA[m]:=j;generate(m?1)背包問題TheKnapsackProblem解決方案：給定n個支路，用一個數(shù)組A[1…n]如果支路i被用上，則使得A[i]=1。遍歷A[1…n]來尋找合值。n=3,s1=4,s2=5,s3=2,L=6.算法使用二進制字符串算法。優(yōu)化剪切：設l為剩余長度，1，A[m]=0時是合適的；2，A[m]=1時是不合適的，如果sm>l；優(yōu)化剪切程序knapsack(n,L)用長度分別為s1,...,sn的n個枝條輸出背包問題的所有解，背包的長度大小為L。procedureknapsack(m,l)commentsolveknapsackproblemwithmrods,knapsacksizelifm=0thenifl=0thenprint(A)elseA[m]:=0;knapsack(m?1,l)ifsm≤lthenA[m]:=1;knapsack(m?1,l?sm)分析：時間為O(2n)廣義字符串注意k可以可以與字符串的每個數(shù)字不同,比如設數(shù)組D[1..n]，A[m]取值0..D[m]-1.procedurestring(m)commentprocessallstringsoflengthmifm=0thenprocess(A)elseforj:=0toD[m]?1doA[m]:=j;string(m?1)應用：在一個有n個節(jié)點的圖中，D[m]可以是節(jié)點m的深度。漢密爾頓循環(huán)HamiltonianCycles在一個有向圖中的漢密爾頓循環(huán)是每一個頂僅經(jīng)過一次的循環(huán)。問題：給定一個有向圖G=(V,E),找到一個漢密爾頓循環(huán)。用鄰接表保存有向圖(頂點v?{1,2,...n}，保存一個頂點w的表使得(v,w)?E).用A[1...n]保存一個漢密爾頓循環(huán)，循環(huán)為A[n]→A[n1]→...A[2]→A[1]→A[n]漢密爾頓循環(huán)近鄰表AdjacencylistN為neighboursD為degree（近鄰個數(shù)）漢密爾頓循環(huán):算法使用廣義字符串算法。修剪優(yōu)化：設定一個布爾數(shù)組U[1...n],如果頂點m未用，U[m]未用?？紤]點m1.U[m]=ture是合適的2.U[m]=false是不合適的；優(yōu)化剪切為了解決漢密爾頓循環(huán)問題，為輸入圖建立數(shù)組N(鄰接)和D(度)，并執(zhí)行下列。假設n>1.分析漢密爾頓程序花費多長時間找到一個哈密爾頓循環(huán)？假設沒有找到.設T(n)是hanmilton(v,n)運行時間.假設圖形有最大輸出度d。因而，存在b,c?IN,因此（通過重復替代）,T(n)=O(dn).因此在一個n結點的，無漢密爾頓循環(huán)的圖中總運行時間是O(dn)。而有一個漢密爾頓循環(huán)被找到的運行時間則是O(dn+d)=O(dn).旅行推銷員問題優(yōu)化問題(TSP):給定有向標記圖G=（V,E），找到最小代價的漢密爾頓循環(huán)（成本是指路徑上標記的總和）。有界優(yōu)化問題(BTSP):給定有向標記圖G=（V,E）且B∈IN,找到一個成本小于B的漢密爾頓循環(huán)。解決邊界問題是足夠的。然后完整的問題可以通過二進制搜索完成。假設我們有一個程序BTSP(x),能夠返回一個長度為最大x的漢密爾頓循環(huán)，如果循環(huán)存在。為了解決優(yōu)化問題，調用TSP(1,B),其中B是所有邊界成本的和(如果存在漢密爾頓循環(huán)，消耗最小的那個循環(huán)一定比TSP(1,B)少.)functionTSP(l,r)commentreturnmincostHam.cycleofcost≤rand≥lifl=rthenreturn(BTSP(l))elsem:=[(l+r)/2]

ifBTSP(m)succeedsthenreturn(TSP(l,m))elsereturn(TSP(m+1,r))(注意，應該首先調用BTSP(B)來確保一個漢密爾頓環(huán)存在)程序TSP被稱為O(logB)時間(分析與二進制搜索相似)。假設1.圖有n個邊2.圖在最大b上有標記（所以B≤bn)3.程序運行時間O(T(n)).因而，程序TSP運行時間——(logn+logb)T(n).BTSP的回溯設C[v,w]是路徑(v,w)∈E的成本,假如(v,w)∈E,C[v,w]=∞.1.fori:=1ton?1doU[i]:=true2.U[n]:=false;A[n]:=n3.hamilton(n?1,B)procedurehamilton(m,b)commentcompleteHamiltoniancyclefromA[m+1]withmunusednodes,cost≤b4.ifm=0thenprocess(A,b)else5.forj:=1toD[A[m+1]]do6.w:=N[A[m+1],j]7.ifU[w]andC[A[m+1],w]≤bthen8.U[w]:=false9.A[m]:=whamilton(m?1,b?C[v,w])10.U[w]:=trueprocedureprocess(A,b)commentcheckthatthecycleisclosed11.ifC[A[1],n]≤bthenprint(A)分析:運行時間O(dn),對于漢密爾頓環(huán)1.成本最大的路徑的額外修剪是在7行完成。2.程序(行11)通過使用鄰接矩陣使得運算更簡單?；厮莘?摘要：排列回溯應用于：漢密爾頓路徑問題和平皇后問題排列問題：生成n個不同數(shù)字的所有排列。解決方案：1.經(jīng)過所有的長度為n的n元字符串，剪除所有的非排列。2.設一個布爾數(shù)組U[1..n],如果m是未用的,U[m]是ture。3.用一個數(shù)組A[1..n]來表示當前的排列。4.目的是調用process(a),一旦A[1..n]包含當前排列。調用程序permute(n):procedurepermute(m)commentprocessallpermsoflengthm1.ifm=0thenprocess(A)else2.forj:=1tondo3.ifU[j]then4.U[j]:=false5.A[m]:=j;permute(m?1)6.U[j]:=true這里和前面的漢密爾頓環(huán)問題是一樣的。一個漢密爾頓環(huán)就是圖像節(jié)點的一個排列。分析很清楚，算法的運行時間為O(nn).但是這個分析并不緊密:它沒有考慮到修剪的問題。第三行執(zhí)行了多少次？運行的時間將會大于O(nn).當?shù)?行被運行是是什么情形？0≤i<n,程序會用排列的一部分填充在A的頂部的i個空位，然后會在第2行的下一個空位嘗試n個候選。前i個位置：從n個數(shù)中選i個數(shù)，沒有重復，進行排列。

有幾種方法填寫排列的一部分？因此，第三行被執(zhí)行的次數(shù)是所以，排序所要花費的時間為O((n+1)!),這就比之前的一般算法要優(yōu)越快速排序之前的排列生成算法不是最優(yōu)化算法：對于因子n，生成了n!個排列，耗時O((n+1)!).一個更好的算法是：用分而治之算法去創(chuàng)造一個只有有一種排列方式的更快的回溯算法：1.首先對于所有的1≤i≤n,設定A[i]=i,2.用A[1...n-1]的值,依次從1..n替代A[n]。排序代碼procedurepermute(m)commentprocessallpermsinA[1..m]1.ifm=1thenprocess(A)else2.permute(m?1)3.fori:=1tom?1do4.swapA[m]withA[j]forsome1≤j<m5.permute(m?1)問題：如何確保在第4行中交換進A[m]中的值是不同的解決方法：在每一次遞歸調用后，確保A是重置的，并用A[i]置換A[m]procedurepermute(m)1.ifm=1thenprocesselse2.permute(m?1)3.fori:=m?1downto1do4.swapA[m]withA[i]5.permute(m?1)6.swapA[m]withA[i]分析設T(n)是由程序permute(n)產(chǎn)生的交換次數(shù)?？傻肨(1)=0,T(n)=nT(n-1)+2(n-1),n>2.要求:對任意n≥1,T(n)≤2n!?2.證明:對于n進行歸納法證明。對于n=1,要求明顯成立，假設題設對于n成立?？捎校琓(n+1)=(n+1)T(n)+2n≤(n+1)(2n!?2)+2n=2(n+1)!?2.因此，排列程序運行時間為O(n!),是最優(yōu)的。稠密圖上的漢密爾頓循環(huán)使用鄰接矩陣:M[i,j]是真，如果(i,j)∈E.1.fori:=1tondo2.A[i]:=i3.hamilton(n?1)procedurehamilton(m)commentfindHamiltoniancyclefromA[m]withmunusednodes4.ifm=0thenprocess(A)else5.forj:=mdownto1do6.ifM[A[m+1],A[j]]then7.swapA[m]withA[j]8.hamilton(m?1)9.swapA[m]withA[j]procedureprocess(A)commentcheckthatthecycleisclosed10.ifM[A[1],n]thenprint(A)分析因此，，漢密爾頓換的運行時間為?O(dn)(使用廣義字符竄)?O((n?1)!)(使用排列).兩個范圍那個更??？取決于d的取值。當d≤n/e(e=2.7183...)，字符串算法更優(yōu)。和平皇后問題該問題是十九世紀著名的數(shù)學家高斯1850年提出：在8X8格的國際象棋上擺放八個皇后，使其不能互相攻擊，即任意兩個皇后都不能處于同一行、同一列或同一斜線上，問有多少種擺法。皇后問題用數(shù)組A[i]來存儲第i列皇后的位置，如圖A=[42736851]發(fā)現(xiàn)這形成了一個排序算法procedurequeen(m)1.ifm=0thenprocesselse2.fori:=mdownto1do3.ifOKtoputqueenin(A[i],m)then4.swapA[m]withA[i]5.queen(m?1)6.swapA[m]withA[i]如何確定將皇后放到位子(i,j)是否正確？當沒有皇后在所放位子的對角線和反對角線上沒有皇后。考慮下面的數(shù)組：entry(i,j)=i+_j要點：?在同一反對角線上的函數(shù)值是相同的?函數(shù)值的范圍是2..2n考慮下面的數(shù)組：entry(i,j)=i-j要點：?在同一對角線上的函數(shù)值是相同的?函數(shù)值的范圍是-n+1..n-1設定數(shù)組b[2..2n]和d[-n+1..n-1](初始化為真)，使得?b[i]是假的,如果反對角線i是被一個皇后占用的,2≤i≤2n?d[i]是假的,如果對角線i是被一個皇后占用的,?n+1≤i≤n?1.于前面的程序相比，增加的判定條件b[A[i]+m]andd[A[i]?m]procedurequeen(m)1.ifm=0thenprocesselse2.fori:=mdownto1do3.ifb[A[i]+m]andd[A[i]?m]then4.swapA[m]withA[i]5.b[A[m]+m]:=false6.d[A[m]?m]:=false7.queen(m?1)8.b[A[m]+m]:=true9.d[A[m]?m]:=true10.swapA[m]withA[i]實驗結果如何將一個算法付諸實踐？?理論運行時間：O(n!)?應用于BerkeleyUnixPascalonSunSparc2?適用于n≤18?通過因子2也許能夠減少運行時間（沒能實現(xiàn)）?改進了原始回溯法（理論上O(n?n!)）觀察超過一個常數(shù)的多元Count為放置皇后的方式有count種時間縱軸用1e+t來表示，可看出隨著皇后數(shù)量n的增加，運算時間增長很快回溯法3重點：組合回溯組合：從n個不同元素中取r個不重復的元素組成一個子集，而不考慮其元素的順序，稱為從n個中取r個的無重組合，例如OR={1,2,3,4},n=4,r=3則無重組合為：

{1,2,3};{1,2,4};{1,3,4};{2,3,4}.組合問題：n中一次選r生成所有組合。解：用數(shù)組A[1..r]來表示當前組合。調用程序choose(n,r)。procedurechoose(m,q)commentchooseqelementsoutof1..mifq=0thenprocess(A)elsefori:=qtomdoA[q]:=ichoose(i?1,q?1)正確性分三個部分進行證明：1.程序只生成組合；2.生成組合的正確的數(shù)目;3.沒有組合被生成兩次。要求1.如果0≤r≤n,被choose(n,r)生成的組合中，A[1...r]包含n中選r的組合。證明：關于r進行歸納證明。假設對于r=0顯然成立。現(xiàn)在假設r>0，對于任意的i≥r?1,，在由程序choose(i,r-1)產(chǎn)生的組合中，A[1...r-1]包含從1..i中選r-1的組合?，F(xiàn)在調用程序choose(i-1,r-1),i的取值由r到n,因此,由歸納假設和A[r]的設定值i，在由程序choose(n,r)產(chǎn)生的組合中A[1..r]包含從1..i-1中選r-1的組合，遵循i的值。那意味著，A[1..r]中包含從1..n中選r的組合。要求2.程序choose(n,r)調用會產(chǎn)生的組合數(shù)目為證明：在r上使用歸納法證明。假設對于r=0是明顯成立的?，F(xiàn)在假設r>0，對于任意的r?1≤i≤n，程序choose(i,r-1)一次將產(chǎn)生的組合數(shù)目為現(xiàn)在，choose(n,r)調用choose(i-1,r-1),i的取值r≤i≤n.因此，由歸納假設，生成的組合數(shù)目為第一部遵從重索引，第二部遵從恒等式2恒等式1恒等式2要求：對于任意的n≥0和1≤r≤n,證明：關于n進行歸納假設證明。假設對于n=r是明顯成立的，在這種情況下等式的兩邊為1現(xiàn)在假設n>r時成立我們需要證明的是現(xiàn)在有歸納假設有，

（由恒等式1）

回到正確性證明要求3.程序choose(n,r)的一次調用，產(chǎn)生從1..n中選r的組合，沒有組合是重復的。證明：這個證明關于r進行歸納法證明，證明過程與上面類似?，F(xiàn)在我完成正確性證明：由有要求1，程序choose(n,r)的一次調用將會產(chǎn)生從1..n中選r的所有組合(因為r個元素一次性有數(shù)組A中選出，根據(jù)要求3，不會產(chǎn)生重復的組合)由要求2，將會產(chǎn)生生成組合的正確數(shù)目。因此它將會產(chǎn)生所有從1..n中選r個的正確組合。分析設T(n,r)是在choose(n,r)中產(chǎn)生的時間數(shù)量。要求：對于任意的n≥1和0≤r≤n,證明：choose(n,r)的一次調用將會生成下面的遞歸調用fori:=rtondoA[r]:=ichoose(i?1,r?1)因此，成本的總和為

我們關于r進行歸納法證明要求對于r=0明顯成立?，F(xiàn)在假設對于r>0和任意的i<n,然后根據(jù)歸納假設和恒等式2，最后一部遵循前面，對于任意的1≤r≤n,這也同樣能關于r應用歸納法證明。對于r=1明顯成立，因為在這種情況下不等式的兩邊都為n現(xiàn)在假設r>1.最優(yōu)性由上面可知數(shù)組生產(chǎn)算法耗時為因為每個任務生成的額外計算是一個常數(shù)，因此組合算法對于常數(shù)多元而言并不是最優(yōu)的。C為組合數(shù)量A為處理任務數(shù)Ratio(比例)為A/C最優(yōu)r≤n/2可看出表格上下有一定的對稱性，觀察發(fā)現(xiàn)如果r≤n/2時有有沒有這樣的規(guī)律呢？需要證明要求：如果1≤r≤n/2,則有證明：首先我們需要證明要求要求對于r=1，2成立。然后我們應用歸納假設證明對于3≤r≤n/2成立當r=1T(n,1)=n(由觀察得到),且因此，符合要求。當r=2時根據(jù)和我們要求這時成立的，因為n≥4(回想一下,r≤n/2),因此n2?3n?2≥0的最大根是當3≤r≤n/2要求：當3≤r≤n/2，時有關于n進行歸納假設證明。基本結為n=6.此時r的值只能為3，實驗證明算法需要34步去生成20個組合。因為2·20?2=38>34,假設對于基本要求成立?，F(xiàn)在假設n≥6,這意味著r≥3.由歸納假設和情況1，2可得最優(yōu)性回顧因此，我們的算法對于r≤n/2，是最優(yōu)的。有時這是一樣有用的:如果r>n/2,生成沒有選擇的項目,而不是有選擇的項目?；厮莘?繼續(xù)討論回溯的組合問題，它將應用于1團問題2獨立集問題3拉姆齊數(shù)完整圖Kn=(V,E)用來表示有n個頂點的完整圖，其中V={1,2,...,n},E=V×V.每個端點與另一個端點都有連線子圖誘發(fā)型子圖我們稱B=(U,F)是G=(V,E)的子圖，當U?V且F?E。我們稱B=(U,F)是G=(V,E)的子圖，當U?V且F=(U×U)∩E。誘發(fā)型子圖與子圖區(qū)別在于F的界定團問題一個團是一個完整圖的誘導子圖。團的大小就是頂點的數(shù)目。團問題：輸入：一個圖G=(V,E)，和一個整數(shù)r。輸出：圖G中一個大小為r的小團體，如果該小團體存在。假設:鑒于u,v∈V,我們可以在O(1)時間內檢查是否(u,v)∈E。此圖中有6元素的完整嗎？答案是：當然有什么是團:一個誘發(fā)型子圖里的一張完整圖一個回溯算法使用回溯法在一個從V中選出，具有r個頂點的的組合A。假設程序Process(A)用來檢查A中頂點是否形成團。A意味著在一個潛在團中的一系列