算法設計及分析 第五章ppt

第一章算法概述第二章遞歸與分治策略第三章動態(tài)規(guī)劃第四章貪心算法第五章回溯法第六章分支限界法第七章概率算法算法設計與分析>目錄1通用解題法5.1基本思想5.2裝載問題5.3批處理作業(yè)調度5.5n后問題5.7最大團問題5.8圖的著色問題算法設計與分析>目錄25.4符號三角形問題5.9旅行售貨員問題5.12

連續(xù)郵資問題3有許多問題，當需要找出它的解集或者要求回答什么解是滿足某些約束條件的最佳解時，往往要使用回溯法。回溯法的基本做法是搜索，或是一種組織得井井有條的、能避免不必要搜索的窮舉式搜索法。這種方法適用于解一些組合數(shù)相當大的問題。算法設計與分析>回溯法引言4回溯法在問題的解空間樹中，按深度優(yōu)先策略，從根結點出發(fā)搜索解空間樹。算法搜索至解空間樹的任意一點時，先判斷該結點是否包含問題的解：如果肯定不包含，則跳過對該結點為根的子樹的搜索，逐層向其祖先結點回溯；否則，進入該子樹，繼續(xù)按深度優(yōu)先策略搜索。算法設計與分析>回溯法5應用回溯法解問題時，首先應明確定義問題的解空間。問題的解空間應至少包含問題的一個(最優(yōu))解。問題的解向量：回溯法希望一個問題的解能夠表示成一個n元式(x1,x2,…,xn)的形式。顯約束：對分量xi的取值限定。解空間：對于問題的一個實例，解向量滿足顯式約束條件的所有多元組，構成了該實例的一個解空間。算法設計與分析>回溯法5.1算法框架注意：同一個問題可以有多種表示，有些表示方法更簡單，所需表示的狀態(tài)空間更小（存儲量少，搜索方法簡單）。

例如

0-1背包問題設有n個物體和一個背包,物體i的重量為wi價值為vi背包的載荷為C,若將物體i(1i

n,)裝入背包,則有價值為vi

.目標是找到一個方案,使得能放入背包的物體總價值最高。算法設計與分析>回溯法有限離散問題總可以用窮舉法求得問題的全部解.61、問題的解空間7算法設計與分析>回溯法

例如取N=3,C=30,w={16,15,15},v={45,25,25}問題所有可能的解為(解空間):

(0,0,0),(0,0,1),(0,1,0),

(0,1,1),(1,0,0),(1,0,1),(1,1,0),(1,1,1)可表示為一棵3層的完全正則二叉樹時間復雜性:O(2n)子集樹對物品1的選擇對物品3的選擇對物品2的選擇111111000000011234578111214151310698算法設計與分析>回溯法旅行售貨員問題該問題是一個NP完全問題，有(n-1)!條可選路線91234206305410ABCDEFGHIJKLMNOPQ1234344342322423算法設計與分析>回溯法旅行售貨員問題最優(yōu)解(1,3,2,4,1)，最優(yōu)值25解空間組織成一棵樹,從樹的根結點到任意一葉結點的路徑定義了圖G的一條周游路線排列樹10基本步驟：(1)針對所給問題，定義問題的解空間；(2)確定易于搜索的解空間結構；(3)以深度優(yōu)先方式搜索解空間，并在搜索過程中用剪枝函數(shù)避免無效搜索。算法設計與分析>回溯法2、回溯法的基本思想11生成問題狀態(tài)基本方法擴展結點：一個正在產(chǎn)生兒子的結點稱為擴展結點活結點：一個自身已生成但其兒子還沒有全部生成的節(jié)點稱做活結點死結點：一個所有兒子已經(jīng)產(chǎn)生的結點稱做死結點回溯法：為了避免生成那些不可能產(chǎn)生最佳解的問題狀態(tài)，要不斷地利用限界函數(shù)來處死那些實際上不可能產(chǎn)生所需解的活結點，以減少問題的計算量。具有限界函數(shù)的深度優(yōu)先生成法稱為回溯法。算法設計與分析>回溯法12深度優(yōu)先的問題狀態(tài)生成法：如果對一個擴展結點R，一旦產(chǎn)生了它的一個兒子C，就把C當做新的擴展結點。在完成對子樹C（以C為根的子樹）的窮盡搜索之后，將R重新變成擴展結點，繼續(xù)生成R的下一個兒子（如果存在）寬度優(yōu)先的問題狀態(tài)生成法：在一個擴展結點變成死結點之前，它一直是擴展結點算法設計與分析>回溯法13常用剪枝函數(shù)：用約束函數(shù)在擴展結點處剪去不滿足約束的子樹；用限界函數(shù)剪去得不到最優(yōu)解的子樹。算法設計與分析>回溯法例如:0-1背包問題的回溯法用剪枝函數(shù)剪去導致不可行解的子樹;旅行售貨員問題的回溯法中剪去不含最優(yōu)解的子樹,如果從根結點到當前擴展結點處的部分周游路線的費用已超過當前找到的最好周游線路費用,則斷定該結點的子樹不含最優(yōu)解.14關于復雜性：搜索過程中動態(tài)產(chǎn)生問題的解空間。在任何時刻，算法只保存從根結點到當前擴展結點的路徑。如果解空間樹中從根結點到葉結點的最長路徑的長度為h(n)，則回溯法所需的計算空間通常為O(h(n))。存儲解空間則需要O(2h(n))或O(h(n)!)。算法設計與分析>回溯法153、遞歸回溯回溯法對解空間作深度優(yōu)先搜索，因此，在一般情況下用遞歸方法實現(xiàn)回溯法。voidbacktrack(intt){if(t>n)output(x);elsefor(inti=f(n,t);i<=g(n,t);i++){x[t]=h(i);if(constraint(t)&&bound(t))

backtrack(t+1);}}算法設計與分析>回溯法記錄或輸出得到的可行解x表示在當前擴展結點處的約束函數(shù)和限界函數(shù)表示在擴展節(jié)點處的第i個可選值t:遞歸深度n:葉結點f:起始編號g:終止編號164、迭代回溯采用樹的非遞歸深度優(yōu)先遍歷算法，可將回溯法表示為一個非遞歸迭代過程。

voiditerativeBacktrack() { 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--; } }算法設計與分析>回溯法判斷在當前擴展節(jié)點處是否已得到可行解假設現(xiàn)在有一列數(shù)a[0],a[1],...a[n-1]①如果一個問題的解的長度不是固定的，并且解和元素順序無關，即可以從中選擇0個或多個，那么解空間的個數(shù)將是為2n指數(shù)級,可以用子集樹來表示所有的解②如果解空間是由n個元素的排列形成，也就是說n個元素的每一個排列都是解空間中的一個元素，那么最后解空間的組織形式是排列樹175、子集樹與排列樹算法設計與分析>回溯法遍歷子集樹需O(2n)計算時間voidbacktrack(intt){if(t>n)output(x);elsefor(inti=0;i<=1;i++){x[t]=i;if(constraint(t)&&bound(t))backtrack(t+1);}}18（1）子集樹算法設計與分析>回溯法當所給出的問題是從n個元素的集合S中找到滿足某種性質的子集時，解空間稱為子集樹19算法設計與分析>回溯法當所給出的問題是確定n個元素滿足某種性質的排列時，解空間稱為排列樹遍歷排列樹需O(n!)計算時間voidbacktrack(intt){if(t>n)output(x);elsefor(inti=t;i<=n;i++){

swap(x[t],x[i]);if(constraint(t)&&bound(t))backtrack(t+1);swap(x[t],x[i]);}}執(zhí)行回溯前,先將變量數(shù)組初始化為單位排列（2）排列樹算法設計與分析>回溯法>裝載問題5.2裝載問題1.問題描述:n個集裝箱裝到2艘載重量分別為c1,c2的貨輪,其中集裝箱i的重量為wi且

.

問題要求找到一個合理的裝載方案可將這n個貨箱裝上這2艘輪船。例如:當n=3,c1=c2=50,若w=[10,40,50],有解;若w=[20,40,40],問題無解.2021算法設計與分析>回溯法>裝載問題當時,問題等價子集和問題;采用動態(tài)規(guī)劃求解,其時間復雜性為:O(min{C1,2n}

)若裝載問題有解,采用如下策略可得一個最優(yōu)裝載方案:(1)將第一艘輪船盡可能裝滿;(2)將剩余的貨箱裝到第二艘船上。將第一艘船盡可能裝滿等價于如下0-l背包問題:xi{0,1},1in算法設計與分析>回溯法>裝載問題用子集樹表示解空間,則解為n元向量{x1,...,xn},

xi{0,1}

由于是最優(yōu)化問題:當cw>c1,該結點為根結點的子樹都不滿足約束條件，可利用此條件進一步剪去不含最優(yōu)解的子樹

。

2、回溯算法思路22當前裝載量算法設計與分析>回溯法>裝載問題例如n=4,c1=12,w=[8,6,2,3].bestw初值=0;23不滿足約束條件

算法設計與分析>回溯法>裝載問題template<classType>TypeMaxloading(typew[],typec,intn)loading<Type>X；

//初始化XX.w=w;//集裝箱重量數(shù)組

X.c=c;//第一艘船載重量

X.n=n；//集裝箱數(shù)

X.bestw=0;//當前最優(yōu)載重

X.cw=0;//當前載重量

//計算最優(yōu)載重量

X.Backtrack(1)；

returnX.bestw；}算法復雜性:O(2n)24調用遞歸函數(shù)Backtrack(1)實現(xiàn)回溯搜索25算法設計與分析>回溯法>裝載問題Backtrack(i)搜索子集樹中第i層子樹。i≤n,當前擴展節(jié)點Z是子集樹中的內部結點;該結點有以下兩種情況:x[i]=1:進入左兒子,

cw+wj+1c1,對左子樹遞歸搜索x[i]=0:進入右兒子,總是可行,不檢查i>n時,算法搜索至葉結點,其相應裝載重量為cw,如果cw>bestw,更新bestw=cw約束函數(shù)26算法設計與分析>回溯法>裝載問題template<classType>voidLoading<Type>::Backtrack(inti){//搜索第i層結點

if(i>n){//到達葉結點

if(cw>bestw)

bestw=cw；

return；}

//搜索子樹

if(cw+w[i]]<=c){

//x[i]=1cw+=w[i]；

Backtrack(i+1)；

cw-=w[i]};

Backtrack(i+1)；

//x[i]=0}Backtrack(i)搜索子樹集中第i層子樹左子樹右子樹回溯過程27設bestw:當前最優(yōu)載重量,(某個葉節(jié)點)cw=:當前擴展結點的載重量

;r=:剩余集裝箱的重量;當cw+r(限界函數(shù))≤bestw時,將cw對應的子樹剪去。cw+r≤bestw+wj+1>c1剪枝條件:算法設計與分析>回溯法>3、加入上界函數(shù)算法設計與分析>回溯法>裝載問題例如n=4,c1=12,w=[8,6,2,3].bestw初值=0;28不滿足上界函數(shù)

template<classType>TypeMaxloading(typew[],typec,intn,)loading<Type>X；

//初始化XX.w=w;//集裝箱重量數(shù)組

X.c=c;//第一艘船載重量

X.n=n；//集裝箱數(shù)

X.bestw=0;//當前最優(yōu)載重

X.cw=0;//當前載重量

X.r=0;//剩余集裝箱重量

for(inti=1;i<=n;i++)X.r+=w[i]//計算最優(yōu)載重量

X.Backtrack(1)；

returnX.bestw；}29算法設計與分析>回溯法>裝載問題30voidLoading<Type>::Backtrack(inti){//搜索第i層結點

if(i>n){//到達葉結點

bestw=cw;

return；}

//搜索子樹

r-=w[i];if(cw+w[i]]<=c){

//x[i]=1,搜索左子樹cw+=w[i]；x[i]=1

;

Backtrack(i+1)；

cw-=w[i]};

if(cw+r>bestw){

//搜索右子樹

x[i]=0;Backtrack(i+1)}；

r+=w[i];}引入上界函數(shù),剪去不含最優(yōu)解的子樹,改進算法效率算法設計與分析>回溯法>裝載問題314、構造最優(yōu)解算法設計與分析>回溯法>裝載問題增加兩個私有成員：

x：記錄從根到當前結點的路徑int*x;

bestx：記錄當前最優(yōu)解int*bestx;初始化：

X.x=newint[n+1];X.bestx=bestx;Backtrack(inti){if(i>n){//在葉節(jié)點上

for(intj=1;j<=n;j++)

bestx[j]=x[j];//最優(yōu)解

bestw=cw;

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

//x[i]=1,搜索左子樹cw+=w[i]；x[i]=1

;

Backtrack(i+1)；

cw-=w[i]};if(cw+r>bestw){

//搜索右子樹

x[i]=0;

Backtrack(i+1)}；

r+=w[i];}32算法設計與分析>回溯法>裝載問題算法設計與分析>回溯法>5.3

批處理作業(yè)調度[問題描述]給定n個作業(yè)的集合J=(1,2,...,n)。每一作業(yè)i

須先由機器l處理,再由機器2處理.設tji是在機器j上處理作業(yè)i的時間,i=1,...,n,j=1,2.Fji是在機器j上完成作業(yè)i的時間.所有作業(yè)在機器2上完成時間和:f=∑F2i.對于給定J,制定一最佳作業(yè)調度方案,使完成時間和最小.3334[問題想法]：顯然，批處理作業(yè)的一個最優(yōu)調度應使機器1沒有空閑時間，且機器2的空閑時間最小?？梢宰C明，存在一個最優(yōu)作業(yè)調度使得在機器1和機器2上作業(yè)以相同次序完成。解空間E={x1,...,xn},

xi{1,..n},

約束條件:當ij,xi

xj(元素不能重復選取)

限界函數(shù):bestf:為當前最小完成時間和f:當前作業(yè)k的完成時間;當f>bestf時,將k對應的子樹剪去

算法設計與分析>回溯法>算法設計與分析>回溯法>作業(yè)調度intFlow(int**M,intn,intbestx[]){intub=32767;

INT_MAXFlowshopX;X.x=newint[n+1];

//當前調度

X.f2=newint[n+l];

//機器2的完成時間X.M=M;

//各作業(yè)所需處理時間

X.n=n;

//作業(yè)數(shù)

X.bestx=bestx;

//當前最優(yōu)調度

X.bestf=ub;

//當前最優(yōu)調度時間

X.fl=0;

//機器1完成處理時間

X.f=0;

//完成處理時間和

for(inti=0;i<=n;i++)

X.f2[i]=0,X.x[i]=i;X.Backtrack(1);delete[]X.x;delete[]X.f2;returnX.bestf;}算法復雜性:O(n!)3536Backtrack中:當i＞n時，算法搜索至葉結點，得到一個新的作業(yè)調度方案，此時算法適合更新當前最優(yōu)值和相應的當前最佳作業(yè)調度。當i<n時，當前擴展節(jié)點位于排列樹的第i-1層。此時算法選擇下一個要安排的作業(yè)，以深度優(yōu)先的方式遞歸地對相應子樹進行搜索。對于不滿足上界約束的節(jié)點，則剪去相應的子樹。算法設計與分析>回溯法>作業(yè)調度37voidFlowshop::Backtrack(inti){if(i>n){for(intj=1;j<=n;j++)bestx[j]=x[j];bestf=f;}elsefor(intj=i;j<=n;j++){fl+=M[x[j]][1];f2[i]=((f2[i-1]>fl)?f2[i-1]:fl)+M[x[j]][2];f+=f2[i];if(f<bestf){Swap(x[i],x[j]);Backtrack(i+1);

Swap(x[i],x[j]);

}fl-=M[j]][1];f-=f2[i];}}算法設計與分析>回溯法>作業(yè)調度葉結點當前擴展結點限界函數(shù)385.4符號三角形問題一、問題描述二、問題分析三、算法描述算法設計與分析>回溯法>391、問題描述右圖是由14個“+”和14個“-”組成的符號三角形。2個同號下面都是“+”，2個異號下面都是“-”。在一般情況下，符號三角形的第一行有n個符號。符號三角形問題要求對于給定的n，計算有多少個不同的符號三角形，使其所含的“+”和“-”的個數(shù)相同。++-+-+++----+-+++--++--+---+算法設計與分析>回溯法>402、問題分析定義：用n元組x[1:n]表示符號三角形的第一行。當x[i]=1,表示符號三角形的第一行的第i個符號為“+”當x[i]=0,表示符號三角形的第一行的第i個符號為“-”使用回溯法解決符號三角形問題用一棵完全二叉樹表示其解空間.算法設計與分析>回溯法>子樹集41可行性約束函數(shù)：當前符號三角形所包含的“+”個數(shù)與“-”個數(shù)均不超過n*(n+1)/4無解的判斷：n*(n+1)/2為奇數(shù)

復雜度分析：計算可行性約束需要O(n)時間，在最壞情況下有O(2n)個結點需要計算可行性約束，故解符號三角形問題的回溯算法所需的計算時間為O(n2n)。算法設計與分析>回溯法>三角形中+-號總數(shù)為n(n+1)/242P[1:t]p[2][t]p[3][t-1]……p[1][t+1]算法設計與分析>回溯法>說明：符號三角形距陣定義為**p；已知深度t的三角形距陣P[1:t]，只需要確定p[1][t+1]的值，就能在已確定的三角形的右邊加一條邊擴展P[1:t+1]433、算法描述voidTriangle::Backtrack(intt){if((count>half)||(t*(t-1)/2-count>half))return;

//加或減號個數(shù)大于符號總數(shù)的一半if(t>n)

sum++;

//找到一個符合條件的三角形elsefor(inti=0;i<2;i++){

//i=1為”+”，i=0為”-”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;}}算法設計與分析>回溯法>n:第一行符號個數(shù)half:為n(n+1)/4count:“+”個數(shù)**p:符號三角矩陣sum:符號三角形數(shù)計算新增的最后一斜列的+和-號個數(shù)44八皇后問題是十九世紀著名的數(shù)學家高斯于1850年提出的。問題：在8×8的棋盤上擺放八個皇后，使其不能互相攻擊，即任意兩個皇后都不能處于同一行、同一列或同一斜線上。把八皇后問題擴展到n皇后問題，即在n×n的棋盤上擺放n個皇后，使任意兩個皇后都不能處于同一行、同一列或同一斜線上。算法設計與分析>回溯法5.5八皇后問題4512341234皇后1皇后2皇后3皇后4圖

四皇后問題四皇后問題四皇后問題的解空間樹是一個完全4叉樹樹的根結點表示搜索的初始狀態(tài)從根結點到第2層結點對應皇后1在棋盤中第1行的可能擺放位置，從第2層結點到第3層結點對應皇后2在棋盤中第2行的可能擺放位置，依此類推。算法設計與分析>回溯法46想法:棋盤的每一行上可以而且必須擺放一個皇后，所以，n皇后問題的可能解用一個n元向量X=(x1,x2,…,xn)表示，其中，1≤i≤n并且1≤xi≤n，即第i個皇后放在第i行第xi列上。由于兩個皇后不能位于同一列上，所以，解向量X必須滿足約束條件：

xi≠xj算法設計與分析>回溯法皇后i,j不在同一列上47若兩個皇后擺放的位置分別是(i,xi)和(j,xj)，在棋盤上斜率為-1的斜線上，滿足條件i－j=xi－xj，在棋盤上斜率為1的斜線上，滿足條件i＋j=xi＋xj，綜合兩種情況，由于兩個皇后不能位于同一斜線上，所以，解向量X必須滿足約束條件：

|i－xi|≠|j－xj|算法設計與分析>回溯法皇后i,j不在同一斜線上48算法設計與分析>回溯法算法：回溯法求解n皇后問題1.初始化解向量x[n]={-1};2.

k=1;3.

while(k>=1)3.1把皇后擺放在下一列位置，x[k]++;3.2從x[k]開始依次考察每一列，如果不發(fā)生沖突，則轉向步驟3.3；否則x[k]++試探下一列；3.3若n個皇后已全部擺放，輸出一個解，結束；3.4若尚有皇后沒擺放，則k++,轉向步驟3,擺放下一皇后；3.5若x[k]出界，則回溯：x[k]=-1,k--;轉步驟3重新擺放k皇后；4.退出循環(huán)，無解。算法設計與分析>回溯法>最大團問題

最大團問題的回溯算法intMaxClique(int**a,intv[i],intn){ CliqueY; Y.x=newint[n+l]; Y.a=a;//圖G的鄰接矩陣

Y.n=n;//圖G頂點數(shù)

Y.cn=0;//當前團頂點數(shù)

Y.bestn=0;//當前最大團頂點數(shù)

Y.bestx=v;//當前最優(yōu)解

Y.Backtrack(1); delete[]Y.x; returnY.bestn；

}49voidclique::Backtrack(inti){if(i>n)

//找到更大團,更新

{for(intj=1;j<=n；j++)bestx[j]=x[j]; bestn=cn; return;

}

//檢查頂點i是否與當前團相連

intOK=1;

//滿足加入團的條件

for(intj=1;j<=i;j++)if(x[j]&&a[i][j]==0)

//i不與j相連，剪左枝

{OK=0;break;}if(OK)//向左枝遞歸

{x[i]=1;//把i加入團

cn++; Backtrack(i+1); x[i]=0;cn--;}

//回溯到i，為進入右子樹做準備

if(cn+n-i>bestn)

//剪右枝條件，否則向右枝遞歸

{ X[i]=0；Backtrack(i+1);}}設當前擴展節(jié)點Z位于解空間樹的第i層，在進入左子樹之前，必須確認從頂點i到已入選的頂點集中每一個頂點都有邊相連。在進入右子樹之前，必須確認還有足夠多的可選擇的頂點使算法有可能在右子樹中找到更大的團。復雜度分析：回溯算法backtrack所需的計算時間顯然為O(n2n)。算法設計與分析>回溯法

>著色問題圖的m色判定問題:給定無向連通圖G和m種顏色。用這些顏色為圖G的各頂點著色.問是否存在著色方法,使得G中任2鄰接點有不同顏色。圖的m色優(yōu)化問題:給定無向連通圖G,為圖G的各頂點著色,使圖中任2鄰接點著不同顏色,問最少需要幾種顏色。所需的最少顏色的數(shù)目m稱為該圖的色數(shù)。5.8圖的m著色問題

問題描述5152可平面圖：如果一個圖得所有頂點和邊都能用某種方式畫在平面上，且沒有任何兩面相交，則稱這個圖為可平面圖。4色定理：若圖G是可平面圖,則它的色數(shù)不超過4色4色定理的應用:在一個平面或球面上的任何地圖能夠只用4種顏色來著色使得相鄰的國家在地圖上著有不同顏色4321512345算法設計與分析>回溯法>著色問題a).將G的結點按照度數(shù)遞減的次序排列.b).用第一種顏色對第一個結點著色,并按照結點排列的次序對與前面著色點不鄰接的每一點著以相同顏色.c).用第二種顏色對尚未著色的點重復步驟b).用第三種顏色繼續(xù)這種作法,直到所有點著色完為止.

任意圖的著色WelchPowell法算法設計與分析>回溯法>著色問題53算法設計與分析>回溯法>著色問題設圖G=(V,E),|V|=n,顏色數(shù)=m,用鄰接矩陣a表示G,用整數(shù)1,2…m來表示m種不同的顏色。頂點i所著的顏色用x[i]表示。問題的解向量可以表示為n元組x={x[1],...,x[n]}.x[i]{1,2,...,m},解空間樹為排序樹,是一棵n+1層的完全m叉樹.約束條件:x[i]x[j],如果a[j][i]=1.

(如果兩點相鄰,不能著同色)算法思路54算法設計與分析>回溯法>著色問題intmColoring(intn,intm,int**a){ColorX；

//初始化XX．n=n；//圖的頂點數(shù)

X．m=m//可用顏色數(shù)

X．a(chǎn)=a；//圖的鄰接矩陣

X．Sum=0;//已找到的著色方案數(shù)

int*p=newint[n+1]；

for(inti=0；i<=n；i++)p[i]=0；

X.x=p//當前解；

X.Backtrack(1)；

delete[]p；

returnX．sum；}5556boolColor::Ok(intk){//檢查顏色可用性，即約束條件

for(intj=1；j<=n；j++)if((a[k][j]==1)＆＆(x[j]==x[k])) returnfalse；

returntrue；

}算法設計與分析>回溯法>著色問題判斷顏色是否可用的Ok方法57算法設計與分析>回溯法>著色問題Backtrack函數(shù)中：當i>n時，算法搜索至葉結點，得到新的m著色方案，當前找到的可m著色的方案數(shù)sum加一.當i≤n時，當前擴展結點Z是解空間中的內部結點。該結點有x[i]=1,2,……,m共m個兒子結點。對當前擴展結點Z的每一個兒子結點，由函數(shù)OK檢查其可行性，并以深度優(yōu)先遞歸地對可行的子樹進行搜索，或減去不可行的子樹voidColorbacktrack(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);

}}算法復雜性:58算法設計與分析>回溯法>著色問題5.9旅行售貨員問題旅行商問題的解空間是一個排列樹。如果以x=[1,2,?,n