計(jì)算復(fù)雜性之回溯法

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

有幾種方法填寫(xiě)排列的一部分？因此，第三行被執(zhí)行的次數(shù)是所以，排序所要花費(fèi)的時(shí)間為O((n+1)!),這就比之前的一般算法要優(yōu)越快速排序之前的排列生成算法不是最優(yōu)化算法：對(duì)于因子n，生成了n!個(gè)排列，耗時(shí)O((n+1)!).一個(gè)更好的算法是：用分而治之算法去創(chuàng)造一個(gè)只有有一種排列方式的更快的回溯算法：1.首先對(duì)于所有的1≤i≤n,設(shè)定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)問(wèn)題：如何確保在第4行中交換進(jìn)A[m]中的值是不同的解決方法：在每一次遞歸調(diào)用后，確保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]分析設(shè)T(n)是由程序permute(n)產(chǎn)生的交換次數(shù)?？傻肨(1)=0,T(n)=nT(n-1)+2(n-1),n>2.要求:對(duì)任意n≥1,T(n)≤2n!?2.證明:對(duì)于n進(jìn)行歸納法證明。對(duì)于n=1,要求明顯成立，假設(shè)題設(shè)對(duì)于n成立。可有，T(n+1)=(n+1)T(n)+2n≤(n+1)(2n!?2)+2n=2(n+1)!?2.因此，排列程序運(yùn)行時(shí)間為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)分析因此，，漢密爾頓換的運(yùn)行時(shí)間為?O(dn)(使用廣義字符竄)?O((n?1)!)(使用排列).兩個(gè)范圍那個(gè)更??？取決于d的取值。當(dāng)d≤n/e(e=2.7183...)，字符串算法更優(yōu)。和平皇后問(wèn)題該問(wèn)題是十九世紀(jì)著名的數(shù)學(xué)家高斯1850年提出：在8X8格的國(guó)際象棋上擺放八個(gè)皇后，使其不能互相攻擊，即任意兩個(gè)皇后都不能處于同一行、同一列或同一斜線上，問(wèn)有多少種擺法?；屎髥?wèn)題用數(shù)組A[i]來(lái)存儲(chǔ)第i列皇后的位置，如圖A=[42736851]發(fā)現(xiàn)這形成了一個(gè)排序算法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)是否正確？當(dāng)沒(méi)有皇后在所放位子的對(duì)角線和反對(duì)角線上沒(méi)有皇后。考慮下面的數(shù)組：entry(i,j)=i+_j要點(diǎn)：?在同一反對(duì)角線上的函數(shù)值是相同的?函數(shù)值的范圍是2..2n考慮下面的數(shù)組：entry(i,j)=i-j要點(diǎn)：?在同一對(duì)角線上的函數(shù)值是相同的?函數(shù)值的范圍是-n+1..n-1設(shè)定數(shù)組b[2..2n]和d[-n+1..n-1](初始化為真)，使得?b[i]是假的,如果反對(duì)角線i是被一個(gè)皇后占用的,2≤i≤2n?d[i]是假的,如果對(duì)角線i是被一個(gè)皇后占用的,?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]實(shí)驗(yàn)結(jié)果如何將一個(gè)算法付諸實(shí)踐？?理論運(yùn)行時(shí)間：O(n!)?應(yīng)用于BerkeleyUnixPascalonSunSparc2?適用于n≤18?通過(guò)因子2也許能夠減少運(yùn)行時(shí)間（沒(méi)能實(shí)現(xiàn)）?改進(jìn)了原始回溯法（理論上O(n?n!)）觀察超過(guò)一個(gè)常數(shù)的多元Count為放置皇后的方式有count種時(shí)間縱軸用1e+t來(lái)表示，可看出隨著皇后數(shù)量n的增加，運(yùn)算時(shí)間增長(zhǎng)很快回溯法3重點(diǎn)：組合回溯組合：從n個(gè)不同元素中取r個(gè)不重復(fù)的元素組成一個(gè)子集，而不考慮其元素的順序，稱為從n個(gè)中取r個(gè)的無(wú)重組合，例如OR={1,2,3,4},n=4,r=3則無(wú)重組合為：

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

（由恒等式1）

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

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