算法設計與分析：搜索方法

算法設計與分析基本思想與分治策略，動態(tài)規(guī)劃，貪心法相比，搜索算法不需要進行子問題劃分，也沒有直接的遞推公式的求解，它在狀態(tài)空間圖中一步一步地探索問題的解搜索算法是一種通用的問題求解方法：首先把問題表示轉換為一個狀態(tài)空間圖，然后設計特定的圖遍歷方法在狀態(tài)空間中搜索問題的解

為了提高搜索的效率，在遍歷狀態(tài)空間時需要添加優(yōu)化技術，比如剪枝策略用于盡可能避免不必要的無效搜索，啟發(fā)式信息用來加速朝目標狀態(tài)逼近的速度狀態(tài)空間圖狀態(tài)圖：如果把狀態(tài)定義為圖的結點，操作符定義為圖的邊，一個問題的全部可能狀態(tài)則可以表示為一個圖，即狀態(tài)圖。

操作符（運算符）：是指把一個狀態(tài)轉換為另外一個狀態(tài)的操作或者運算。操作符可以是規(guī)劃，數(shù)學運算等。路徑：通過操作符序列連接起來的狀態(tài)圖中的一個狀態(tài)序列。路徑耗散函數(shù)：定義在路徑上的一個數(shù)值函數(shù)，它反映了一條路徑的性能度量或者求解問題的代價。在求解最優(yōu)化問題時，路徑耗散函數(shù)往往與優(yōu)化目標相關聯(lián)。狀態(tài)空間圖狀態(tài)空間圖可以形式化地定義為一個四元組（S，A，G，F(xiàn)）S表示問題的初始狀態(tài)，它是搜索的起點。A是采取的操作符集合，初始狀態(tài)和操作符隱含地定義了問題的狀態(tài)圖。G表示目標測試，它判斷給定的狀態(tài)是否為目標狀態(tài)。它可以是表示目標狀態(tài)的一個狀態(tài)集合，也可以是一個判定函數(shù)。F代表路徑耗散函數(shù)，它的定義需要具體問題具體分析。

搜索就是在狀態(tài)空間圖中從初始狀態(tài)出發(fā)，執(zhí)行特定的操作，試探地尋找目標狀態(tài)的過程。當然，也可以從目標結點到初始結點反向進行。狀態(tài)空間圖中從初始狀態(tài)到目標狀態(tài)的路徑則代表問題的解。解的優(yōu)劣由路徑耗散函數(shù)量度，最優(yōu)解就是路徑耗散函數(shù)值最小的路徑。狀態(tài)空間圖【例】傳教士渡河問題：在河的左岸有三個傳教士、一條船和三個野人，傳教士們想用這條船將所有的成員都運過河去，但是受到以下條件的限制：①教士和野人都會劃船，但船一次最多只能裝運兩個；②在任何岸邊野人數(shù)目都不得超過傳教士，否則傳教士就會遭遇危險：被野人攻擊甚至被吃掉。此外，假定野人會服從任何一種過河安排，試設計出一個確保全部成員安全過河的計劃。

狀態(tài)空間圖

狀態(tài)(m,c,b)狀態(tài)(m,c,b)狀態(tài)(m,c,b)狀態(tài)(m,c,b)S0331S8131S16330S24130S1321S9121S17320S25120S2311S10111S18310S26110S3301S11101S19300S27100S4231S12031S20230S28030S5221S13021S21220S29020S6211S14011S22210S30010S7201S15001S23200S31000表中的狀態(tài)并不全都是合法的狀態(tài)，可以刪除非法的狀態(tài)，從而加速搜索過程。搜索算法類型基于枚舉策略的搜索深度優(yōu)先搜索廣度優(yōu)先搜索優(yōu)化+枚舉的搜索回溯算法=深度優(yōu)先搜索+剪枝策略分支限界算法=廣度優(yōu)先搜索+剪枝策略啟發(fā)式搜索，啟發(fā)式搜索是一種基于規(guī)則的優(yōu)化搜索算法。深度優(yōu)先搜索（DFS）

DFS的搜索策略可以描述為“能進則進，不進再換，無換則退”。深度優(yōu)先搜索（DFS）【例】給定一個有向圖G=（V，E），如下圖所示，給出該圖深度優(yōu)先搜索的一個訪問序列。Demo深度優(yōu)先搜索（DFS）functionDFS(problem,stack)

//stack初始化為空node=Make-Node(Initial-State[problem]);//生成初始結點

stack←Insert(node,stack);

//棧中插入初始結點

do

while(1)

if

stack==Empty

return

failure;

//沒有搜索到目標狀態(tài)

node←Remove-First(stack);

//取出棧頂元素

visit(node);

//訪問棧頂元素

if

State[node]==Goal

//目標測試

return

Solution(node)

//搜索到目標狀態(tài)

sonNodes=Expend(node,problem);

//擴展node

stack←Insert-All(sonNodes,stack);//全部未訪問子結點加入?；跅５腄FS算法框架：深度優(yōu)先搜索（DFS）functionDFS(problem,node)if

State[node]==Goal/Failure//遞歸出口

return

Solution(node);else

visit(node);

//訪問當前結點for(iteratorsonNode=Init(node);sonNode<=Last(node);sonNode++)

if

notVisited(sonNode)DFS(sonNode);//遞歸遍歷其子樹return;基于遞歸的DFS算法框架：注解：for循環(huán)用于擴展node的所有未訪問子結點，并依次遞歸調(diào)用，其中Init表示node的第一個子結點，Last表示最后一個子結點。廣度優(yōu)先搜索（BFS）

BFS是以v為起始點，由近至遠，依次訪問和v有路徑相通的結點。通俗地講，BFS的搜索策略是“由近及遠，按層展開”。廣度優(yōu)先搜索（BFS）【例】給定一個有向圖G=（V，E），如圖7-3a所示，給出該圖廣度優(yōu)先搜索的一個訪問序列。Demo廣度優(yōu)先搜索（BFS）functionBFS(problem,queue)

//queue初始化為空node=Make-Node(Initial-State[problem]);//生成初始結點

queue←Insert(node,queue);

//隊列中加入初始結點

do

while(1)

if

queue==Empty

returnfailure

node←Remove-First(queue)

//取出隊列的頭部結點

visit(node);

//訪問當前結點

if

State[node]==Goal

//目標測試

return

Solution(node)

//搜索到目標狀態(tài)，返回解

sonNodes=Expend(node,problem);

//生成node的未訪問子結點

queue←Insert-All(sonNodes,queue)

//依次插入所有子狀態(tài)基于隊列的BFS算法框架：回溯算法深度優(yōu)先搜索是一種依照“能進則進，不進再換，無換則退”的策略進行的枚舉算法，也就意味著它可能遍歷整個圖空間，導致算法效率不高。給定一個問題的狀態(tài)空間表示，設計搜索算法時需要考慮以下兩個事實：回溯算法=深度優(yōu)先搜索+剪枝策略并不是所有的狀態(tài)都是合法的狀態(tài)狀態(tài)空間不等于搜索空間回溯算法回溯算法需要定義問題的狀態(tài)空間圖，包括以下四個方面：

約束條件：X中每一個分量自身的取值約束；分量之間的取值約束。注意：約束條件是剪枝策略的基礎，需要深入分析和挖掘操作符集合：從一個狀態(tài)轉換到另外一個狀態(tài)的操作，在狀態(tài)空間圖中它構成邊集。問題解和解空間：問題的解可以認為是一類特殊的狀態(tài)，即目標狀態(tài)。對于問題的一個實例，所有滿足約束條件的解向量就構成該問題實例的解空間。注意：在回溯算法中，狀態(tài)空間圖并不是顯式地構造，也就是說，并沒有在內(nèi)存中生成一個完整的狀態(tài)空間圖。實際上，回溯算法只是根據(jù)初始狀態(tài)，目標狀態(tài)和操作符集合（它產(chǎn)生后續(xù)狀態(tài)），隱式地構造狀態(tài)空間圖?；厮菟惴ɑ厮菟惴ㄐ枰O計合適的剪枝策略，盡量避免不必要的搜索。常用的剪枝策略包括兩大類：約束函數(shù)剪枝：根據(jù)約束條件，狀態(tài)空間圖中的部分狀態(tài)可能是不合法的。因此，在狀態(tài)空間圖中以不合法狀態(tài)為根的子圖/子樹是不可能包含可行解的，故其子空間不需要搜索。通俗地講，約束函數(shù)剪枝可以剪除狀態(tài)空間圖中的不可行解。

回溯算法─背包問題

1）問題的狀態(tài)表示

2）約束條件

回溯算法─背包問題

3）操作符

4）問題解和解空間

回溯算法─背包問題

深度優(yōu)先搜索算法遍歷整棵完全二叉樹，得到8個3維0-1解向量，然后統(tǒng)計最優(yōu)的裝包方案?；厮菟惴ㄌ砑恿思糁Σ呗裕M量避免不必要的搜索?；厮菟惴īけ嘲鼏栴}

ABCDJKELFMBestV=45BestV=50G約束函數(shù)剪枝：刪除不可行解限界函數(shù)剪枝：刪除非最優(yōu)解回溯算法─旅行商問題【例】某商人要到若干城市去推銷商品，已知各城市之間的旅行費用，他要選定一條從駐地出發(fā)，經(jīng)過每個城市一遍，最后回到駐地的路線，使總的費用最少。試構造下圖對應問題實例的最優(yōu)旅行方案。回溯算法─旅行商問題1）問題的狀態(tài)表示

2）約束條件

3）操作符

回溯算法─旅行商問題4）問題解和解空間給定{1,2,3,4}的一個排列都可以構造一個旅行商路徑解空間可以用一棵多叉樹來表示，亦稱為排列樹回溯算法─旅行商問題ABDEFICKJPA

約束函數(shù)剪枝：刪除不可行解限界函數(shù)剪枝：刪除非最優(yōu)解回溯算法回溯算法設計通常包含以下2個主要步驟：針對所給問題，定義問題的狀態(tài)空間圖。以深度優(yōu)先方式搜索狀態(tài)圖，并用剪枝策略避免無效搜索。//x是全局變量，記錄從根結點到當前結點的必要信息voidbacktrack(intt){

//t是遞歸深度if(t>n)

//遞歸出口，n表示遞歸的最大深度output(x);

//輸出問題的解else{for

(inti=Init(n,t);i<=Last(n,t);i++){

x[t]=Node(i);

//記錄當前子結點相關信息

if(constraint(x)&&bound(x))

//約束函數(shù)與限界函數(shù)

backtrack(t+1);

//遞歸調(diào)用，繼續(xù)深度優(yōu)先搜索}}注解：for循環(huán)體依次擴展當前結點的所有子結點，Init()和Last()是一種抽象表示，返回開始子結點和末尾子結點的編號。for循環(huán)執(zhí)行完畢則回溯到父結點。裝載問題把原問題簡化為一艘輪船的裝載問題。容易證明下述結論：如果一個給定裝載問題實例有解，則采用下面的策略可得到最優(yōu)裝載方案：(1)首先將第一艘輪船盡可能裝滿；(2)將剩余的集裝箱裝上第二艘輪船。問題分析裝載問題等價于以下特殊的0-1背包問題：問題分析問題的狀態(tài)表示約束條件操作符問題解和解空間

裝載問題─深度優(yōu)先搜索#defineMaxBox1000intglobalWeight[MaxBox],globalNum,globalC1;//輸入?yún)?shù)intglobalX[MaxBox],globalAns;//保存狀態(tài)X和最優(yōu)值的全局變量voidloadingDFS(intt){

if(t==globalNum){

//邊界條件，判定一個n維-1向量是否是可行解

intsumWeight1=0;

for(inti=0;i<globalNum;i++){sumWeight1+=globalX[i]*globalWeight[i];}//計算裝載量

if((sumWeight1<=globalC1)&&sumWeight1>globalAns)globalAns=sumWeight1;

//找到更優(yōu)的可行解

return;}//endofifglobalX[t]=1;loadingDFS(t+1);//擴展左子樹globalX[t]=0;loadingDFS(t+1);//擴展右子樹}010110011010108個狀態(tài)全部訪問一遍，選擇最大且小于C1的結果輸出裝載問題─回溯算法

左子結點

右子結點

裝載問題─回溯算法

右子結點

裝載問題─回溯算法

右子結點

左子結點

裝載重量的上限等于其父結點的上限裝載問題─回溯算法#defineMaxBox1000intglobalWeight[MaxBox],globalNum,globalC1;//輸入?yún)?shù)intglobalX[MaxBox];//保存狀態(tài)X的全局變量intglobalWt,globalBd,globalMaxWt;//保存中間量的全局變量voidloadingBacktrack(intt){

if(t==globalNum){

//邊界條件，得到一個C1的更好可行解globalMaxWt=globalWt;

return;}//endof(ifglobalBd-=globalWeight[t];

//擴展子結點時減少globalBd

if(globalWt+globalWeight[t]<=globalC1){//約束剪枝globalX[t]=1;globalWt+=globalWeight[t];

//增大globalWtloadingBacktrack(t+1);

//擴展左子樹globalWt-=globalWeight[t];

//回溯時恢復globalWt}

if(globalWt+globalBd>globalMaxWt){//限界剪枝globalX[t]=0;loadingBacktrack(t+1);

//擴展右子樹}globalBd+=globalWeight[t];//回溯時恢復globalBd}細節(jié)0101100110101050+0>010+40=500+10<5010+40=5050+40>500+80>500+40<500+40<5040+40>5040+0<50判斷條件：左子樹：globalWt+globalWeight[t]<=globalC1右子樹：globalWt+globalBd>globalMaxWtglobalMaxWt

=50t=0t=1t=2t=3圓排列問題問題描述：給定n個大小不等的圓C1,C2,…,Cn，現(xiàn)要將這n個圓排進一個矩形框中，且要求各圓與矩形框的底邊相切。圓排列問題要求從n個圓的所有排列中找出有最小長度的圓排列。例如，當n=3，且所給的3個圓的半徑分別為1，1，2時，這3個圓的最小長度的圓排列如圖所示。問題分析問題的狀態(tài)表示約束條件操作符問題解和解空間

圓排列─回溯算法1）約束函數(shù)剪枝用于剪除那些不可能導出可行解的分支。

2）限界函數(shù)剪枝用于剪除那些不可能導出最優(yōu)解的分支。

圓排列#include

<math.h>#include<stdio.h>#defineMaxN1000doubleglobalRadius[MaxN];//圓排列中每個圓的半徑，注意保證它始終是一個排列doubleglobalCenterX[MaxN];//圓排列中的圓心X軸坐標，約定第一個圓心坐標為0doubleglobalMin;//全局最優(yōu)值int

globalNum;//圓的數(shù)目void

CircleBacktrack(intt){

if(t==globalNum){globalMin=permLength();//得到更優(yōu)的解}else{

doublecenterx,width;

for(intj=t;j<globalNum;j++){//遍歷所有子結點Swap(globalRadius[t],globalRadius[j]);//把下標j處的圓排列在位置tcenterx=curCenter(t);//計算當前排列中第t個圓的圓心X坐標width=centerx+globalRadius[t]+globalRadius[0];

if(width<globalMin){//限界判定globalCenterX[t]=centerx;CircleBacktrack(t+1);//遞歸處理}Swap(globalRadius[t],globalRadius[j]);//globalRadius[j]處理完后，換回原來位置}//endoffor}}細節(jié)圓排列

有沒有異議？

圓排列#include

<math.h>#include<stdio.h>#defineMaxN1000doubleglobalRadius[MaxN];//圓排列中每個圓的半徑，注意保證它始終是一個排列doubleglobalCenterX[MaxN];//圓排列中的圓心X軸坐標，約定第一個圓心坐標為0doubleglobalMin;//全局最優(yōu)值intglobalNum;//圓的數(shù)目doublecurCenter(intt){//在當前排列下，計算第t個圓的圓心坐標

doubletemp=0,valuex;

for(intj=0;j<t;j++){//遍歷t之前的圓，根據(jù)相切求圓心坐標valuex=globalCenterX[j]+2.0*sqrt(globalRadius[t]*globalRadius[j]);

if(valuex>temp)temp=valuex;}valuex=globalRadius[t]-globalRadius[0];//此時不與任何圓相切，與左邊框相切

if(valuex>temp)temp=valuex;

returntemp;}回溯法的效率回溯算法的效率在很大程度上依賴于以下因素：產(chǎn)生新狀態(tài)的時間；滿足顯約束的狀態(tài)的個數(shù)；計算約束函數(shù)constraint的時間；計算限界函數(shù)bound的時間；滿足約束函數(shù)和限界函數(shù)約束的狀態(tài)的個數(shù)。好的約束函數(shù)能顯著地減少所生成的結點數(shù)。但這樣的約束函數(shù)往往計算量較大。因此，在選擇約束函數(shù)時通常存在生成結點數(shù)與約束函數(shù)計算量之間的折衷?；厮莘ǖ男嗜绻饪臻g的結構已經(jīng)確定，則影響回溯法效率的前三個因素就可以確定，只剩下生成結點的數(shù)目是可變的，它將隨問題的具體內(nèi)容及結點的不同生成方式而變動。即使對同一問題的不同實例，回溯法所產(chǎn)生的結點數(shù)也會有很大變化。對于一個實例，回溯法可能只產(chǎn)生O(n)個結點而對另一個非常相近的實例，回溯法可能就會產(chǎn)生解空間中的所有結點。

p=(100,1,1)，w=(30,20,20)C=60p=(1,1,100)，w=(20,20,30)C=60重排原理對于許多問題而言，在搜索試探時選取x[i]的值順序是任意的在其他條件相當?shù)那疤嵯拢尶扇≈底钌俚膞[i]優(yōu)先分支限界法廣度優(yōu)先搜索+剪枝優(yōu)化將根結點加入隊列中接著從隊列中取出首結點，使其成為當前擴展結點，一次性生成它的所有孩子結點，判斷孩子結點是舍棄還是保存。舍棄那些不可能導致可行解或最優(yōu)解的孩子結點，其余的結點則保存在隊列中重復上述擴展過程，直到找到問題的解或隊列為空時為止。每一個活結點最多只有一次機會成為擴展結點。分支限界法─背包問題

約束函數(shù)剪枝：刪除不可行解限界函數(shù)剪枝：刪除非最優(yōu)解ABCDJKELFMBestV=50GBound<BestV分支限界法分支限界算法設計通常包含以下2個主要步驟：針對所給問題，定義問題的狀態(tài)空間圖以廣度優(yōu)先方式搜索狀態(tài)空間圖，并在搜索過程中用剪枝策略避免無效搜索functionBranchBound(problem,queue){

//queue初始化為空

node=Make-Node(Initial-State[problem]);

//生成初始狀態(tài)結點

queue←Insert(node,queue)

//初始結點加入隊列

do

while(1)

if

queue==Empty

return

failure

node←Remove-First(queue)

//取出隊列的頭部結點

visit(node);

//訪問當前結點

if

State[node]==Goal

//目標測試

return

Solution(node)

//搜索到目標狀態(tài)，返回解

while

(((sonNode=Next(problem,node))!=NULL){

//子結點約束條件與限界條件判定

if(constraint(sonNode)&&bound(sonNode))

Insert(queue,sonNode);

//在隊列中插入子結點

}}using

namespacestd;structnode{

intWt;

//裝載的重量

intidxBox;//當前被處理的集裝箱編號};//隊列中的結點定義intglobalWeight[MaxBox],globalNum,globalC1;intloadingBFS(){

intmaxWt=0;//最優(yōu)裝載量queue<node>que;//隊列定義nodeheadNode,sonNode;headNode.Wt=0;headNode.idxBox=-1;//初始狀態(tài)結點que.push(headNode);

for(;!que.empty();que.pop()){headNode=que.front();//取出隊列首結點

if(headNode.idxBox==globalNum){//得到葉子結點，或n維-1向量

if((headNode.Wt<=globalC1)&&(headNode.Wt>maxWt)){maxWt=headNode.Wt;//更優(yōu)的解}}else{//擴展所有子結點sonNode.idxBox=headNode.idxBox+1;sonNode.Wt=headNode.Wt+globalWeight[headNode.idxBox+1];que.push(sonNode);//左子結點sonNode.Wt=headNode.Wt;que.push(sonNode);//右子結點}}

returnmaxWt;}裝載問題─廣度優(yōu)先搜索001101101010(10,2)(10,0)(0,0)(50,1)(10,1)(90,2)(50,2)(0,-1)(40,1)(0,1)(80,2)(40,2)(40,2)(0,2)(0,-1)(10,0)(0,0)(50,1)(10,1)(40,1)(0,1)(90,2)(50,2)(10,2)(80,2)(40,2)(50,2)(40,2)(0,2)queuestructnode{

intWt;

//裝載的重量

intidxBox;//當前被處理的集裝箱編號};//隊列中的結點定義que.front(50,2)01判斷條件Wt<=globalC1&&Wt>maxWtmaxWt=50裝載問題─分支限界法

什么時候更新MaxWt？#include

<math.h>#include<stdio.h>#include<queue>#defineMaxBox1000using

namespacestd;structnode{

intWt;//裝載的重量

intBd;//剩余集裝箱總重量

intidxBox;//當前被處理的集裝箱編號};//隊列中的結點定義intglobalWeight[MaxBox],globalNum,globalTotalWt,globalC1;//全局變量intLoadingBranchBound(){

intmaxWt=0;//最優(yōu)裝載量queue<node>que;//隊列定義nodeheadNode,sonNode;headNode.Wt=0;headNode.Bd=globalTotalWt;headNode.idxBox=-1;//初始狀態(tài)結點que.push(headNode);

for(;!que.empty();que.pop()){headNode=que.front();//取隊列首結點

if(headNode.idxBox==globalNum){//得到葉子結點，或n維-1向量

if((headNode.Wt<=globalC1)&&(headNode.Wt>maxWt)){maxWt=headNode.Wt;}}else{//擴展所有子結點sonNode.idxBox=headNode.idxBox+1;sonNode.Bd=headNode.Bd-globalWeight[headNode.idxBox+1];sonNode.Wt=headNode.Wt+globalWeight[headNode.idxBox+1];

if(sonNode.Wt<=globalC1){//約束條件剪枝que.push(sonNode);//左子結點maxWt=sonNode.Wt>maxWt?sonNode.Wt:maxWt;//最優(yōu)值}sonNode.Wt=headNode.Wt;

if(sonNode.Wt+sonNode.Bd>maxWt)//限界條件剪枝que.push(sonNode);//右子結點}}

returnmaxWt;}(10,80,0)(0,80,0)(50,40,1)(10,40,1)(90,0,2)(50,0,2)(0,90,-1)(40,40,1)(0,40,1)(80,0,2)(40,0,2)queuestructnode{

intWt;

//裝載的重量

int

Bd;

//剩余集裝箱總重量

intidxBox;//當前被處理的集裝箱編號};//隊列中的結點定義que.front左右節(jié)點入隊列判斷條件左節(jié)點：Wt<=globalC1右節(jié)點：Wt+Bd>maxWt(0,90,-1)(10,80,0)(0,80,0)(50,40,1)(40,40,1)(50,0,2)40+0<50不滿足0+80>10滿足maxWt=1050=50滿足maxWt=5010+40=50不滿足40<50滿足0+40=40不滿足90>50不滿足50+0>40滿足maxWt=5080>50不滿足10<50滿足判斷條件Wt<=globalC1&&Wt>maxWt啟發(fā)式搜索1）當前擴展結點的子結點，深度優(yōu)先搜索與回溯法2）當前擴展結點的兄弟節(jié)點，廣度優(yōu)先搜索與分支限界法3）最具有“啟發(fā)性”的結點，啟發(fā)式搜索在狀態(tài)空間圖中搜索時，選擇新的擴展結點時有三種策略：啟發(fā)式搜索

啟發(fā)式搜索

廣度優(yōu)先搜索和分支限界法深度優(yōu)先搜索和回溯法

A*算法

A*算法的性質(zhì)定理

A*算法可以在穩(wěn)定的狀態(tài)空間圖中找到問題的最優(yōu)解，這是A*算法適用性的保證。A*算法的性質(zhì)定理

如果A2比A1更靈通，那么其搜索速度相對來說也更快。框架程序HeuristicSearch(){Open=[起始結點];Closed=[];

while(Open表非空){從Open中取得一個結點X,并從OPEN表中刪除.

if(X是目標結點){求得路徑PATH;

}

for(每一個X的合法子結點Y){

if(Y不在OPEN表和CLOSED表中){求Y的估價值;并將Y插入OPEN表中;

//還沒有排序

}

elseif(Y在OPEN表中){

if(Y的估價值小于OPEN表的估價值)更新OPEN表中的估價值;

}

else{//Y在CLOSED表中

if(Y的估價值小于CL