計算理論與算法分析設計課件：搜索法

搜索法

2024/7/52

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

(1)窮舉搜索(Exhaustive

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

(Backtracking);-廣度優(yōu)先搜索(BFS);-分枝限界法(Branch&Bound);-博弈樹搜索(α-βSearch)(3)啟發(fā)式搜索(HeuristicSearch)2024/7/53

of158方法概述:搜索算法介紹（續(xù)）搜索空間的三種表示

-表序表示:搜索對象用線性表數(shù)據(jù)結構表示;-顯式圖表示:搜索對象在搜索前就用圖(樹)的數(shù)據(jù)結構表示;-隱式圖表示:除了初始結點,其他結點在搜索過程中動態(tài)生成.緣于搜索空間大,難以全部存儲.2024/7/54

of158方法概述:搜索算法介紹（續(xù)）提高搜索效率的思考：隨機搜索

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

of158組合爆炸一張充分大的普通紙對折40次：

高度超過5千座珠穆朗瑪峰一張充分大的普通紙對折50次：月地距離的128倍一個問題有n個變量,k個選擇,則遍歷空間的大小為kn

并行處理也不可能克服和繞過組合爆炸；但并行處理可能是當前提高求解規(guī)模的最好和現(xiàn)實的途徑。2024/7/56

of158世界紀錄:2^132011年，15名學生和教師利用長度超過2英里=3218米的衛(wèi)生紙和MIT的無盡長廊(無盡長廊是連接MIT主建筑群的走廊，長度為825英尺=251.46米，不用再擔心廁紙會被風吹走)，創(chuàng)造了紙張連續(xù)對半折疊的新世界紀錄——13次，打破了2002年的舊記錄——12次。連續(xù)向同一方向對折13次相當于疊出8192（2^13）層。數(shù)學教師、廁紙折疊高手Tanton表示，這相當于攀登珠穆朗瑪峰。2024/7/57

of158世界紀錄:2^132024/7/58

of158一、寬度優(yōu)先搜索法BreadthFirstSearch(BFS)寬度優(yōu)搜索法：逐層地對結點進行擴展。例：重排九宮問題：在3Х3的方格棋盤上放置分別標有數(shù)字1，2，3，···，8的八張牌，初始狀態(tài)為S0，目標狀態(tài)為St28314765S0

12384765St2024/7/59

of1582834765S01283

1

4765223

8

47653283

476542836

4755

832147652837

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)2024/7/510

of158

優(yōu)點：只要問題有解，用寬度優(yōu)先搜索法一定可以得到解，而且得到的是路徑最短的解。缺點：盲目性較大。當目標結點距離初始結點較遠時將會產生許多無用結點，搜索效率低。2024/7/511

of158二、深度優(yōu)先搜索法DepthFirstSearch(DFS)深度優(yōu)搜索法：縱深地對結點進行擴展。2024/7/512

of158St2834765S01283

14765223

8476511283

4765283

6475

832147652837

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:St2024/7/513

of158搜索一旦進入某個分支，就將沿著該分支一直向下搜索。如果目標結點恰好在此分支上，則可較快地得到解。但如果目標結點不在此分支上，而該分支又是一個無窮分支，則就不可能得到解。所以深度優(yōu)先搜索是不完備的。2024/7/514

of158（二）、有界深度優(yōu)先搜索法解決深度優(yōu)先搜索不完備的問題，引入搜索深度的界限（設為dm），當搜索深度達到了深度界限，而尚未出現(xiàn)目標結點，就換一個分支進行搜索。2024/7/515

of158

123452024/7/516

of158三、啟發(fā)式搜索法估價函數(shù)：用于估價結點重要性的函數(shù)。一般形式：f(x)=g(x)+h(x)其中：g(x)為從初始結點Si到結點x已經(jīng)付出的代價；h(x)是從結點x到目標結點St的最優(yōu)路徑的估計代價，它體現(xiàn)了問題的啟發(fā)性信息。g(x)：表示結點x的深度；h(x)：表示結點x的格局與目標結點格局不相同的牌數(shù)。2024/7/517

of15828314765283147652318476528314765283164753

8321476528371465

23184765231847654455564612384765412384765分支限界法

2024/7/519

of158Branch&Bound例：用分支限界法求解分配問題分配問題：設有n個人，每個人都可以完成n種不同的任務，但所需時間不同。如果只需一人去完成每一項工作，則應如何分配n個人并使完成所有n項工作的總時間為最小。2024/7/520

of158可行解：滿足以下約束條件：分配一人且僅一人去做每項工作的解稱為分配問題的可行解考慮n=4的情況。 A,B,C,D四個人分別完成1、2、3、4。這時問題有4！=24個可行解2024/7/521

of158人工作1234A21097B154148C13141611D4

15139

2024/7/522

of158人1234

A21097

B154148

C13141611

D4

1513922A做1B做1C做1D做1274133243624342831A做2B做2C做2A做3C做3283739B做2C做2D做2A→3,B→2,C→4,D→1,總時間為282024/7/523

of158四、α-β剪枝術7651有7根火柴，A,B兩人依次從中取出1根或2根，不能不取也不能取多于2根，最后一個將火柴取盡的就是勝利者。用符號表示輪到A時有m1根火柴的狀態(tài),用表示輪到B時有m2根火柴的狀態(tài)，雙方對弈假定從A開始。用1表示A取勝，用-1表示B取勝。m1m22024/7/524

of158小游戲：給出自然數(shù)n，然后給出2n個自然數(shù)。如n=4時：7,9,3,6,4,2,5,3游戲雙方A和B，只允許從給定數(shù)列的兩端取數(shù)；A先?。蝗⊥旰笳l取得的數(shù)總和最大誰獲勝；若雙方的和相等，則判A勝，問A有必勝的策略嗎？回溯法

2024/7/526

of158

回溯法是一個既帶有系統(tǒng)性又帶有跳躍性的搜索算法。

它在包含問題的所有解的解空間樹中，按照深度優(yōu)先的策略，從根結點出發(fā)搜索解空間樹

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

這種以深度優(yōu)先的方式系統(tǒng)地搜索問題的解的算法稱為回溯法，它適用于解一些組合數(shù)較大的問題。2024/7/527

of158有三種結點：解空間樹：根結點（搜索的起點）中間結點（非終端結點）葉結點（終端結點），葉結點為解向量搜索過程就是找一個或一些特別的葉結點。2024/7/528

of158－搜索從開始結點（根結點）出發(fā)，以

DFS搜索整個解空間。－開始結點成為一個活結點，同時也成為當

前的擴展結點。在當前的擴展結點處向縱

深方向移至一個新結點，并成為一個新的

活結點，也成為當前擴展結點。－如果在當前的擴展結點處不能再向縱深方

向擴展，則當前擴展結點就成為死結點。－此時，應往回移動（回溯）至最近的一個

活結點處，并使這個活結點成為當前的擴

展結點；直至找到一個解或全部解。2024/7/529

of158start??deadenddeadend??deadenddeadend?success!deadend2024/7/530

of158算法的基本步驟1）針對問題，定義問題的解空間（對解進行編碼）；2）確定易于搜索的解空間組織結構（按樹或圖組織解）；3）以深度優(yōu)先方式搜索解空間，搜索過程中裁減掉死結點的子樹提高搜索效率。2024/7/531

of158例[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)2024/7/532

of158n=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)值為502024/7/533

of158貨郎擔問題：有4個頂點的貨郎擔問題，如圖所示，求從頂點1出發(fā)，最后回到頂點1的最短路線。1234206305410ABCDEFGHIJKLMNOPQ12343443423224232024/7/534

of158注解：（1）提高回溯法效率的二種方法①用約束函數(shù)剪去不滿足約束的子樹；②用限界函數(shù)剪去不能得到最優(yōu)解的子樹。（2）二類常見的解空間樹①子集樹：如0-1背包，葉結點數(shù)2n，總結點數(shù)2n+1，遍歷時間為Ω(2n)；②排列樹：如TSP問題，葉結點數(shù)n!，遍歷時間為Ω(n!)。2024/7/535

of158子集樹與排列樹0-1背包問題含有2n個葉結點旅行商問題含有(n-1)!個葉結點問：每個樹的葉結點數(shù)目是多少？2024/7/536

of158回溯算法的一般框架子集樹回溯算法

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

{//當前擴展結點為x[t]if(t>n)output(x);//葉結點是可行解，輸出解

elsewhile(allXt){//Xt為所有x[t]的合法取值集

x[t]=Xt中第i個值;if(Constraint(t)&&Bound(t))Backtrack(t+1);}}執(zhí)行時：Backtrack(1)//從1擴展并回溯2024/7/537

of158回溯算法的一般框架（續(xù)）排列樹回溯算法

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

{//當前擴展結點為x[t]if(t>n)output(x);//葉結點是可行解，輸出解

else

for(inti=t;i<=n;i++){swap(x[t],x[i]);if(Constraint(t)&&Bound(t))Backtrack(t+1);swap(x[t],x[i]);}}2024/7/538

of158

例（4后問題）設有一4*4的棋盤，把4個皇后放在棋盤上，要求滿足下列兩個條件：1）任意兩個皇后不在同一行上和同一列上；2）任意兩個皇后不在同一條對角線上；問有多少種放法？若用窮舉法，先不考慮這兩個條件，則有種方案。C(16,4)=18202024/7/539

of158下面首先給行、列和皇后都編號：放在第i行的皇后編號為i，以xi的下標i表示,而xi的值表示皇后i所處的列數(shù)，這樣4后問題的全部解向量可以寫成(x1,x2,x3,x4)的形式。顯式約束條件是Si={1，2，3，4}1≤i≤4若只考慮顯式約束條件，則解空間是由個四元組組成。44=256隱式條件有兩個：兩個皇后不在同一列上和不在同一對角線上。2024/7/540

of1581238134691114165710121517x1=118192429202225273032212326283133x1=2x2=2x3=3x4=4344242334232

這棵排列樹僅考慮了條件1）。這棵樹也叫做該問題的解空間。結點的編號是按深度優(yōu)先給出的。樹中的分支代表著解向量(x1,x2,x3,x4)的分量xi的取值。從根到葉子的所有路徑組成解空間。則有種方案。4!=242024/7/541

of158QQХХQQQХХХХQQХQХХХХQQХ12347568109x1=1x2=23424233BBBBB2024/7/542

of15812347568109x1=1x2=23424233BBBBB111213141516x1=2BB134132024/7/543

of158n后問題

在同一條對角線的條件|xi-xk|=|i-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;

}

2024/7/544

of158算法：求n后問題的所有解voidnqueens(int

n,intx[])

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

while(k>0){

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

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

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

if(x[k]<=n){

if(k==n)break;

else{k=k+1;x[k]=0;}

}

else{x[k]=0;k=k-1;}

}

}2024/7/545

of158n皇后問題的任意解構造法一、當n%6!=2且n%6!=3時，有一個解為：2,4,6,8,...,n,

1,3,5,7,...,n-1(n為偶數(shù))

2,4,6,8,...,n-1,

1,3,5,7,...,n(n為奇數(shù))

(上面序列第i個數(shù)為ai，表示在第i行ai列放一個皇后；...省略的序列中，相鄰兩數(shù)以2遞增。下同)例如4后問題因為4%6!=2,3，所以有一個解為：2,4,1,32024/7/546

of158n皇后問題的任意解構造法二、當n%6==2或n%6==3時，

(當n為偶數(shù),k=n/2；當n為奇數(shù),k=(n-1)/2)

k,k+2,k+4,...,n,－2,4,...,k-2,－k+3,k+5,...,n-1,－1,3,5,...,k+1

(k為偶數(shù),n為偶數(shù))

k,k+2,k+4,...,n-1,－2,4,...,k-2,－k+3,k+5,...,n-2,－1,3,5,...,k+1,n

(k為偶數(shù),n為奇數(shù))

k,k+2,k+4,...,n-1,－1,3,5,...,k-2,－k+3,...,n,－2,4,...,k+1

(k為奇數(shù),n為偶數(shù))

k,k+2,k+4,...,n-2,－1,3,5,...,k-2,－k+3,...,n-1,－2,4,...,k+1,n

(k為奇數(shù),n為奇數(shù))poj3239－SolutiontothenQueensPuzzle

2024/7/547

of158回溯過程的效率回溯過程的效率依賴于四個因素：1）產生一個x(k)的時間；2）滿足顯式約束條件的x(k)的個數(shù)；3）限界函數(shù)的計算時間；4）滿足限界函數(shù)的x(k)的個數(shù)。在決定采用回溯法正式求解某問題之前，應先估計一下回溯法在此情況下的效率。2024/7/548

of158用回溯法去處理一實例所要生成的結點數(shù)，一般是采用在狀態(tài)空間樹中生成一條隨機路徑的方法估計。2024/7/549

of1581ХХ2ХХХХ3Х4ХХХХХХХ5ХХХХХХХХХХХ1+8+8*6+8*6*4+8*6*4*3+8*6*4*3*2=1977根2024/7/550

of1581ХХХ2Х3ХХХХХХХХХ4Х5ХХХХХХХХХ6ХХХХХХХХХХХ7ХХХХ8ХХХ

1+8+8*5+8*5*3+8*5*3*2+8*5*3*2*2+8*5*3*2*2*1+8*5*3*2*2*1*1+8*5*3*2*2*1*1*1

=23292024/7/551

of1582024/7/552

of158裝載問題有一批共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]2024/7/553

of158問題分析容易證明，如果一個給定裝載問題有解，則采用下面的策略可得到最優(yōu)裝載方案：(1)首先將第一艘輪船盡可能裝滿；(2)將剩余的集裝箱裝上第二艘輪船。2024/7/554

of158將第一艘輪船盡可能裝滿等價于選取全體集裝箱的一個子集，使該子集中集裝箱重量之和最接近C1。由此可知，裝載問題等價于特殊的0-1背包問題。2024/7/555

of158解空間：子集樹可行性約束函數(shù)(選擇當前元素)：2024/7/556

of158裝載問題算法描述voidbacktrack(inti){//搜索第i層結點

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

x[i]=1;

cw+=w[i];

backtrack(i+1);

cw-=w[i];}

backtrack(i+1);}2024/7/557

of158限界函數(shù)：用于剪去不含最優(yōu)解的子樹，從而提高算法在平均情況下的運行效率。設Z是解空間樹第i層上的當前擴展結點，cw是當前載重量，R是剩余集裝箱的重量，besetW是當前最優(yōu)載重量，則當

cw+r≤bestW時，剪去Z的右子樹。2024/7/558

of158裝載問題改進算法描述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];}2024/7/559

of158練習:子集和問題問題給定由n個不同正整數(shù)組成的集合W={wi}，和正整數(shù)M，求W中所有和等于M的子集的集合。例如n=5,M=20,

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

2024/7/560

of158批處理作業(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è)調度方案，使其完成時間和達到最小。2024/7/561

of158實例分析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。2024/7/562

of158算法設計因為我們要從n個作業(yè)的所有排列中找出最小完成時間和的最小調度問題，所以批處理作業(yè)調度問題的解空間是一顆排列樹。2024/7/563

of158批處理作業(yè)調度解空間：排列樹classFlowshop{friendFlow(int**,int,int[]);voidBacktrack(inti);

int**M,//作業(yè)所需處理時間

*x,//當前作業(yè)調度

*bestx,//當前最優(yōu)作業(yè)調度

*f2,//機器2完成處理時間

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

f,//完成時間和

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

n;//作業(yè)數(shù)};2024/7/564

of158批處理作業(yè)調度voidFlowshop::Backtrack(inti){if(i>n){for(intj=1;j<=n;j++)

bestx[j]=x[j];

bestf=f;}else2024/7/565

of158for(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];

2024/7/566

of158算法效率解空間：排列樹復雜性：在最壞情況下，整個算法的計算時間復雜性為T(n)=O(n!)。2024/7/567

of1580-1背包問題解空間：子集樹可行性約束函數(shù)：∑wixi≤C限界函數(shù)：Bound()2024/7/568

of1580-1背包問題template<classTypew,classTypep>TypepKnap<Typew,Typep>::Bound(inti){//計算上界

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

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

while(i<=n&&w[i]<=cleft){cleft-=w[i];b+=p[i];i++;}//裝滿背包

if(i<=n)b+=p[i]/w[i]*cleft;returnb;}2024/7/569

of158voidbacktrack(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);}}2024/7/570

of1582024/7/570

of1580/1背包問題

且

2024/7/571

of158載重量50，物體5,15,25,27,30，價值12,30,44,46,50。2024/7/572

of158符號三角形問題++-+-+++----+-+++--++--+---+下圖是由14個“+”和14個“-”組成的符號三角形。2個同號下面都是“+”，2個異號下面都是“-”。在一般情況下，符號三角形的第一行有n個符號。符號三角形問題要求對于給定的n，計算有多少個不同的符號三角形，使其所含的“+”和“-”的個數(shù)相同。2024/7/573

of158符號三角形問題解向量：用n元組x[1:n]表示符號三角形的第一行?？尚行约s束函數(shù)：當前符號三角形所包含的“+”個數(shù)與“-”個數(shù)均不超過n*(n+1)/4無解的判斷：n*(n+1)/2為奇數(shù)privatestaticvoidbacktrack(intt){

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

if(t>n)sum++;

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;}}++-+-+++----+-+++--++--+---+2024/7/574

of158算法效率解空間：子集樹復雜性：計算可行性約束需要O(n)時間，在最壞情況下有O(2n)個結點需要計算可行性約束，故解符號三角形問題的回溯算法所需的計算時間為O(n2n)。2024/7/575

of158最大團問題完全子圖：給定無向圖G=(V，E)。如果U

V，且對任意u，v

U有(u，v)

E，則稱U是G的完全子圖。團：G的完全子圖U是G的團當且僅當U不包含在G的更大的完全子圖中。G的最大團：是指G中所含頂點數(shù)最多的團。2024/7/576

of158例子12354{1,2}是G的一個大小為2的完全子圖，它不是團。因為它包含于G的更大的完全子圖{1,2,5}之中。{1,2,5},{1,4,5},{2,3,5}分別是G的最大團。G的最大團？2024/7/577

of158基本概念空子圖：如果U

V且對任意u，v

U有(u，v)

E，則稱U是G的空子圖。12354{2,4}是G的一個空子圖。2024/7/578

of158基本概念(續(xù))獨立集：G的空子圖U是G的獨立集當且僅當U不包含在G的更大的空子圖中。G的最大獨立集：是G中所含頂點數(shù)最多的獨立集。12354{2,4}是G的一個最大獨立子集。2024/7/579

of158基本概念(續(xù))補圖：對于任一無向圖G=(V，E)其補圖=(V1，E1)定義為：V1=V，且(u，v)

E1當且僅當(u，v)

E。12354123542024/7/580

of158例子12354{1，2}是的一個空子圖