博弈樹搜索課件

主講人：呂敏Email:{lvmin05@}Spring2012，USTC算法基礎算法基礎2023/1/42第十一講回溯法內(nèi)容提要：理解回溯法的深度優(yōu)先搜索策略掌握用回溯法解題的算法框架子集樹算法框架排列樹算法框架通過應用范例學習回溯法的設計策略2022/12/272第十一講回溯法內(nèi)容提要：3搜索算法介紹（1）窮舉搜索（2）盲目搜索—深度優(yōu)先(DFS)或回溯搜索(Backtracking);—廣度優(yōu)先搜索(BFS);—分支限界法(Branch&Bound)；—博弈樹搜索(α-βSearch)（3）啟發(fā)式搜索—A*算法和最佳優(yōu)先(Best-FirstSearch)—迭代加深的A*算法—B*,AO*,SSS*等算法—LocalSearch,GA等算法11-1方法概述3搜索算法介紹11-1方法概述4搜索空間的三種表示：—表序表示：搜索對象用線性表數(shù)據(jù)結構表示；—顯示圖表示：搜索對象在搜索前就用圖（樹）的數(shù)據(jù)結構表示；—隱式圖表示：除了初始結點，其他結點在搜索過程中動態(tài)生成。緣于搜索空間大，難以全部存儲。搜索效率的思考：隨機搜索—上世紀70年代中期開始，國外一些學者致力于研究隨機搜索求解困難的組合問題，將隨機過程引入搜索；—選擇規(guī)則是隨機地從可選結點中取一個，從而可以從統(tǒng)計角度分析搜索的平均性能；—隨機搜索的一個成功例子是：判定一個很大的數(shù)是不是素數(shù)，獲得了第一個多項式時間的算法。11-1方法概述4搜索空間的三種表示：11-1方法概述5回溯法：—回溯法是一個既帶有系統(tǒng)性又帶有跳躍性的搜索算法；—它在包含問題的所有解的解空間樹中，按照深度優(yōu)先的策略，從根結點出發(fā)搜索解空間樹?！到y(tǒng)性—算法搜索至解空間樹的任一結點時，判斷該結點為根的子樹是否包含問題的解，如果肯定不包含，則跳過以該結點為根的子樹的搜索，逐層向其祖先結點回溯。否則，進入該子樹，繼續(xù)深度優(yōu)先的策略進行搜索?！S性—這種以深度優(yōu)先的方式系統(tǒng)地搜索問題的解的算法稱為回溯法，它適用于解一些組合數(shù)較大的問題。11-1方法概述5回溯法：11-1方法概述6問題的解空間—問題的解向量：回溯法希望一個問題的解能夠表示成一個n元式

(x1,x2,…,xn)的形式?！@約束：對分量xi的取值限定?！[約束：為滿足問題的解而對不同分量之間施加的約束?！饪臻g：對于問題的一個實例，解向量滿足顯式約束條件的所有多元

組，

構成了該實例的一個解空間。11-1方法概述注意：同一個問題可以有多種表示，有些表示方法更簡單，所需表示的狀態(tài)空間更?。ù鎯α可伲阉鞣椒ê唵危?。n=3時的0-1背包問題用完全二叉樹表示的解空間6問題的解空間11-1方法概述注意：同一個問題可以有多種表711-1方法概述711-1方法概述8基本思想：—搜索從開始結點（根結點）出發(fā)，以深度優(yōu)先搜索整個解空間?！@個開始結點成為活結點，同時也成為當前的擴展結點。在當前的擴展結點處，搜索向縱深方向移至一個新結點。這個新結點就成為新的活結點，并成為當前擴展結點?！绻诋斍暗臄U展結點處不能再向縱深方向擴展，則當前擴展結點就成為死結點?！藭r，應往回移動（回溯）至最近的一個活結點處，并使這個活結點成為當前的擴展結點；直到找到一個解或全部解。11-1方法概述8基本思想：11-1方法概述9基本步驟：針對所給問題，定義問題的解空間；確定易于搜索的解空間結構；以深度優(yōu)先方式搜索解空間，并在搜索過程中用剪枝函數(shù)避免無效搜索。11-1方法概述常用剪枝函數(shù)：用約束函數(shù)在擴展結點處剪去不滿足約束的子樹；用限界函數(shù)剪去得不到最優(yōu)解的子樹。9基本步驟：11-1方法概述常用剪枝函數(shù)：10二類常見的解空間樹：子集樹：當所給的問題是從n個元素的集合S中找出滿足某種性質(zhì)的子集時，相應的解空間樹稱為子集樹。子集樹通常有2n個葉子結點，其總結點個數(shù)為2n+1-1，遍歷子集樹時間為Ω(2n)。如0-1背包問題，葉結點數(shù)為2n，總結點數(shù)2n+1；排列樹：當所給問題是確定n個元素滿足某種性質(zhì)的排列時，相應的解空間樹稱為排列樹。排列樹通常有n!個葉子結點，因此，遍歷排列樹需要Ω(n!)的計算時間。如TSP問題(TravelingSalesmanProblem，推銷員問題)

，葉結點數(shù)為n!，遍歷時間為Ω(n!)。11-1方法概述10二類常見的解空間樹：11-1方法概述11例1[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)構造解空間樹：11-1方法概述11例1[0-1背包]：n=3,w=(16,15,1211-1方法概述1211-1方法概述13例2

[TSP問題]:（1）定義解空間：X={12341,12431,13241,13421,14231,14321}（2）構造解空間樹：（3）從A出發(fā)按DFS搜索整棵樹：最優(yōu)解：13241，14231成本：2511-1方法概述13例2[TSP問題]:11-1方法概述14用回溯法解題的一個顯著特征是在搜索過程中動態(tài)產(chǎn)生問題的解空間。在任何時刻，算法只保存從根結點到當前擴展結點的路徑。如果解空間樹中從根結點到葉結點的最長路徑的長度為h(n)，則回溯法所需的計算空間通常為O(h(n))。而顯式地存儲整個解空間則需要O(2h(n))或O(h(n)!)內(nèi)存空間。11-1方法概述14用回溯法解題的一個顯著特征是在搜索過程中動態(tài)產(chǎn)生問題的解15回溯法對解空間作深度優(yōu)先搜索，因此在一般情況下可用遞歸函數(shù)來實現(xiàn)回溯法：子集樹回溯算法Backtrack(intt)//搜索到樹的第t層{//由第t層向第t+1層擴展，確定x[t]的值ift>nthenoutput(x);//葉子結點是可行解elsewhile(allXt)do//Xt為當前擴展結點的所有可能取值集合{x[t]=Xt中的第i個值；if(Constraint(t)andBound(t))Backtrack(t+1);}}執(zhí)行時，從Backtrack(1)開始。11-2算法框架15回溯法對解空間作深度優(yōu)先搜索，因此在一般情況下可用遞歸函16排列樹回溯法Backtrack(intt)//搜索到樹的第t層{//由第t層向第t+1層擴展，確定x[t]的值ift>nthenoutput(x);//葉子結點是可行解elsefori=ttondo{swap(x[t],x[i]);if(Constraint(t)andBound(t))Backtrack(t+1);swap(x[t],x[i]);}}11-2算法框架16排列樹回溯法11-2算法框架17問題定義：給定正整數(shù)n，生成1,2,…,n所有排列。解空間樹（排列樹）：當n=3時，11-3排列生成問題17問題定義：給定正整數(shù)n，生成1,2,…,n所有排列1811-3排列生成問題1811-3排列生成問題19問題描述：略基本思想：利用排列生成問題的回溯算法Backtrack(2)，對x[]={1,2,…,n}的x[2..n]進行全排列，則(x[1],x[2])，(x[2],x[3])，…,(x[n],x[1])構成一個回路。在全排列算法的基礎上，進行路徑計算保存以及進行限界剪枝。main(intn){a[n][n];x[n]={1,2,…,n};bestx[];cc=0.0;bestv=∞;//bestx保存當前最佳路徑，bestv保存當前最優(yōu)值input(a);//輸入鄰接矩陣TSPBacktrack(2);output(bestv,bestx[]);}11-4TSP問題19問題描述：略11-4TSP問題20TSPBacktrack(inti){//cc記錄(x[1],x[2]),…,(x[i-1],x[i])的距離和if(i>n){//搜索到葉結點，輸出可行解與當前最優(yōu)解比較if(cc+a[x[n]][1]<bestvorbestv=∞){bestv=cc+a[x[n]][1];for(j=1;j<=n;j++)bestx[j]=x[j];}}else{for(j=i;j<=n;j++)if(cc+a[x[i-1]][x[j]]<bestvorbestv=∞){//限界裁剪子樹

swap(x[i],x[j]);cc+=a[x[i-1]][x[i]];TSPBacktrack(i+1);cc-=a[x[i-1]][x[i]];swap(x[i],x[j]);}}}11-4TSP問題20TSPBacktrack(inti)11-4T21問題描述：在4x4棋盤上放上4個皇后，使皇后彼此不受攻擊。不受攻擊的條件是彼此不在同行（列）、斜線上。求出全部的放法。解表示：11-5

n皇后問題21問題描述：11-5n皇后問題2211-5

n皇后問題2211-5n皇后問題2311-5

n皇后問題2311-5n皇后問題2411-5

n皇后問題2411-5n皇后問題2511-6符號三角形問題下圖是由14個“+”和14個“-”組成的符號三角形。2個同號下面都是“+”，2個異號下面都是“-”。++-+-+++----+-+++--++--+---+在一般情況下，符號三角形的第一行有n個符號。符號三角形問題要求對于給定的n，計算有多少個不同的符號三角形，使其所含的“+”和“-”的個數(shù)相同。2511-6符號三角形問題下圖是由14個“+”和14個“26解向量：用n元組x[1:n]表示符號三角形的第一行，x[i]=1表示符號三角形的第一行第i個符號為“+”，x[i]=0表示符號三角形的第一行第i個符號為“-”?？尚行约s束函數(shù)：當前符號三角形所包含的“+”個數(shù)與“-”個數(shù)均不超過n*(n+1)/4無解的判斷：n*(n+1)/2為奇數(shù)11-6符號三角形問題++-+-+++----+-+++--++--+---

+++-+-++-----+++-++-+-26解向量：用n元組x[1:n]表示符號三角形的第一行，x[27voidTriangle::Backtrack(intt){//是一棵子集樹,t控制著第一行符號個數(shù)，對應于樹的層次if((count>half)||(t*(t-1)/2-count>half))return;//剪枝法，剪除不必要的子樹if(t>n)sum++;//到葉子結點，”+”號數(shù)和”-”號數(shù)相同的符號三角形個數(shù)增加1elsefor(inti=0;i<2;i++){//當前擴展結點Z只有兩種可能的取值0或1，即只可能有2個孩子p[1][t]=i;//二維數(shù)據(jù)p記錄了符號三角形矩陣count+=i;//當前符號三角形矩陣中，”+”號的個數(shù)for(intj=2;j<=t;j++){//從第二行起計算”+”號個數(shù)，計算可行性約束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);//擴展到第t+1層for(intj=2;j<=t;j++)//必須回退！因為外層for循環(huán)是對當前擴展結點兩個子樹分別搜索！count-=p[j][t-j+1];count-=i;}}11-6符號三角形問題27voidTriangle::Backtrack(int28復雜度分析：計算可行性約束需要O(n)時間，在最壞情況下有O(2n)個結點需要計算可行性約束，故解符號三角形問題的回溯算法所需的計算時間為O(n2n)。11-6符號三角形問題28復雜度分析：11-6符號三角形問題29問題描述：略解表示和解空間：{(x1,x2,…,xn)|xi∈{0,1},i=1~n}解空間樹：11-70-1背包問題29問題描述：略11-70-1背包問題30無限界函數(shù)的算法KnapBacktrack(inti){//cw當前背包重量，cv當前背包價值，bestv當前最優(yōu)價值if(i>n){//搜索到可行解bestv=(bestv<cv)?cv:bestv;output(x);}else{if(cw+w[i]<=c){//走左子樹x[i]=1;cw+=w[i];cv+=v[i];KnapBacktrack(i+1);cw-=w[i];cv-=v[i];}

//以下走右子樹x[i]=0;KnapBacktrack(i+1);}}11-70-1背包問題main(floatc,intn,floatw[],floatv[],intx[]){//主程序floatcw=0.0,cv=0.0,bestv=0.0;KnapBacktrack(1);}30無限界函數(shù)的算法11-70-1背包問題main(fl31有限界函數(shù)的算法—基本思想：設r是當前擴展結點z的右子樹（或左子樹）的價值上界，如果cv+r<=bestv時，則可以裁剪掉右子樹（或左子樹）。一種簡單的確定z的左、右子樹最優(yōu)值上界的方法（設z為第k層結點）：左子樹上界=i=k∑i=nvi，右子樹上界=i=k+1∑i=nvi

—求經(jīng)擴展結點z的可行解價值上界的方法：計算至擴展結點的當前背包價值已知xi，i=1~k-1，當前背包價值cv=i=1∑i=k-1vixi最后，

經(jīng)z左子樹的可行解價值上界=cv+左子樹上界經(jīng)z右子樹的可行解價值上界=cv+右子樹上界—算法（略）11-70-1背包問題31有限界函數(shù)的算法11-70-1背包問題32問題描述：給定無向連通圖G和m種不同的顏色。用這些顏色為圖G的各頂點著色，每個頂點著一種顏色。是否有一種著色法使G中每條邊的2個頂點著不同顏色。這個問題是圖的m可著色判定問題。若一個圖最少需要m種顏色才能使圖中每條邊連接的2個頂點著不同顏色，則稱這個數(shù)m為該圖的色數(shù)。求一個圖的色數(shù)m的問題稱為圖的m可著色優(yōu)化問題。四色猜想：

在一個平面或球面上的任何地圖能夠只用4種顏色來著色，使相鄰的國家在地圖上著不同的顏色。假設每個國家在地圖上是單連通區(qū)域，兩個國家相鄰則其邊界長度不為0.11-8圖的m著色問題右圖是一個有5個區(qū)域的地圖及其相應的平面圖。32問題描述：11-8圖的m著色問題右圖是一個有5個區(qū)域的33解向量：(x1,x2,…,xn)表示頂點i所著顏色x[i]；可行性約束函數(shù)：頂點i與已經(jīng)著色的相鄰頂點顏色不重復。11-8圖的m著色問題voidColor::Backtrack(intt){if(t>n){sum++;for(inti=1;i<=n;i++)cout<<x[i]<<'';cout<<endl;}elsefor(inti=1;i<=m;i++){x[t]=i;if(Ok(t))Backtrack(t+1);}}boolColor::Ok(intk){//檢查顏色可用性

for(intj=1;j<=n;j++)if((a[k][j]==1)&&(x[j]==x[k]))returnfalse;returntrue;}33解向量：(x1,x2,…,xn)表示頂點i所著顏色34算法復雜度分析：圖m可著色問題的解空間樹中內(nèi)結點個數(shù)是。對于每一個內(nèi)結點，在最壞情況下，用ok檢查當前擴展結點的每一個兒子所相應的顏色可用性需耗時O(mn)。因此，回溯法總的時間耗費是11-8圖的m著色問題34算法復雜度分析：11-8圖的m著色問題35通過前面具體實例的討論容易看出，回溯算法的效率在很大程度上依賴于以下因素：(1)產(chǎn)生x[t]的時間；(2)滿足顯約束的x[t]值的個數(shù)；(3)計算約束函數(shù)constraint的時間；(4)計算上界函數(shù)bound的時間；(5)滿足約束函數(shù)和上界函數(shù)約束的所有x[k]的個數(shù)。好的約束函數(shù)能顯著地減少所生成的結點數(shù)。但這樣的約束函數(shù)往往計算量較大。因此，在選擇約束函數(shù)時通常存在生成結點數(shù)與約束函數(shù)計算量之間的折衷。11-9回溯法效率分析35通過前面具體實例的討論容易看出，回溯算法的效率在很大程度36對于許多問題而言，在搜索試探時選取x[i]的值順序是任意的。在其它條件相當?shù)那疤嵯?，讓可取值最少的x[i]優(yōu)先。從圖中關于同一問題的2棵不同解空間樹，可以體會到這種策略的潛力。11-9回溯法效率分析(a)(b)圖(a)中，從第1層剪去1棵子樹，則從所有應當考慮的3元組中一次消去12個3元組。對于圖(b)，雖然同樣從第1層剪去1棵子樹，卻只從應當考慮的3元組中消去8個3元組。前者的效果明顯比后者好。36對于許多問題而言，在搜索試探時選取x[i]的值順序是任意謝謝！2023/1/437Q&A作業(yè)：1.P33522.3-22用回溯法從n個不同元素中取r個不重復的元素的所有組合。謝謝！2022/12/2737Q&A主講人：呂敏Email:{lvmin05@}Spring2012，USTC算法基礎算法基礎2023/1/439第十一講回溯法內(nèi)容提要：理解回溯法的深度優(yōu)先搜索策略掌握用回溯法解題的算法框架子集樹算法框架排列樹算法框架通過應用范例學習回溯法的設計策略2022/12/272第十一講回溯法內(nèi)容提要：40搜索算法介紹（1）窮舉搜索（2）盲目搜索—深度優(yōu)先(DFS)或回溯搜索(Backtracking);—廣度優(yōu)先搜索(BFS);—分支限界法(Branch&Bound)；—博弈樹搜索(α-βSearch)（3）啟發(fā)式搜索—A*算法和最佳優(yōu)先(Best-FirstSearch)—迭代加深的A*算法—B*,AO*,SSS*等算法—LocalSearch,GA等算法11-1方法概述3搜索算法介紹11-1方法概述41搜索空間的三種表示：—表序表示：搜索對象用線性表數(shù)據(jù)結構表示；—顯示圖表示：搜索對象在搜索前就用圖（樹）的數(shù)據(jù)結構表示；—隱式圖表示：除了初始結點，其他結點在搜索過程中動態(tài)生成。緣于搜索空間大，難以全部存儲。搜索效率的思考：隨機搜索—上世紀70年代中期開始，國外一些學者致力于研究隨機搜索求解困難的組合問題，將隨機過程引入搜索；—選擇規(guī)則是隨機地從可選結點中取一個，從而可以從統(tǒng)計角度分析搜索的平均性能；—隨機搜索的一個成功例子是：判定一個很大的數(shù)是不是素數(shù)，獲得了第一個多項式時間的算法。11-1方法概述4搜索空間的三種表示：11-1方法概述42回溯法：—回溯法是一個既帶有系統(tǒng)性又帶有跳躍性的搜索算法；—它在包含問題的所有解的解空間樹中，按照深度優(yōu)先的策略，從根結點出發(fā)搜索解空間樹?！到y(tǒng)性—算法搜索至解空間樹的任一結點時，判斷該結點為根的子樹是否包含問題的解，如果肯定不包含，則跳過以該結點為根的子樹的搜索，逐層向其祖先結點回溯。否則，進入該子樹，繼續(xù)深度優(yōu)先的策略進行搜索?！S性—這種以深度優(yōu)先的方式系統(tǒng)地搜索問題的解的算法稱為回溯法，它適用于解一些組合數(shù)較大的問題。11-1方法概述5回溯法：11-1方法概述43問題的解空間—問題的解向量：回溯法希望一個問題的解能夠表示成一個n元式

(x1,x2,…,xn)的形式。—顯約束：對分量xi的取值限定?！[約束：為滿足問題的解而對不同分量之間施加的約束?！饪臻g：對于問題的一個實例，解向量滿足顯式約束條件的所有多元

組，

構成了該實例的一個解空間。11-1方法概述注意：同一個問題可以有多種表示，有些表示方法更簡單，所需表示的狀態(tài)空間更?。ù鎯α可?，搜索方法簡單）。n=3時的0-1背包問題用完全二叉樹表示的解空間6問題的解空間11-1方法概述注意：同一個問題可以有多種表4411-1方法概述711-1方法概述45基本思想：—搜索從開始結點（根結點）出發(fā)，以深度優(yōu)先搜索整個解空間?！@個開始結點成為活結點，同時也成為當前的擴展結點。在當前的擴展結點處，搜索向縱深方向移至一個新結點。這個新結點就成為新的活結點，并成為當前擴展結點?！绻诋斍暗臄U展結點處不能再向縱深方向擴展，則當前擴展結點就成為死結點。—此時，應往回移動（回溯）至最近的一個活結點處，并使這個活結點成為當前的擴展結點；直到找到一個解或全部解。11-1方法概述8基本思想：11-1方法概述46基本步驟：針對所給問題，定義問題的解空間；確定易于搜索的解空間結構；以深度優(yōu)先方式搜索解空間，并在搜索過程中用剪枝函數(shù)避免無效搜索。11-1方法概述常用剪枝函數(shù)：用約束函數(shù)在擴展結點處剪去不滿足約束的子樹；用限界函數(shù)剪去得不到最優(yōu)解的子樹。9基本步驟：11-1方法概述常用剪枝函數(shù)：47二類常見的解空間樹：子集樹：當所給的問題是從n個元素的集合S中找出滿足某種性質(zhì)的子集時，相應的解空間樹稱為子集樹。子集樹通常有2n個葉子結點，其總結點個數(shù)為2n+1-1，遍歷子集樹時間為Ω(2n)。如0-1背包問題，葉結點數(shù)為2n，總結點數(shù)2n+1；排列樹：當所給問題是確定n個元素滿足某種性質(zhì)的排列時，相應的解空間樹稱為排列樹。排列樹通常有n!個葉子結點，因此，遍歷排列樹需要Ω(n!)的計算時間。如TSP問題(TravelingSalesmanProblem，推銷員問題)

，葉結點數(shù)為n!，遍歷時間為Ω(n!)。11-1方法概述10二類常見的解空間樹：11-1方法概述48例1[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)構造解空間樹：11-1方法概述11例1[0-1背包]：n=3,w=(16,15,4911-1方法概述1211-1方法概述50例2

[TSP問題]:（1）定義解空間：X={12341,12431,13241,13421,14231,14321}（2）構造解空間樹：（3）從A出發(fā)按DFS搜索整棵樹：最優(yōu)解：13241，14231成本：2511-1方法概述13例2[TSP問題]:11-1方法概述51用回溯法解題的一個顯著特征是在搜索過程中動態(tài)產(chǎn)生問題的解空間。在任何時刻，算法只保存從根結點到當前擴展結點的路徑。如果解空間樹中從根結點到葉結點的最長路徑的長度為h(n)，則回溯法所需的計算空間通常為O(h(n))。而顯式地存儲整個解空間則需要O(2h(n))或O(h(n)!)內(nèi)存空間。11-1方法概述14用回溯法解題的一個顯著特征是在搜索過程中動態(tài)產(chǎn)生問題的解52回溯法對解空間作深度優(yōu)先搜索，因此在一般情況下可用遞歸函數(shù)來實現(xiàn)回溯法：子集樹回溯算法Backtrack(intt)//搜索到樹的第t層{//由第t層向第t+1層擴展，確定x[t]的值ift>nthenoutput(x);//葉子結點是可行解elsewhile(allXt)do//Xt為當前擴展結點的所有可能取值集合{x[t]=Xt中的第i個值；if(Constraint(t)andBound(t))Backtrack(t+1);}}執(zhí)行時，從Backtrack(1)開始。11-2算法框架15回溯法對解空間作深度優(yōu)先搜索，因此在一般情況下可用遞歸函53排列樹回溯法Backtrack(intt)//搜索到樹的第t層{//由第t層向第t+1層擴展，確定x[t]的值ift>nthenoutput(x);//葉子結點是可行解elsefori=ttondo{swap(x[t],x[i]);if(Constraint(t)andBound(t))Backtrack(t+1);swap(x[t],x[i]);}}11-2算法框架16排列樹回溯法11-2算法框架54問題定義：給定正整數(shù)n，生成1,2,…,n所有排列。解空間樹（排列樹）：當n=3時，11-3排列生成問題17問題定義：給定正整數(shù)n，生成1,2,…,n所有排列5511-3排列生成問題1811-3排列生成問題56問題描述：略基本思想：利用排列生成問題的回溯算法Backtrack(2)，對x[]={1,2,…,n}的x[2..n]進行全排列，則(x[1],x[2])，(x[2],x[3])，…,(x[n],x[1])構成一個回路。在全排列算法的基礎上，進行路徑計算保存以及進行限界剪枝。main(intn){a[n][n];x[n]={1,2,…,n};bestx[];cc=0.0;bestv=∞;//bestx保存當前最佳路徑，bestv保存當前最優(yōu)值input(a);//輸入鄰接矩陣TSPBacktrack(2);output(bestv,bestx[]);}11-4TSP問題19問題描述：略11-4TSP問題57TSPBacktrack(inti){//cc記錄(x[1],x[2]),…,(x[i-1],x[i])的距離和if(i>n){//搜索到葉結點，輸出可行解與當前最優(yōu)解比較if(cc+a[x[n]][1]<bestvorbestv=∞){bestv=cc+a[x[n]][1];for(j=1;j<=n;j++)bestx[j]=x[j];}}else{for(j=i;j<=n;j++)if(cc+a[x[i-1]][x[j]]<bestvorbestv=∞){//限界裁剪子樹

swap(x[i],x[j]);cc+=a[x[i-1]][x[i]];TSPBacktrack(i+1);cc-=a[x[i-1]][x[i]];swap(x[i],x[j]);}}}11-4TSP問題20TSPBacktrack(inti)11-4T58問題描述：在4x4棋盤上放上4個皇后，使皇后彼此不受攻擊。不受攻擊的條件是彼此不在同行（列）、斜線上。求出全部的放法。解表示：11-5

n皇后問題21問題描述：11-5n皇后問題5911-5

n皇后問題2211-5n皇后問題6011-5

n皇后問題2311-5n皇后問題6111-5

n皇后問題2411-5n皇后問題6211-6符號三角形問題下圖是由14個“+”和14個“-”組成的符號三角形。2個同號下面都是“+”，2個異號下面都是“-”。++-+-+++----+-+++--++--+---+在一般情況下，符號三角形的第一行有n個符號。符號三角形問題要求對于給定的n，計算有多少個不同的符號三角形，使其所含的“+”和“-”的個數(shù)相同。2511-6符號三角形問題下圖是由14個“+”和14個“63解向量：用n元組x[1:n]表示符號三角形的第一行，x[i]=1表示符號三角形的第一行第i個符號為“+”，x[i]=0表示符號三角形的第一行第i個符號為“-”。可行性約束函數(shù)：當前符號三角形所包含的“+”個數(shù)與“-”個數(shù)均不超過n*(n+1)/4無解的判斷：n*(n+1)/2為奇數(shù)11-6符號三角形問題++-+-+++----+-+++--++--+---

+++-+-++-----+++-++-+-26解向量：用n元組x[1:n]表示符號三角形的第一行，x[64voidTriangle::Backtrack(intt){//是一棵子集樹,t控制著第一行符號個數(shù)，對應于樹的層次if((count>half)||(t*(t-1)/2-count>half))return;//剪枝法，剪除不必要的子樹if(t>n)sum++;//到葉子結點，”+”號數(shù)和”-”號數(shù)相同的符號三角形個數(shù)增加1elsefor(inti=0;i<2;i++){//當前擴展結點Z只有兩種可能的取值0或1，即只可能有2個孩子p[1][t]=i;//二維數(shù)據(jù)p記錄了符號三角形矩陣count+=i;//當前符號三角形矩陣中，”+”號的個數(shù)for(intj=2;j<=t;j++){//從第二行起計算”+”號個數(shù)，計算可行性約束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);//擴展到第t+1層for(intj=2;j<=t;j++)//必須回退！因為外層for循環(huán)是對當前擴展結點兩個子樹分別搜索！count-=p[j][t-j+1];count-=i;}}11-6符號三角形問題27voidTriangle::Backtrack(int65復雜度分析：計算可行性約束需要O(n)時間，在最壞情況下有O(2n)個結點需要計算可行性約束，故解符號三角形問題的回溯算法所需的計算時間為O(n2n)。11-6符號三角形問題28復雜度分析：11-6符號三角形問題66問題描述：略解表示和解空間：{(x1,x2,…,xn)|xi∈{0,1},i=1~n}解空間樹：11-70-1背包問題29問題描述：略11-70-1背包問題67無限界函數(shù)的算法KnapBacktrack(inti){//cw當前背包重量，cv當前背包價值，bestv當前最優(yōu)價值if(i>n){//搜索到可行解bestv=(bestv<cv)?cv:bestv;output(x);}else{if(cw+w[i]<=c){//走左子樹x[i]=1;cw+=w[i];cv+=v[i];KnapBacktrack(i+1);cw-=w[i];cv-=v[i];}

//以下走右子樹x[i]=0;KnapBacktrack(i+1);}}11-70-1背包問題main(floatc,intn,floatw[],floatv[],intx[]){//主程序floatcw=0.0,cv=0.0,bestv=0.0;KnapBacktrack(1);}30無限界函數(shù)的算法11-70-1背包問題main(fl68有限界函數(shù)的算法—基本思想：設r是當前擴展結點z的右子樹（或左子樹）的價值上界，如果cv+r<=bestv時，則可以裁剪掉右子樹（或左子樹）。一種簡單的確定z的左、右子樹最優(yōu)值上界的方法（設z為第k層結點）：左子樹上界=i=k∑i=nvi，右子樹上界=i=k+1∑i=n