計算理論與算法分析設計：05-backtrack

搜索法

方法概述:搜索算法介紹搜索算法

(1)窮舉搜索(Exhaustive

Search)(2)盲目搜索(BlindSearch)-深度優(yōu)先(DFS)或回溯搜索

(Backtracking);-廣度優(yōu)先搜索(BFS);-分枝限界法(Branch&Bound);-博弈樹搜索(α-βSearch)(3)啟發(fā)式搜索(HeuristicSearch)-A*算法，B*，GA……2方法概述:搜索算法介紹（續(xù)）搜索空間的三種表示

-表序表示:搜索對象用線性表數據結構表示;-顯式圖表示:搜索對象在搜索前就用圖(樹)的數據結構表示;-隱式圖表示:除了初始結點,其他結點在搜索過程中動態(tài)生成.緣于搜索空間大,難以全部存儲.3方法概述:搜索算法介紹（續(xù)）提高搜索效率的思考：隨機搜索

-上世紀70年代中期開始,國外一些學者致力于研究隨機搜索求解困難的組合問題,將隨機過程引入搜索;-選擇規(guī)則是隨機地從可選結點中取一個,從而可以從統(tǒng)計角度分析搜索的平均性能;-隨機搜索的一個成功例子:n后問題.4組合爆炸一張充分大的普通紙對折40次：

高度超過5千座珠穆朗瑪峰一張充分大的普通紙對折50次：月地距離的128倍一個問題有n個變量,k個選擇,則遍歷空間的大小為kn并行處理也不可能克服和繞過組合爆炸；但并行處理可能是當前提高求解規(guī)模的最好和現實的途徑。5世界紀錄:2^132011年，15名學生和教師利用長度超過2英里=3218米的衛(wèi)生紙和MIT的無盡長廊(無盡長廊是連接MIT主建筑群的走廊，長度為825英尺=251.46米，不用再擔心廁紙會被風吹走)，創(chuàng)造了紙張連續(xù)對半折疊的新世界紀錄——13次，打破了2002年的舊記錄——12次。連續(xù)向同一方向對折13次相當于疊出8192（2^13）層。數學教師、廁紙折疊高手Tanton表示，這相當于攀登珠穆朗瑪峰。6世界紀錄:2^137一、寬度優(yōu)先搜索法BreadthFirstSearch(BFS)寬度優(yōu)搜索法：逐層地對結點進行擴展。例：重排九宮問題：在3Х3的方格棋盤上放置分別標有數字1，2，3，···，8的八張牌，初始狀態(tài)為S0，目標狀態(tài)為St28314765S012384765St82834765S01283

1

4765223

8

47653283

476542836

4755832147652837

1465

23

8

476523

8

476528

43765283

4

576283

64

75283

6475678910111213832147652837

14651

23

8

4765234

876528

4

3765283

4

576283

641

75283

67541415218

32147658

13247652223283746

152837

146

52425123847651

2378

4652627StRoute:S0→3→8→16→26(St)9

優(yōu)點：只要問題有解，用寬度優(yōu)先搜索法一定可以得到解，而且得到的是路徑最短的解。缺點：盲目性較大。當目標結點距離初始結點較遠時將會產生許多無用結點，搜索效率低。10二、深度優(yōu)先搜索法DepthFirstSearch(DFS)深度優(yōu)搜索法：縱深地對結點進行擴展。11St2834765S01283

14765223

8476511283

4765283

6475832147652837

1465

23

8

476523

8

476528

43765283

4

576283

64

75283

64753713832147652837

14651

23

8

4765234

876528

4

3765283

4

576283

641

75283

6754488

32147658

132476556283746

152837

146

5910123847651

2378

4651412So:l→11→12→13→14:St12搜索一旦進入某個分支，就將沿著該分支一直向下搜索。如果目標結點恰好在此分支上，則可較快地得到解。但如果目標結點不在此分支上，而該分支又是一個無窮分支，則就不可能得到解。所以深度優(yōu)先搜索是不完備的。13（二）、有界深度優(yōu)先搜索法解決深度優(yōu)先搜索不完備的問題，引入搜索深度的界限（設為dm），當搜索深度達到了深度界限，而尚未出現目標結點，就換一個分支進行搜索。14

1234515回溯法

回溯法既帶有系統(tǒng)性又帶有跳躍性的搜索算法。在包含問題所有解的解空間樹中，按照深度優(yōu)先的策略，從根結點出發(fā)搜索解空間樹(系統(tǒng)性)

算法搜索至解空間樹的任一結點時，判斷該結點為根的子樹是否包含問題的解(跳躍性)如果肯定不包含，則跳過以該結點為根的子樹的搜索，逐層向其祖先結點回溯。否則，進入該子樹，繼續(xù)按深度優(yōu)先的策略進行搜索。

這種以深度優(yōu)先的方式系統(tǒng)地搜索問題的解的算法稱為回溯法，它適用于解一些組合數較大的問題。17問題的解空間18問題的解向量：回溯法希望一個問題的解能夠表示成一個n元式(x1,x2,…,xn)的形式。顯約束：對分量xi的取值限定。隱約束：為滿足問題的解而對不同分量之間施加的約束。解空間：對于問題的一個實例，解向量滿足顯式約束條件的所有多元組，構成了該實例的一個解空間。注意：同一個問題可以有多種表示，有些表示方法更簡單，所需表示的狀態(tài)空間更?。ù鎯α可伲阉鞣椒ê唵危?。n=3時的0-1背包問題用完全二叉樹表示的解空間有三種結點：解空間樹：根結點（搜索的起點）中間結點（非終端結點）葉結點（終端結點），葉結點為解向量搜索過程就是找一個或一些特別的葉結點。19－從開始結點（根結點）出發(fā)，以DFS搜索整個解空間。－開始結點成為一個活結點，同時也成為當前的擴展結點。在當前的擴展結點處向縱深方向移至一個新結點，并成為一個新的活結點，也成為當前擴展結點。－如果在當前的擴展結點處不能再向縱深方向擴展，則當前擴展結點就成為死結點。－此時，應往回移動（回溯）至最近的一個活結點處，并使這個活結點成為當前的擴展結點；直至找到一個解或全部解。方法概述20start??deadenddeadend??deadend?success!deadend算法的基本步驟1）針對問題，定義問題的解空間（對解進行編碼）；2）確定易于搜索的解空間組織結構（按樹或圖組織解）；3）以深度優(yōu)先方式搜索解空間，搜索過程中裁減掉死結點的子樹提高搜索效率。21常用剪枝函數：用約束函數在擴展結點處剪去不滿足約束的子樹；用限界函數剪去得不到最優(yōu)解的子樹。二類常見的解空間樹①子集樹：當所給的問題是從n個元素的集合S中找出滿足某種性質的子集時，相應的解空間樹稱為子集樹葉結點數2n，總結點數2n+1，遍歷時間為Ω(2n)如0-1背包②排列樹：當所給問題是確定n個元素滿足某種性質的排列時，相應的解空間樹稱為排列樹葉結點數n!，遍歷時間為Ω(n!)如TSP問題方法概述22子集樹與排列樹0-1背包問題含有2n個葉結點旅行商問題含有(n-1)!個葉結點問：每個樹的葉結點數目是多少？23例[0-1背包]：n=3,w=(16,15,15),v=(45,25,25),c=30(1)定義解空間：X={(0,0,0),(0,0,1),(0,1,0),…,(1,1,0),(1,1,1)}(2)構造解空間樹：(1,1,1)AHIDJKEBLMFNOGC10101010101010(1,1,0)(1,0,1)(1,0,0)(0,1,1)(0,1,0)(0,0,1)(0,0,0)24n=3,w=(16,15,15),v=(45,25,25),c=30(3)從A出發(fā)按DFS搜索：AHIDJKEBLMFNOGC10101010101010455025250可行解:(1,0,0)(0,1,1)(0,1,0)(0,0,1)(0,0,0)殺死結點解值:最優(yōu)解L=(0,1,1),最優(yōu)值為5025(1)定義解空間：X={12341,12431,13241,13421,14231,14321}(2)構造解空間樹：(3)從A出發(fā)按DFS搜索整棵樹：26例[TSP問題]：求從頂點1出發(fā)，最后回到頂點1的最短路線。最優(yōu)解：13241，14231成本：25用回溯法解題的一個顯著特征是在搜索過程中動態(tài)產生問題的解空間在任何時刻，算法只保存從根結點到當前擴展結點的路徑如果解空間樹中從根結點到葉結點的最長路徑的長度為h(n)，則回溯法所需的計算空間通常為O(h(n))。顯式地存儲整個解空間則需要O(2h(n))或O(h(n)!)內存空間27回溯算法的一般框架子集樹回溯算法

voidBacktrack(intt)//搜索到樹的第t層

{//由第t層向第t+1層擴展，確定x[t]的值if(t>n)output(x);//葉結點是可行解，輸出解

elsewhile(allXt){//Xt為當前擴展結點的所有可能取值集合，例如0和1

x[t]=Xt中第i個值;if(Constraint(t)&&Bound(t))Backtrack(t+1);}}執(zhí)行時：Backtrack(1)//從1擴展并回溯28節(jié)點可行，則探索下一深度當前節(jié)點取遍所有可能，即探索樹下一深度回溯算法的一般框架（續(xù)）排列樹回溯算法

voidBacktrack(intt)//搜索到樹的第t層

{//由第t層向第t+1層擴展，確定x[t]的值if(t>n)output(x);//葉結點是可行解，輸出解

else//已經探索到第t個元素，需要調整后面至n的元素排序fori=tton{//對后續(xù)節(jié)點，每個試一次swap(x[t],x[i]);if(Constraint(t)&&Bound(t))Backtrack(t+1);swap(x[t],x[i]);}}29恢復到初始排序，便于回溯針對第t個節(jié)點，依次將它與后繼所有節(jié)點進行置換，即遍歷新次序是有價值的5.2裝載問題有一批共n個集裝箱要裝上2艘載重量分別為C1和C2的輪船，其中集裝箱i的重量為wi，且∑wi≤C1+C2裝載問題要求確定是否有一個合理的裝載方案可將這些集裝箱裝上這2艘輪船。如果有，找出一種裝載方案。如何利用貪心算法合理的裝載方案？n=3,C1=C2=50,w=[10,40,40]n=3,C1=C2=50,w=[20,40,40]30問題分析容易證明，如果一個給定裝載問題有解，則采用下面的策略可得到最優(yōu)裝載方案：(1)首先將第一艘輪船盡可能裝滿；(2)將剩余的集裝箱裝上第二艘輪船。31將第一艘輪船盡可能裝滿等價于選取全體集裝箱的一個子集，使該子集中集裝箱重量之和最接近C1。由此可知，裝載問題等價于特殊的0-1背包問題。32解空間：子集樹對于當前擴展節(jié)點Z，對于箱子i，有x[i]=1：左子樹，代表選中x[i]=0：右子樹，代表不選可行性約束函數(選擇當前元素)：記當前載重量為cw若cw+w[i]<=c1，左子樹可選擇右子樹總是可以選，因為不增加重量33限界函數：用于剪去不含最優(yōu)解的子樹，從而提高算法在平均情況下的運行效率。設Z是解空間樹第i層上的當前擴展結點，cw是當前載重量，R是剩余集裝箱的重量，besetW是當前最優(yōu)載重量，則當

cw+R≤bestW時，剪去Z的右子樹34裝載問題算法描述voidbacktrack(inti){//搜索第i層結點

if(i>n)//到達葉結點更新最優(yōu)解bestx,bestw;return;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];}35練習:子集和問題問題給定由n個不同正整數組成的集合W={wi}，和正整數M，求W中所有和等于M的子集的集合。例如n=5,M=20,

W={8,4,9,7,3}

365.3批處理作業(yè)調度問題描述給定n個作業(yè)的集合{J1,J2,…,Jn}。每個作業(yè)必須先由機器1處理，然后由機器2處理。作業(yè)Ji需要機器j的處理時間為tji。對于一個確定的作業(yè)調度，設Fji是作業(yè)i在機器j上完成處理的時間。所有作業(yè)在機器2上完成處理的時間和稱為該作業(yè)調度的完成時間和。批處理作業(yè)調度問題要求對于給定的n個作業(yè)，制定最佳作業(yè)調度方案，使其完成時間和達到最小。37實例分析tji機器1機器2作業(yè)121作業(yè)231作業(yè)323這3個作業(yè)的6種可能的調度方案是1,2,3；1,3,2；2,1,3；2,3,1；3,1,2；3,2,1；它們所相應的完成時間和分別是19，18，20，21，19，19。則最佳調度方案是1,3,2，其完成時間和為18。38122321133+6+10算法設計從n個作業(yè)的所有排列中找出最小完成時間和的最小調度問題，所以批處理作業(yè)調度問題的解空間是一顆排列樹。39批處理作業(yè)調度40解空間：排列樹voidFlowshop::Backtrack(inti){if(i>n){//到達葉結點，判斷并更新最優(yōu)解for(intj=1;j<=n;j++)bestx[j]=x[j];bestf=f;}elsefor(intj=i;j<=n;j++){f1+=M[x[j]][1];f2[i]=((f2[i-1]>f1)?f2[i-1]:f1)+M[x[j]][2];f+=f2[i];if(f<bestf){//僅考慮有更優(yōu)可能選擇Swap(x[i],x[j]);Backtrack(i+1);Swap(x[i],x[j]);}f1-=M[x[j]][1];f-=f2[i];}}classFlowshop{friendFlow(int**,int,int[]);private:voidBacktrack(inti);int**M,//各作業(yè)所需的處理時間*x,//當前作業(yè)調度*bestx,//當前最優(yōu)作業(yè)調度*f2,//機器2完成處理時間

f1,//機器1完成處理時間

f,//完成時間和

bestf,//當前最優(yōu)值

n;//作業(yè)數};算法效率解空間：排列樹復雜性：在最壞情況下，整個算法的計算時間復雜性為T(n)=O(n!)。415.4符號三角形問題++-+-+++----+-+++--++--+---+下圖是由14個“+”和14個“-”組成的符號三角形。2個同號下面都是“+”，2個異號下面都是“-”。在一般情況下，符號三角形的第一行有n個符號。符號三角形問題要求對于給定的n，計算有多少個不同的符號三角形，使其所含的“+”和“-”的個數相同。425.4符號三角形問題解向量：用n元組x[1:n]表示三角形第一行，其中x[i]=1代表“+”，x[i]=0代表“-”解空間：子集數，且為二叉樹遞推生成：x[1:i]確定一個子三角；x[i+1]的結果只需多考慮一條斜邊三角形包含符合個數：n*(n+1)/2|+|=|-|=n*(n+1)/4故當“+”或“-”超過n*(n+1)/4，可剪枝n*(n+1)/2為奇數時，肯定不滿足43++-+-+++----+-+++--++--+---+5.4符號三角形問題privatestaticvoidbacktrack(intt){

if((count>half)||(t*(t-1)/2-count>half))return;

if(t>n)sum++;//到達葉節(jié)點，找到一個解

elsefor(inti=0;i<2;i++){//探索左右子樹p[1][t]=i;count+=i;

for(intj=2;j<=t;j++){p[j][t-j+1]=p[j-1][t-j+1]^p[j-1][t-j+2];count+=p[j][t-j+1];}

backtrack(t+1);

for(intj=2;j<=t;j++)count-=p[j][t-j+1];count-=i;}}44++-+-+++----+-+++--++--+---+count:“+”個數half：總符號數/2sum：達標三角形個數p：符合三角形內容從第二行起遞推擴展子三角，計算”+”號個數剪除不可能分枝算法效率解空間：子集樹復雜性：計算可行性約束需要O(n)時間，在最壞情況下有O(2n)個結點需要計算可行性約束，故解符號三角形問題的回溯算法所需的計算時間為O(n2n)。455.5n后問題

例（4后問題）設有一4*4的棋盤，把4個皇后放在棋盤上，要求滿足下列兩個條件：1）任意兩個皇后不在同一行上和同一列上；2）任意兩個皇后不在同一條對角線上；問有多少種放法？若用窮舉法，先不考慮這兩個條件，則有種方案。C(16,4)=182046設第i行放置第i個皇后，xi表示皇后i所處的列數，這樣4后問題的全部解向量可以寫成(x1,x2,x3,x4)的形式。顯式約束條件是xi={1，2，3，4}1≤i≤4若只考慮顯式約束條件，則解空間是由44=256個四元組組成。隱式條件有兩個：兩個皇后不在同一列上和不在同一對角線上。471238134691114165710121517x1=118192429202225273032212326283133x1=2x2=2x3=3x4=4344242334232

這棵排列樹僅考慮了條件1）。這棵樹也叫做該問題的解空間。結點的編號是按深度優(yōu)先給出的。樹中的分支代表著解向量(x1,x2,x3,x4)的分量xi的取值。從根到葉子的所有路徑組成解空間。則有種方案。4!=2448QQХХQQQХХХХQQХQХХХХQQХ12347568109x1=1x2=23424233BBBBB4912347568109x1=1x2=23424233BBBBB111213141516x1=2BB1341350n后問題顯約束：xi=1,2,…,n隱約束：不同列：xixj不處于同一正、反對角線：|i-j||xi-xj|

如何判斷是否處于對角線：有y1=f(x1)，y2=f(x2)斜率(x1-x2)/(y1-y2)=1|xi-xj|=|i-j|51n后問題算法：判斷能否放置一個新棋子//在第k行的列位置x[k]是否可放置boolplace(intx[],intk)

{inti;

for(i=1;i<k;i++)

if((x[i]==x[k]))||abs(x[i]-x[k])==abs(i-k)))

returnFALSE;

i←i+1;}

returnTRUE;

}

52n后遞歸算法voidnqueens(intn,intx[])

{//由第k層向k+1層擴展，確定x[k]的值

if(k>n)thenprintf(x[]);else{fori=1ton{x[k]=i;if(Place(x[],k))Backtrack(k+1);}

}

}53n后非遞歸算法voidnqueens(intn,intx[])

{intk=1;x[1]=0;

while(k>0){

x[k]=x[k]+1;//試驗第k行的下一個未考察列

while(x[k]<=n)&&(!place(x,k)))

x[k]=x[k]+1;

if(x[k]<=n){//說明第k行有位置可放入

if(k==n)break;//n行全部考察結束

else{k=k+1;x[k]=0;}//下一行

}

else{x[k]=0;k=k-1;}//無法放入，退一行

}

}54n后問題555.60-1背包問題：裝載問題法比較裝載問題求最大重量0-1背包求最大價值解空間：子集樹1走左子樹，0走右子樹可行性約束函數當前載重cw，價值cpcw+w[i]<=c，左子樹可選擇右子樹總是可以選，因為不增加重量限界函數：cp+r<=bestp，減去右子樹565.60-1背包問題解空間：子集樹1走左子樹，0走右子樹改進的限界函數：Bound()假設物品可拆分，利用貪心思想，求剩余空間裝滿對應的最大價值按單位重量價值從大到小排序進行選擇570-1背包問題Bound(inti){//計算價值的上界，故效率更高

intcleft=c-cw;//剩余容量

intb=cp;//以物品單位重量價值遞減序裝入物品

while(i<=n&&w[i]<=cleft){cleft-=w[i];b+=p[i];i++;}//裝滿背包，假設物品可拆分

if(i<=n)b+=p[i]/w[i]*cleft;returnb;}58voidbacktrack(inti){//搜索第i層結點

if(i>n)//到達葉結點更新最優(yōu)解bestx,bestp;return;if(cw+w[i]<=c){//搜索左子樹

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

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

if(bound(i+1)>bestp){x[i]=0;//搜索右子樹

backtrack(i+1);}}59載重量50，物體5,15,25,27,30，價值12,30,44,46,50。已按單位價值排好序605.7最大團問題完全子圖：給定無向圖G=(V，E)。如果UV，且對任意u，vU有(u，v)E，則稱U是G的完全子圖。團：G的完全子圖U是G的團當且僅當U不包含在G的更大的完全子圖中。G的最大團：是指G中所含頂點數最多的團。61例子12354{1,2}是G的一個大小為2的完全子圖，它不是團。因為它包含于G的更大的完全子圖{1,2,5}之中。{1,2,5},{1,4,5},{2,3,5}分別是G的最大團。G的最大團？62基本概念空子圖：如果UV且對任意u，vU有(u，v)E，則稱U是G的空子圖。12354{2,4}是G的一個空子圖。63基本概念(續(xù))獨立集：G的空子圖U是G的獨立集當且僅當U不包含在G的更大的空子圖中。G的最大獨立集：是G中所含頂點數最多的獨立集。12354{2,4}是G的一個最大獨立子集。64基本概念(續(xù))補圖：對于任一無向圖G=(V，E)其補圖=(V1，E1)定義為：V1=V，且(u，v)E1當且僅當(u，v)E。123541235465例子12354{1，2}是的一個空子圖，不是的獨立集，因為它包含在的空子圖{1,2,5}中。{1,2,5}是的最大獨立集。66基本概念(續(xù))U是G的最大團當且僅當U是的最大獨立集。67問題分析解空間：子集樹可行性約束函數：頂點i到已選入的頂點集中每一個頂點都有邊相連。限界函數：有足夠多的可選擇頂點使得算法有可能找到更大的團。68voidClique::Backtrack(inti)//計算最大團{if(i>n){//到達葉結點

for(intj=1;j<=n;j++)bestx[j]=x[j];bestn=cn;return;}intOK=1;//檢查頂點i與當前團的連接

for(intj=1;j<i;j++)if(x[j]&&a[i][j]==0){//i與j不相連

OK=0;break;}if(OK){//進入左子樹

x[i]=1;cn++;Backtrack(i+1);x[i]=0;cn--;}if(cn+n-i>bestn){//進入右子樹

x[i]=0;Backtrack(i+1);}}69復雜度分析復雜度分析最大團問題的回溯算法backtrack所需的計算時間為O(n2