算法設(shè)計(jì)與分析：搜索方法

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

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

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

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

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

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

stack←Insert(node,stack);

//棧中插入初始結(jié)點(diǎn)

do

while(1)

if

stack==Empty

return

failure;

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

node←Remove-First(stack);

//取出棧頂元素

visit(node);

//訪問棧頂元素

if

State[node]==Goal

//目標(biāo)測試

return

Solution(node)

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

sonNodes=Expend(node,problem);

//擴(kuò)展node

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

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

return

Solution(node);else

visit(node);

//訪問當(dāng)前結(jié)點(diǎn)for(iteratorsonNode=Init(node);sonNode<=Last(node);sonNode++)

if

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

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

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

queue←Insert(node,queue);

//隊(duì)列中加入初始結(jié)點(diǎn)

do

while(1)

if

queue==Empty

returnfailure

node←Remove-First(queue)

//取出隊(duì)列的頭部結(jié)點(diǎn)

visit(node);

//訪問當(dāng)前結(jié)點(diǎn)

if

State[node]==Goal

//目標(biāo)測試

return

Solution(node)

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

sonNodes=Expend(node,problem);

//生成node的未訪問子結(jié)點(diǎn)

queue←Insert-All(sonNodes,queue)

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

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

回溯算法─背包問題

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

2）約束條件

回溯算法─背包問題

3）操作符

4）問題解和解空間

回溯算法─背包問題

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

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

2）約束條件

3）操作符

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

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

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

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

//輸出問題的解else{for

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

x[t]=Node(i);

//記錄當(dāng)前子結(jié)點(diǎn)相關(guān)信息

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

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

backtrack(t+1);

//遞歸調(diào)用，繼續(xù)深度優(yōu)先搜索}}注解：for循環(huán)體依次擴(kuò)展當(dāng)前結(jié)點(diǎn)的所有子結(jié)點(diǎn)，Init()和Last()是一種抽象表示，返回開始子結(jié)點(diǎn)和末尾子結(jié)點(diǎn)的編號。for循環(huán)執(zhí)行完畢則回溯到父結(jié)點(diǎn)。裝載問題把原問題簡化為一艘輪船的裝載問題。容易證明下述結(jié)論：如果一個(gè)給定裝載問題實(shí)例有解，則采用下面的策略可得到最優(yōu)裝載方案：(1)首先將第一艘輪船盡可能裝滿；(2)將剩余的集裝箱裝上第二艘輪船。問題分析裝載問題等價(jià)于以下特殊的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){

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

intsumWeight1=0;

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

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

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

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

左子結(jié)點(diǎn)

右子結(jié)點(diǎn)

裝載問題─回溯算法

右子結(jié)點(diǎn)

裝載問題─回溯算法

右子結(jié)點(diǎn)

左子結(jié)點(diǎn)

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

if(t==globalNum){

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

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

//擴(kuò)展子結(jié)點(diǎn)時(shí)減少globalBd

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

//增大globalWtloadingBacktrack(t+1);

//擴(kuò)展左子樹globalWt-=globalWeight[t];

//回溯時(shí)恢復(fù)globalWt}

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

//擴(kuò)展右子樹}globalBd+=globalWeight[t];//回溯時(shí)恢復(fù)globalBd}細(xì)節(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個(gè)大小不等的圓C1,C2,…,Cn，現(xiàn)要將這n個(gè)圓排進(jìn)一個(gè)矩形框中，且要求各圓與矩形框的底邊相切。圓排列問題要求從n個(gè)圓的所有排列中找出有最小長度的圓排列。例如，當(dāng)n=3，且所給的3個(gè)圓的半徑分別為1，1，2時(shí)，這3個(gè)圓的最小長度的圓排列如圖所示。問題分析問題的狀態(tài)表示約束條件操作符問題解和解空間

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

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

圓排列#include

<math.h>#include<stdio.h>#defineMaxN1000doubleglobalRadius[MaxN];//圓排列中每個(gè)圓的半徑，注意保證它始終是一個(gè)排列doubleglobalCenterX[MaxN];//圓排列中的圓心X軸坐標(biāo)，約定第一個(gè)圓心坐標(biāo)為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++){//遍歷所有子結(jié)點(diǎn)Swap(globalRadius[t],globalRadius[j]);//把下標(biāo)j處的圓排列在位置tcenterx=curCenter(t);//計(jì)算當(dāng)前排列中第t個(gè)圓的圓心X坐標(biāo)width=centerx+globalRadius[t]+globalRadius[0];

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

有沒有異議？

圓排列#include

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

doubletemp=0,valuex;

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

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

if(valuex>temp)temp=valuex;

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

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

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

//queue初始化為空

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

//生成初始狀態(tài)結(jié)點(diǎn)

queue←Insert(node,queue)

//初始結(jié)點(diǎn)加入隊(duì)列

do

while(1)

if

queue==Empty

return

failure

node←Remove-First(queue)

//取出隊(duì)列的頭部結(jié)點(diǎn)

visit(node);

//訪問當(dāng)前結(jié)點(diǎn)

if

State[node]==Goal

//目標(biāo)測試

return

Solution(node)

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

while

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

//子結(jié)點(diǎn)約束條件與限界條件判定

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

Insert(queue,sonNode);

//在隊(duì)列中插入子結(jié)點(diǎn)

}}using

namespacestd;structnode{

intWt;

//裝載的重量

intidxBox;//當(dāng)前被處理的集裝箱編號};//隊(duì)列中的結(jié)點(diǎn)定義intglobalWeight[MaxBox],globalNum,globalC1;intloadingBFS(){

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

for(;!que.empty();que.pop()){headNode=que.front();//取出隊(duì)列首結(jié)點(diǎn)

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

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

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;//當(dāng)前被處理的集裝箱編號};//隊(duì)列中的結(jié)點(diǎn)定義que.front(50,2)01判斷條件Wt<=globalC1&&Wt>maxWtmaxWt=50裝載問題─分支限界法

什么時(shí)候更新MaxWt？#include

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

namespacestd;structnode{

intWt;//裝載的重量

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

intidxBox;//當(dāng)前被處理的集裝箱編號};//隊(duì)列中的結(jié)點(diǎn)定義intglobalWeight[MaxBox],globalNum,globalTotalWt,globalC1;//全局變量intLoadingBranchBound(){

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

for(;!que.empty();que.pop()){headNode=que.front();//取隊(duì)列首結(jié)點(diǎn)

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

if((headNode.Wt<=globalC1)&&(headNode.Wt>maxWt)){maxWt=headNode.Wt;}}else{//擴(kuò)展所有子結(jié)點(diǎn)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);//左子結(jié)點(diǎn)maxWt=sonNode.Wt>maxWt?sonNode.Wt:maxWt;//最優(yōu)值}sonNode.Wt=headNode.Wt;

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

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;//當(dāng)前被處理的集裝箱編號};//隊(duì)列中的結(jié)點(diǎn)定義que.front左右節(jié)點(diǎn)入隊(duì)列判斷條件左節(jié)點(diǎn)：Wt<=globalC1右節(jié)點(diǎn)：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）當(dāng)前擴(kuò)展結(jié)點(diǎn)的子結(jié)點(diǎn)，深度優(yōu)先搜索與回溯法2）當(dāng)前擴(kuò)展結(jié)點(diǎn)的兄弟節(jié)點(diǎn)，廣度優(yōu)先搜索與分支限界法3）最具有“啟發(fā)性”的結(jié)點(diǎn)，啟發(fā)式搜索在狀態(tài)空間圖中搜索時(shí)，選擇新的擴(kuò)展結(jié)點(diǎn)時(shí)有三種策略：啟發(fā)式搜索

啟發(fā)式搜索

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

A*算法

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

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

如果A2比A1更靈通，那么其搜索速度相對來說也更快?？蚣艹绦騂euristicSearch(){Open=[起始結(jié)點(diǎn)];Closed=[];

while(Open表非空){從Open中取得一個(gè)結(jié)點(diǎn)X,并從OPEN表中刪除.

if(X是目標(biāo)結(jié)點(diǎn)){求得路徑PATH;

}

for(每一個(gè)X的合法子結(jié)點(diǎn)Y){

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

//還沒有排序

}

elseif(Y在OPEN表中){

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

}

else{//Y在CLOSED表中

if(Y的估價(jià)值小于CL