搜索算法講解課件

搜索搜索1人肉搜索google度娘爬蟲文件查找人肉搜索google度娘爬蟲文件查找2什么是搜索算法呢？

搜索算法是利用計算機的高性能來有目的地窮舉一個問題的部分或所有的可能情況，從而求出問題的解的一種方法。

搜索過程實際上是根據(jù)初始條件和擴展規(guī)則構(gòu)造一棵解答樹并尋找符合目標狀態(tài)的節(jié)點的過程。什么是搜索算法呢？ 搜索算法是利用計算機的高性能來有3whatwhat4....A*廣搜貪心算法回溯深搜....A*廣搜貪心算法回溯深搜5

廣度優(yōu)先搜索:從初始狀態(tài)開始,通過規(guī)則來生成第一層結(jié)點,同時檢查生成結(jié)點中是否有目標結(jié)點.若沒有則生成下一層接點,并檢查是否有目標結(jié)點…廣度優(yōu)先搜索廣度優(yōu)先搜索:從初始狀態(tài)開始,通過規(guī)則來生成6廣度優(yōu)先搜索采用隊列存儲每次擴展出當(dāng)前結(jié)點的所有子結(jié)點0123456廣度優(yōu)先搜索采用隊列存儲01234567廣度優(yōu)先搜索voidBFS(intcurNode,intcurDepth){ while(front<rear){ ++front; for(i=0;i<m;i++){ newNode=Expend(q[front].node) if(!Exist(newNode)){ q[rear++].node=newnode; } if(newNode==target)return; }} return;}

廣度優(yōu)先搜索voidBFS(intcurNode,int8搜索算法舉例：八數(shù)碼難題在3×3的方格棋盤上，分別放置了標有數(shù)字1、2、3、4、5、6、7和8的八個棋子5847362158473621

S0初始狀態(tài)

Sg目標狀態(tài)空出一個位置使棋子可以移動，形成不同的局面問題要使棋盤進入某種預(yù)定局面應(yīng)如何移動棋子搜索算法舉例：八數(shù)碼難題在3×3的方格棋盤上，分別放置了標有9廣度

優(yōu)先

搜索

算法

舉例23184765125673目標840層1層2層3層

231847652831476523184765下左右283147652831647528314765下左右12384765下23418765下2831647528316475左右28371465

83214765上下2814376528314576上下1237846512384765下右規(guī)則：空格上下左右廣度

優(yōu)先

搜索

算法

舉例2312567310深度優(yōu)先搜索用堆棧存儲當(dāng)前結(jié)點為下一次擴展結(jié)點的父結(jié)點0123456深度優(yōu)先搜索用堆棧存儲012345611voidDFS(intcurNode,intcurDepth){ if(curNode==Target)return;if(curEdpth>MaxDepth)return; for(inti=0;i<n;++i){ intnewNode=Expend(curNode,i); DFS(newNode,++curDepth); } return; }

函數(shù)的返回值可以根據(jù)具體的情況來設(shè)定voidDFS(intcurNode,intcurDe12深度

優(yōu)先

搜索

算法

舉例23184765

231847652831476523184765283147652831647528314765283164752831647528371465

83214765281437652831457612378465123847652836417528316754832147652837146528143765283145761234567891011121312384765目標0層1層2層3層4層規(guī)則：空格上下左右下左右深度

優(yōu)先

搜索

算法

舉例232131241DescriptionTheGeoSurvCompgeologicsurveycompanyisresponsiblefordetectingundergroundoildeposits.GeoSurvCompworkswithonelargerectangularregionoflandatatime,andcreatesagridthatdividesthelandintonumeroussquareplots.Itthenanalyzeseachplotseparately,usingsensingequipmenttodeterminewhetherornottheplotcontainsoil.Aplotcontainingoiliscalledapocket.Iftwopocketsareadjacent,thentheyarepartofthesameoildeposit.Oildepositscanbequitelargeandmaycontainnumerouspockets.Yourjobistodeterminehowmanydifferentoildepositsarecontainedinagrid.InputTheinputcontainsoneormoregrids.Eachgridbeginswithalinecontainingmandn,thenumberofrowsandcolumnsinthegrid,separatedbyasinglespace.Ifm=0itsignalstheendoftheinput;otherwise1<=m<=100and1<=n<=100.Followingthisaremlinesofncharacterseach(notcountingtheend-of-linecharacters).Eachcharactercorrespondstooneplot,andiseither`*',representingtheabsenceofoil,or`@',representinganoilpocket.Outputareadjacenthorizontally,vertically,ordiagonally.Anoildepositwillnotcontainmorethan100pockets.124114SampleInput11*35*@*@***@***@*@*18@@****@*55****@*@@*@*@**@@@@*@@@**@00SampleOutput0122SampleInput15題目的意思就是在給出的圖中@代表有石油,*代表沒有石油,而在一個有石油的地方它的周圍8個方向的地方如果也有石油,那么這2塊石油是屬于一塊的,給出圖,問圖中有幾塊石油田.若圖為下圖：＠＠＠＠＠是連成一塊的，所以圖中只有一個油田．解題方法：采用深度優(yōu)先搜索策略，對給出的圖中一旦出現(xiàn)一個＠則對其８個方向進行搜索，并對搜索過的＠標記，直到一次搜索結(jié)束則油田總數(shù)加一，最后的總數(shù)即為所求的石油的方塊數(shù)。題目的意思就是在給出的圖中@代表有石油,*代表沒有石油,而在16#include<iostream>usingnamespacestd;

constintMAX=100;intm,n;charmap[MAX][MAX];boolflag[MAX][MAX];intmove_x[8]={-1,0,1,1,1,0,-1,-1};intmove_y[8]={-1,-1,-1,0,1,1,1,0};

voidDfs(intx,inty){inti;if(map[x][y]=='@'&&flag[x][y]==false){flag[x][y]=true;for(i=0;i<8;i++){inttx=x+move_x[i];intty=y+move_y[i];if(tx>=0&&ty>=0&&tx<m&&ty<n&&map[tx][ty]=='@'&&flag[tx][ty]==false){Dfs(tx,ty);}}return;}}#include<iostream>17intmain(){while(cin>>m>>n&&m!=0&&n!=0){memset(flag,false,sizeof(flag));inti,j,sum=0;for(i=0;i<m;i++){for(j=0;j<n;j++){cin>>map[i][j];}}for(i=0;i<m;i++){for(j=0;j<n;j++){if(map[i][j]=='@'&&flag[i][j]==false){Dfs(i,j);sum++;}}}cout<<sum<<endl;}return0;}intmain()18深度優(yōu)先搜索優(yōu)點空間需求少，深度優(yōu)先搜索的存儲要求是深度約束的線性函數(shù)問題可能搜索到錯誤的路徑上，在無限空間中可能陷入無限的搜索最初搜索到的結(jié)果不一定是最優(yōu)的深度優(yōu)先搜索優(yōu)點19廣度優(yōu)先搜索優(yōu)點目標節(jié)點如果存在，用廣度優(yōu)先搜索算法總可以找到該目標節(jié)點，而且是最小（即最短路徑）的節(jié)點缺點當(dāng)目標節(jié)點距離初始節(jié)點較遠時，會產(chǎn)生許多無用的節(jié)點，搜索效率低廣度優(yōu)先搜索優(yōu)點20雙向廣度優(yōu)先搜索（DBFS）DBFS算法是對BFS算法的一種擴展。BFS算法從起始節(jié)點以廣度優(yōu)先的順序不斷擴展，直到遇到目的節(jié)點DBFS算法從兩個方向以廣度優(yōu)先的順序同時擴展，一個是從起始節(jié)點開始擴展，另一個是從目的節(jié)點擴展，直到一個擴展隊列中出現(xiàn)另外一個隊列中已經(jīng)擴展的節(jié)點，也就相當(dāng)于兩個擴展方向出現(xiàn)了交點，那么可以認為找到了一條路徑。比較DBFS算法相對于BFS算法來說，由于采用了從兩個根開始擴展的方式，搜索樹的寬度得到了明顯的減少，所以在算法的時間復(fù)雜度和空間復(fù)雜度上都有優(yōu)勢！技巧:每次擴展結(jié)點總是選擇結(jié)點比較少的那邊進行下次搜索，并不是機械的兩邊交替。雙向廣度優(yōu)先搜索（DBFS）DBFS算法是對BFS算法的一種21雙向廣度優(yōu)先搜索算法是對廣度優(yōu)先算法的一種擴展。廣度優(yōu)先算法從起始節(jié)點以廣度優(yōu)先的順序不斷擴展，直到遇到目的節(jié)點；而雙向廣度優(yōu)先算法從兩個方向以廣度優(yōu)先的順序同時擴展，一個是從起始節(jié)點開始擴展，另一個是從目的節(jié)點擴展，直到一個擴展隊列中出現(xiàn)另外一個隊列中已經(jīng)擴展的節(jié)點，也就相當(dāng)于兩個擴展方向出現(xiàn)了交點，那么可以認為我們找到了一條路徑。雙向廣度優(yōu)先算法相對于廣度優(yōu)先算法來說，由于采用了從兩個根開始擴展的方式，搜索樹的深度得到了明顯的減少，所以在算法的時間復(fù)雜度和空間復(fù)雜度上都有較大的優(yōu)勢！雙向廣度優(yōu)先算法特別適合于給出了起始節(jié)點和目的節(jié)點，要求他們之間的最短路徑的問題。雙向廣度優(yōu)先搜索雙向廣度優(yōu)先搜索算法是對廣度優(yōu)先算法的一種擴22雙向廣度優(yōu)先搜索雙向廣度優(yōu)先算法編程的基本框架如下：數(shù)據(jù)結(jié)構(gòu)：Queueq1,q2;//兩個隊列分別用于兩個方向的擴展（注意在一般的廣度優(yōu)先算法中，只需要一個隊列）inthead[2],tail[2];//兩個隊列的頭指針和尾指針雙向廣度優(yōu)先搜索雙向廣度優(yōu)先算法編程的基本框架如下：23算法流程:一、主控函數(shù):voidsolve(){1.將起始節(jié)點放入隊列q1,將目的節(jié)點放入隊列q22.當(dāng)兩個隊列都未空時，作如下循環(huán)

1)如果隊列q1里的未處理節(jié)點比q2中的少（即tail[0]-head[0]<tail[1]-head[1]),則擴展（expand()）隊列q1

2)否則擴展（expand()）隊列q2(即tail[0]-head[0]>=tail[1]-head[1]時)3.如果隊列q1未空，循環(huán)擴展（expand()）q1直到為空4.如果隊列q2未空，循環(huán)擴展（expand()）q2直到為空}雙向廣度優(yōu)先搜索算法流程:雙向廣度優(yōu)先搜索24算法流程:二、擴展函數(shù):intexpand(i)//其中i為隊列的編號(表示q0或者q1){

取隊列qi的頭結(jié)點H

對頭節(jié)點H的每一個相鄰節(jié)點adj，作如下循環(huán)

1如果adj已經(jīng)在隊列qi之前的某個位置出現(xiàn)，則拋棄節(jié)點adj

2如果adj在隊列qi中不存在

1）將adj放入隊列qi

2)

如果adj在隊列(q(1-i))，即在另外一個隊列中出現(xiàn)，輸出找到路徑

}雙向廣度優(yōu)先搜索算法流程:雙向廣度優(yōu)先搜索25算法流程:三、判斷新節(jié)點是否在同一個隊列中重復(fù)的函數(shù)intisduplicate(i,j)//i為隊列編號，j為當(dāng)前節(jié)點在隊列中的指針{

遍歷隊列,判斷是否存在【線性遍歷的時間復(fù)雜度為O(N)，如果用HashTable優(yōu)化，時間復(fù)雜度可以降到O(1)]}四、判斷當(dāng)前擴展出的節(jié)點是否在另外一個隊列出現(xiàn)，也就是判斷相交的函數(shù)intisintersect(i,j)//i為隊列編號，j為當(dāng)前節(jié)點在隊列中的指針{遍歷隊列,判斷是否存在【線性遍歷的時間復(fù)雜度為O(N)，如果用HashTable優(yōu)化，時間復(fù)雜度可以降到O(1)]}雙向廣度優(yōu)先搜索算法流程:雙向廣度優(yōu)先搜索26給定3X3的矩陣如下:

2

3

41

5

x7

6

8程序每次可以交換"x"和它上下左右的數(shù)字，經(jīng)過多次移動后得到如下狀態(tài):1

2

34

5

67

8

x輸出在最少移動步數(shù)的情況下的移動路徑[每次移動的方向上下左右依次表示為'u','d','l','r']雙向?qū)挾葍?yōu)先搜索求解8數(shù)碼問題給定3X3的矩陣如下:

2

3

4雙27#include<stdio.h>

#include<stdlib.h>

#include<string.h>#defineMAXN1000000#defineSWAP(a,b){chart=a;a=b;b=t;}typedefstruct_NodeNode;struct_Node

{

chartile[10];//representthetile

charpos;

//thepositionof'x'

chardir;

//themovingdirectionof'x'

intparent;//indexofparentnode

};inthead[2],tail[2];

Nodequeue[2][MAXN];//twoqueues//shiftofmovingup,down,left,right

intshift[4][2]={{-1,0},{1,0},{0,-1},{0,1}};//foroutputdirection!

chardir[4][2]={{'u','d'},{'d','u'},{'l','r'},{'r','l'}};//testcase

charstart[10]="23415x768";

charend[10]="12345678x";intmain(intargc,char**argv)

{

readtile();

if(!solve())

{

printf("unsolvable\n");

}

return0;

}//readatile3by3

voidreadtile()

{

inti;

chartemp[10];

for(i=0;i<9;++i)

{

scanf("%s",temp);

start[i]=temp[0];

}

start[9]='\0';

}#include<stdio.h>

#include<s28//callexpandtogeneratequeues

intsolve()

{

init(0,start);

init(1,end);

while(head[0]<=tail[0]&&head[1]<=tail[1])

{

//expandtheshorterqueuefirstly

if(tail[0]-head[0]>=tail[1]-head[1])

{

if(expand(1))return1;

}

else

{

if(expand(0))return1;

}

}

while(head[0]<=tail[0])if(expand(0))return1;

while(head[1]<=tail[1])if(expand(1))return1;

return0;

}//initthequeue

voidinit(intqi,constchar*state)

{

strcpy(queue[qi][0].tile,state);

queue[qi][0].pos=strchr(state,'x')-state;

queue[qi][0].parent=-1;

head[qi]=tail[qi]

=0;

}//callexpandtogeneratequeu29intexpand(intqi)//expandnodes

{

inti,x,y,r;

Node*p=&(queue[qi][head[qi]]);

head[qi]++;

for(i=0;i<4;++i)

{

x=p->pos/3+shift[i][0];

y=p->pos%3+shift[i][1];

if(x>=0&&x<=2&&y>=0&&y<=2)

{

tail[qi]++;

Node*pNew=&(queue[qi][tail[qi]]);

strcpy(pNew->tile,p->tile);

SWAP(pNew->tile[3*x+y],pNew->tile[p->pos]);

pNew->pos=3*x+y;

pNew->parent=head[qi]-1;

pNew->dir=dir[i][qi];

if(isduplicate(qi))

{

tail[qi]--;}

else

{

if((r=isintersect(qi))!=-1)

{

if(qi==1)

{

print_result(r,tail[qi]);

}

else

{

print_result(tail[qi],r);

}

return1;

}

}

}

}

return0;

}intexpand(intqi)//expandno30//checkifthereareduplicatesinthequeue

intisduplicate(intqi)

{

inti;

for(i=0;i<tail[qi];++i)

{

if(strcmp(queue[qi][tail[qi]].tile,queue[qi][i].tile)==0)

{

return1;

}

}

return0;

}//checkifthecurrentnodeisinanotherqueue!

intisintersect(intqi)

{

inti;

for(i=0;i<tail[1-qi];++i)

{

if(strcmp(queue[qi][tail[qi]].tile,queue[1-qi][i].tile)==0)

{

returni;

}

}

return-1;

}//checkifthereareduplicate31//printresult

voidprint_backward(inti)

{

if(queue[0][i].parent!=-1)

{

print_backward(queue[0][i].parent);

printf("%c",queue[0][i].dir);

}

}

voidprint_forward(intj)

{

if(queue[1][j].parent!=-1)

{

printf("%c",queue[1][j].dir);

print_forward(queue[1][j].parent);

}

}

voidprint_result(inti,intj)

{

//printf("%d,%d\n",i,j);

print_backward(i);

print_forward(j);

printf("\n");

}//printresult

voidprint_back32雙向廣度優(yōu)先搜索未必總能達到好的效果雙向廣搜一般來說可以少擴展不到一倍的節(jié)點，個別時候甚至擴展出來的節(jié)點更多?？紤]到程序執(zhí)行邏輯更復(fù)雜，寫得稍微不好就會導(dǎo)致雙向廣搜比單向更慢。在ACM競賽中，一般來說不會因為復(fù)雜度上常數(shù)的差別而超時，所以實際上用到雙向廣搜的時候不多。雙向廣度優(yōu)先搜索未必總能達到好的效果雙向廣搜一般來說可以少擴33回溯算法回溯算法34回溯算法回溯算法的基本思想是：從一條路往前走，能進則進，不能進則退回來，換一條路再試。回溯算法回溯算法的基本思想是：從一條路往前走，能進則進，不能35遞歸類問題對下列步驟循環(huán)執(zhí)行，直到遍歷完解空間：

判斷當(dāng)前步驟是否可行；

如果不可行，返回上一層；

如果可行，對本步驟進行標記;

試探下一步；

無路可走時，釋放標記，返回上一層。遞歸類問題對下列步驟循環(huán)執(zhí)行，直到遍歷完解空間：36物資調(diào)度

限時：2000ms某地區(qū)發(fā)生了地震，災(zāi)區(qū)已經(jīng)非常困難。一方有難，八方支援。現(xiàn)在已知有N個地方分別有A1，A2,….,An個物資可供調(diào)配。目前災(zāi)區(qū)需要物資數(shù)量為M。

現(xiàn)在，請你幫忙算一算，總共有多少種物質(zhì)調(diào)度方案。假設(shè)某地方一旦被選擇調(diào)配，則其物資數(shù)全部運走。物資調(diào)度

限時：2000ms37物資調(diào)度4

=

1

+

1

+

2

=

1

+

1

+

2

=

2

+

26=

1

+

1

+

2

+

2物資調(diào)度4=1+1+2=1+1+238物資調(diào)度每個地方的物資是否調(diào)度，存在兩種情況；解空間是一個二叉樹。物資調(diào)度每個地方的物資是否調(diào)度，存在兩種情況；39物資調(diào)度地點1的物資是否調(diào)度地點2的物資是否調(diào)度地點2的物資是否調(diào)度地點3的物資是否調(diào)度地點3的物資是否調(diào)度。。。。。。調(diào)度調(diào)度不調(diào)度不調(diào)度物資調(diào)度地點1的物資是否調(diào)度地點2的物資是否調(diào)度地點2的物資40物資調(diào)度物資調(diào)度41N皇后問題在8X8格的國際象棋上擺放八個皇后，使其不能互相攻擊，即任意兩個皇后都不能處于同一行、同一列或同一斜線上，問有多少種擺法。N皇后問題在8X8格的國際象棋上擺放八個皇后，使其不能互相攻42N皇后問題以4*4的棋盤為例：N皇后問題以4*4的棋盤為例：43N皇后問題N皇后問題44N皇后問題beginifI=n+1then輸出方案；forj:=1tondoif皇后能放在第I行第J列的位置

試探此步是否可走

thenbegin

放置第I個皇后；

對放置皇后的位置進行標記；

做標記Try（I+1）

試探下一步

對放置皇后的位置釋放標記；

釋放標記end;end;N皇后問題begin45遞歸法不一定要用到遞歸遞歸法不一定要用到遞歸46搜索算法的優(yōu)化搜索算法的優(yōu)化471搜索剪枝在很多情況下，我們已經(jīng)找到了一組比較好的解。但是計算機仍然會義無返顧地去搜索比它更“劣”的其他解，搜索到后也只能回溯。為了避免出現(xiàn)這種情況，我們需要靈活地去定制回溯搜索的邊界。DFS1搜索剪枝在很多情況下，我們已經(jīng)找到了一組比較好的解。但是計481381172612815146112413712求一自塔頂?shù)剿椎穆窂?，該路徑上結(jié)點的值的和最大。數(shù)字三角形問題1381172612815146112413712求一自塔頂491381172612815146112413712剪枝時先利用貪心法尋找路徑1381172612815146112413712剪枝時先利50我們可以采用分枝定界法，把搜索樹中不必要的枝剪去皇后問題

采用一般的回溯，就是每一行的每個格子放與不放都搜索一下，然后回溯一次，換下一個點繼續(xù)搜索。這個算法的效率是n!實際上，在放置了(1,1)這個皇后，再把皇后放置在(2,1)就是毫無意義的，前面一個皇后一定能攻擊到它。我們這樣做：走了一個棋子以后，把它的“勢力范圍”給圈出來，并且告訴以后的皇后：這里不能放置。舉簡單的例子：放置皇后(1,1)，由于打“.”的格子在放了(1,1)這顆子之后，被標注為了“不能走”，所以這些點我們就不去理會了。這樣就節(jié)省了很多時間，大大提高了搜索的效率。我們可以采用分枝定界法，把搜索樹中不必要的枝剪去皇后問題51記憶化搜索的過程中，實際上，很多調(diào)用都是不必要的，也就是把產(chǎn)生過的最優(yōu)狀態(tài)，又產(chǎn)生了一次。為了避免浪費，很顯然，我們把產(chǎn)生過的最優(yōu)狀態(tài)存放在一個數(shù)組中。記憶化搜索的過程中，實際上，很多調(diào)用都是不必要的，也就是把產(chǎn)52

采用動態(tài)規(guī)劃，很容易地，我們寫出狀態(tài)轉(zhuǎn)移方程：f(i,j)=a[i,j]+min{f(i+1,j)+f(i+1,j+1)}得出一個非常簡單的遞歸過程：if(i==0)return(a[i,j]);f1=f(i+1,j);f2=f(i+1,j+1);if（f1>f2）returna[i,j]+f1;elsereturna[i,j]+f2;顯而易見，這個算法就是最簡單的搜索算法。時間復(fù)雜度為2n，明顯是會超時的。分析一下搜索的過程，實際上，很多調(diào)用都是不必要的，也就是把產(chǎn)生過的最優(yōu)狀態(tài)，又產(chǎn)生了一次。為了避免浪費，很顯然，我們存放在一個A數(shù)組中。A[i,j]：每產(chǎn)生一個f(i,j)，將f(i,j)的值放入A中，以后再次調(diào)用到f(i,j)的時候，直接從A[i,j]來取就可以了。數(shù)字三角形問題采用動態(tài)規(guī)劃，很容易地，我們寫出狀態(tài)轉(zhuǎn)移方程：數(shù)字三532雙向搜索從初始結(jié)點開始擴展，每擴展一層（稱它為f1），再從目標結(jié)點按照產(chǎn)生系統(tǒng)相反的辦法來擴展結(jié)點（稱它為f2），直到f1和f2產(chǎn)生出了相同的結(jié)點，把中間路線輸出就可以了。這一類問題，很明顯，需要給你初狀態(tài)和末狀態(tài)，并且狀態(tài)產(chǎn)生是可逆、容易實現(xiàn)的。BFS2雙向搜索從初始結(jié)點開始擴展，每擴展一層（稱它為f1），再從54魔板由8個同樣大小的方塊組成，每個方塊的顏色均不同，本題中用數(shù)字1至8分別表示，可能出現(xiàn)在魔板的任一位置。對于魔板可施加三種不同的操作，分別是A,B,C標識，具體操作方法如下：魔板問題ACB上下行互換每次一行同時循環(huán)右移一格中間四個方格順時針旋轉(zhuǎn)一格魔板由8個同樣大小的方塊組成，每個方塊的顏色均不同，本題中用55啟發(fā)式搜索所謂啟發(fā)式搜索，就在于當(dāng)前搜索結(jié)點往下選擇下一步結(jié)點時，可以通過一個啟發(fā)函數(shù)來進行選擇，選擇代價最少的結(jié)點作為下一步搜索結(jié)點而跳轉(zhuǎn)其上（遇到有一個以上代價最少的結(jié)點，不妨選距離當(dāng)前搜索點最近一次展開的搜索點進行下一步搜索）。一個經(jīng)過仔細設(shè)計的啟發(fā)函數(shù)，往往在很快的時間內(nèi)就可得到一個搜索問題的最優(yōu)解，對于NP問題，亦可在多項式時間內(nèi)得到一個較優(yōu)解。啟發(fā)式搜索所謂啟發(fā)式搜索，就在于當(dāng)前搜索結(jié)點往下選擇下一步結(jié)56啟發(fā)式估價函數(shù)f(n)=g(n)+h(n)其中f(n)是節(jié)點n的估價函數(shù)，g(n)是在狀態(tài)空間中從初始節(jié)點到n節(jié)點的實際代價，h(n)是從n到目標節(jié)點最佳路徑的估計代價。在這里主要是h(n)體現(xiàn)了搜索的啟發(fā)信息，因為g(n)是已知的。啟發(fā)式估價函數(shù)f(n)=g(n)+h(n)57若干啟發(fā)式搜索算法局部擇優(yōu)搜索法 在搜索的過程中選取“最佳節(jié)點”后舍棄其他的兄弟節(jié)點、父親節(jié)點，繼而繼續(xù)搜索最好優(yōu)先搜索法在每一步的估價中都把當(dāng)前的節(jié)點和以前的節(jié)點的估價值比較得到一個“最佳的節(jié)點”，繼而進行搜索A*算法如果一個估價函數(shù)可以找出最短的路徑，我們稱之為可采納性。

A*算法是一個可采納的最好優(yōu)先算法。若干啟發(fā)式搜索算法局部擇優(yōu)搜索法58A*算法f'(n)=g'(n)+h'(n)f‘(n)是估價函數(shù)，g’(n)表示從起始搜索點到當(dāng)前點的代價（通常用某結(jié)點在搜索樹中的深度來表示）。h‘(n)是n到目標的最短路經(jīng)的啟發(fā)值。由于這個f’(n)其實是無法預(yù)先知道的，所以我們用前面的估價函數(shù)f(n)做近似。分支定界實際上是A*算法的一種雛形，其對于每個擴展出來的節(jié)點給出一個預(yù)期值，如果這個預(yù)期值不如當(dāng)前已經(jīng)搜索出來的結(jié)果好的話，則將這個節(jié)點(包括其子節(jié)點)從解答樹中刪去，從而達到加快搜索速度的目的。A*算法f'(n)=g'(n)+h'(n)59A*算法的條件一種具有f(n)=g(n)+h(n)策略的啟發(fā)式算法能成為A*算法的充分條件是：1）搜索樹上存在著從起始點到終止點的最優(yōu)路徑。2）問題域是有限的。3）所有結(jié)點的子結(jié)點的搜索代價值>0。4）h(n)<=h*(n)（h*(n)為實際問題的代價值）。當(dāng)此四個條件都滿足時，一個具有f(n)=g(n)+h(n)策略的啟發(fā)式算法能成為A*算法，并一定能找到最優(yōu)解。A*算法的條件一種具有f(n)=g(n)+h(n)策略的啟發(fā)60A*算法實現(xiàn)框架初始化起始點，將其加入未搜索過點的優(yōu)先隊列當(dāng)隊列非空且未達到終止點時 獲取隊列頭結(jié)點，并尋找其所有孩子結(jié)點；若孩子結(jié)點未在已搜索和待搜索隊列中，計算其F值，并將其有序插入隊列中；若在待搜索隊列中且F值較小，則替換之。輸出搜索結(jié)果

從已搜索隊列中可逆推搜索過程A*算法實現(xiàn)框架初始化起始點，將其加入未搜索過點的優(yōu)先隊列61主要搜索過程偽代碼如下：創(chuàng)建兩個表，OPEN表保存所有已生成而未考察的節(jié)點，CLOSE表中記錄已訪問過的節(jié)點。

算起點的估價值;將起點放入OPEN表;

while(OPEN!=NULL)

{從OPEN表中取估價值f最小的節(jié)點n;

if(n節(jié)點==目標節(jié)點)

break;

for(當(dāng)前節(jié)點n的每個子節(jié)點X)

{

算X的估價值;

if(XinOPEN){

if(X的估價值小于OPEN表的估價值){

把n設(shè)置為X的父親;

更新OPEN表中的估價值;//取最小路徑的估價值]}

}

if(Xin

CLOSE)continue;

if(Xnotinboth){

把n設(shè)置為X的父親;

求X的估價值;

并將X插入OPEN表中;//還沒有排序}

}//endfor將n節(jié)點插入CLOSE表中;

按照估價值將OPEN表中的節(jié)點排序;//實際上是比較OPEN表內(nèi)節(jié)點f的大小，從最小路徑的節(jié)點向下進行。}//endwhile(OPEN!=NULL)主要搜索過程偽代碼如下：創(chuàng)建兩個表，OPEN表保存所有已生62A*算法求解8數(shù)碼問題f(x)=g(x)+h(x)g(x)為經(jīng)過上下左右移動空格附近的數(shù)字來得到新狀態(tài)所需步數(shù)，h(x)為當(dāng)前狀態(tài)與目標狀態(tài)的距離，就是所有不在目標位置的數(shù)字個數(shù)總和，必然小于h*(x)A*算法求解8數(shù)碼問題f(x)=g(x)+h(x)63搜索算法講解課件64搜索：1010、1016、1043、1241、1560、2553、

物資調(diào)度搜索算法講解課件65thankyouthankyou66搜索搜索67人肉搜索google度娘爬蟲文件查找人肉搜索google度娘爬蟲文件查找68什么是搜索算法呢？

搜索算法是利用計算機的高性能來有目的地窮舉一個問題的部分或所有的可能情況，從而求出問題的解的一種方法。

搜索過程實際上是根據(jù)初始條件和擴展規(guī)則構(gòu)造一棵解答樹并尋找符合目標狀態(tài)的節(jié)點的過程。什么是搜索算法呢？ 搜索算法是利用計算機的高性能來有69whatwhat70....A*廣搜貪心算法回溯深搜....A*廣搜貪心算法回溯深搜71

廣度優(yōu)先搜索:從初始狀態(tài)開始,通過規(guī)則來生成第一層結(jié)點,同時檢查生成結(jié)點中是否有目標結(jié)點.若沒有則生成下一層接點,并檢查是否有目標結(jié)點…廣度優(yōu)先搜索廣度優(yōu)先搜索:從初始狀態(tài)開始,通過規(guī)則來生成72廣度優(yōu)先搜索采用隊列存儲每次擴展出當(dāng)前結(jié)點的所有子結(jié)點0123456廣度優(yōu)先搜索采用隊列存儲012345673廣度優(yōu)先搜索voidBFS(intcurNode,intcurDepth){ while(front<rear){ ++front; for(i=0;i<m;i++){ newNode=Expend(q[front].node) if(!Exist(newNode)){ q[rear++].node=newnode; } if(newNode==target)return; }} return;}

廣度優(yōu)先搜索voidBFS(intcurNode,int74搜索算法舉例：八數(shù)碼難題在3×3的方格棋盤上，分別放置了標有數(shù)字1、2、3、4、5、6、7和8的八個棋子5847362158473621

S0初始狀態(tài)

Sg目標狀態(tài)空出一個位置使棋子可以移動，形成不同的局面問題要使棋盤進入某種預(yù)定局面應(yīng)如何移動棋子搜索算法舉例：八數(shù)碼難題在3×3的方格棋盤上，分別放置了標有75廣度

優(yōu)先

搜索

算法

舉例23184765125673目標840層1層2層3層

231847652831476523184765下左右283147652831647528314765下左右12384765下23418765下2831647528316475左右28371465

83214765上下2814376528314576上下1237846512384765下右規(guī)則：空格上下左右廣度

優(yōu)先

搜索

算法

舉例2312567376深度優(yōu)先搜索用堆棧存儲當(dāng)前結(jié)點為下一次擴展結(jié)點的父結(jié)點0123456深度優(yōu)先搜索用堆棧存儲012345677voidDFS(intcurNode,intcurDepth){ if(curNode==Target)return;if(curEdpth>MaxDepth)return; for(inti=0;i<n;++i){ intnewNode=Expend(curNode,i); DFS(newNode,++curDepth); } return; }

函數(shù)的返回值可以根據(jù)具體的情況來設(shè)定voidDFS(intcurNode,intcurDe78深度

優(yōu)先

搜索

算法

舉例23184765

231847652831476523184765283147652831647528314765283164752831647528371465

83214765281437652831457612378465123847652836417528316754832147652837146528143765283145761234567891011121312384765目標0層1層2層3層4層規(guī)則：空格上下左右下左右深度

優(yōu)先

搜索

算法

舉例232791241DescriptionTheGeoSurvCompgeologicsurveycompanyisresponsiblefordetectingundergroundoildeposits.GeoSurvCompworkswithonelargerectangularregionoflandatatime,andcreatesagridthatdividesthelandintonumeroussquareplots.Itthenanalyzeseachplotseparately,usingsensingequipmenttodeterminewhetherornottheplotcontainsoil.Aplotcontainingoiliscalledapocket.Iftwopocketsareadjacent,thentheyarepartofthesameoildeposit.Oildepositscanbequitelargeandmaycontainnumerouspockets.Yourjobistodeterminehowmanydifferentoildepositsarecontainedinagrid.InputTheinputcontainsoneormoregrids.Eachgridbeginswithalinecontainingmandn,thenumberofrowsandcolumnsinthegrid,separatedbyasinglespace.Ifm=0itsignalstheendoftheinput;otherwise1<=m<=100and1<=n<=100.Followingthisaremlinesofncharacterseach(notcountingtheend-of-linecharacters).Eachcharactercorrespondstooneplot,andiseither`*',representingtheabsenceofoil,or`@',representinganoilpocket.Outputareadjacenthorizontally,vertically,ordiagonally.Anoildepositwillnotcontainmorethan100pockets.124180SampleInput11*35*@*@***@***@*@*18@@****@*55****@*@@*@*@**@@@@*@@@**@00SampleOutput0122SampleInput81題目的意思就是在給出的圖中@代表有石油,*代表沒有石油,而在一個有石油的地方它的周圍8個方向的地方如果也有石油,那么這2塊石油是屬于一塊的,給出圖,問圖中有幾塊石油田.若圖為下圖：＠＠＠＠＠是連成一塊的，所以圖中只有一個油田．解題方法：采用深度優(yōu)先搜索策略，對給出的圖中一旦出現(xiàn)一個＠則對其８個方向進行搜索，并對搜索過的＠標記，直到一次搜索結(jié)束則油田總數(shù)加一，最后的總數(shù)即為所求的石油的方塊數(shù)。題目的意思就是在給出的圖中@代表有石油,*代表沒有石油,而在82#include<iostream>usingnamespacestd;

constintMAX=100;intm,n;charmap[MAX][MAX];boolflag[MAX][MAX];intmove_x[8]={-1,0,1,1,1,0,-1,-1};intmove_y[8]={-1,-1,-1,0,1,1,1,0};

voidDfs(intx,inty){inti;if(map[x][y]=='@'&&flag[x][y]==false){flag[x][y]=true;for(i=0;i<8;i++){inttx=x+move_x[i];intty=y+move_y[i];if(tx>=0&&ty>=0&&tx<m&&ty<n&&map[tx][ty]=='@'&&flag[tx][ty]==false){Dfs(tx,ty);}}return;}}#include<iostream>83intmain(){while(cin>>m>>n&&m!=0&&n!=0){memset(flag,false,sizeof(flag));inti,j,sum=0;for(i=0;i<m;i++){for(j=0;j<n;j++){cin>>map[i][j];}}for(i=0;i<m;i++){for(j=0;j<n;j++){if(map[i][j]=='@'&&flag[i][j]==false){Dfs(i,j);sum++;}}}cout<<sum<<endl;}return0;}intmain()84深度優(yōu)先搜索優(yōu)點空間需求少，深度優(yōu)先搜索的存儲要求是深度約束的線性函數(shù)問題可能搜索到錯誤的路徑上，在無限空間中可能陷入無限的搜索最初搜索到的結(jié)果不一定是最優(yōu)的深度優(yōu)先搜索優(yōu)點85廣度優(yōu)先搜索優(yōu)點目標節(jié)點如果存在，用廣度優(yōu)先搜索算法總可以找到該目標節(jié)點，而且是最小（即最短路徑）的節(jié)點缺點當(dāng)目標節(jié)點距離初始節(jié)點較遠時，會產(chǎn)生許多無用的節(jié)點，搜索效率低廣度優(yōu)先搜索優(yōu)點86雙向廣度優(yōu)先搜索（DBFS）DBFS算法是對BFS算法的一種擴展。BFS算法從起始節(jié)點以廣度優(yōu)先的順序不斷擴展，直到遇到目的節(jié)點DBFS算法從兩個方向以廣度優(yōu)先的順序同時擴展，一個是從起始節(jié)點開始擴展，另一個是從目的節(jié)點擴展，直到一個擴展隊列中出現(xiàn)另外一個隊列中已經(jīng)擴展的節(jié)點，也就相當(dāng)于兩個擴展方向出現(xiàn)了交點，那么可以認為找到了一條路徑。比較DBFS算法相對于BFS算法來說，由于采用了從兩個根開始擴展的方式，搜索樹的寬度得到了明顯的減少，所以在算法的時間復(fù)雜度和空間復(fù)雜度上都有優(yōu)勢！技巧:每次擴展結(jié)點總是選擇結(jié)點比較少的那邊進行下次搜索，并不是機械的兩邊交替。雙向廣度優(yōu)先搜索（DBFS）DBFS算法是對BFS算法的一種87雙向廣度優(yōu)先搜索算法是對廣度優(yōu)先算法的一種擴展。廣度優(yōu)先算法從起始節(jié)點以廣度優(yōu)先的順序不斷擴展，直到遇到目的節(jié)點；而雙向廣度優(yōu)先算法從兩個方向以廣度優(yōu)先的順序同時擴展，一個是從起始節(jié)點開始擴展，另一個是從目的節(jié)點擴展，直到一個擴展隊列中出現(xiàn)另外一個隊列中已經(jīng)擴展的節(jié)點，也就相當(dāng)于兩個擴展方向出現(xiàn)了交點，那么可以認為我們找到了一條路徑。雙向廣度優(yōu)先算法相對于廣度優(yōu)先算法來說，由于采用了從兩個根開始擴展的方式，搜索樹的深度得到了明顯的減少，所以在算法的時間復(fù)雜度和空間復(fù)雜度上都有較大的優(yōu)勢！雙向廣度優(yōu)先算法特別適合于給出了起始節(jié)點和目的節(jié)點，要求他們之間的最短路徑的問題。雙向廣度優(yōu)先搜索雙向廣度優(yōu)先搜索算法是對廣度優(yōu)先算法的一種擴88雙向廣度優(yōu)先搜索雙向廣度優(yōu)先算法編程的基本框架如下：數(shù)據(jù)結(jié)構(gòu)：Queueq1,q2;//兩個隊列分別用于兩個方向的擴展（注意在一般的廣度優(yōu)先算法中，只需要一個隊列）inthead[2],tail[2];//兩個隊列的頭指針和尾指針雙向廣度優(yōu)先搜索雙向廣度優(yōu)先算法編程的基本框架如下：89算法流程:一、主控函數(shù):voidsolve(){1.將起始節(jié)點放入隊列q1,將目的節(jié)點放入隊列q22.當(dāng)兩個隊列都未空時，作如下循環(huán)

1)如果隊列q1里的未處理節(jié)點比q2中的少（即tail[0]-head[0]<tail[1]-head[1]),則擴展（expand()）隊列q1

2)否則擴展（expand()）隊列q2(即tail[0]-head[0]>=tail[1]-head[1]時)3.如果隊列q1未空，循環(huán)擴展（expand()）q1直到為空4.如果隊列q2未空，循環(huán)擴展（expand()）q2直到為空}雙向廣度優(yōu)先搜索算法流程:雙向廣度優(yōu)先搜索90算法流程:二、擴展函數(shù):intexpand(i)//其中i為隊列的編號(表示q0或者q1){

取隊列qi的頭結(jié)點H

對頭節(jié)點H的每一個相鄰節(jié)點adj，作如下循環(huán)

1如果adj已經(jīng)在隊列qi之前的某個位置出現(xiàn)，則拋棄節(jié)點adj

2如果adj在隊列qi中不存在

1）將adj放入隊列qi

2)

如果adj在隊列(q(1-i))，即在另外一個隊列中出現(xiàn)，輸出找到路徑

}雙向廣度優(yōu)先搜索算法流程:雙向廣度優(yōu)先搜索91算法流程:三、判斷新節(jié)點是否在同一個隊列中重復(fù)的函數(shù)intisduplicate(i,j)//i為隊列編號，j為當(dāng)前節(jié)點在隊列中的指針{

遍歷隊列,判斷是否存在【線性遍歷的時間復(fù)雜度為O(N)，如果用HashTable優(yōu)化，時間復(fù)雜度可以降到O(1)]}四、判斷當(dāng)前擴展出的節(jié)點是否在另外一個隊列出現(xiàn)，也就是判斷相交的函數(shù)intisintersect(i,j)//i為隊列編號，j為當(dāng)前節(jié)點在隊列中的指針{遍歷隊列,判斷是否存在【線性遍歷的時間復(fù)雜度為O(N)，如果用HashTable優(yōu)化，時間復(fù)雜度可以降到O(1)]}雙向廣度優(yōu)先搜索算法流程:雙向廣度優(yōu)先搜索92給定3X3的矩陣如下:

2

3

41

5

x7

6

8程序每次可以交換"x"和它上下左右的數(shù)字，經(jīng)過多次移動后得到如下狀態(tài):1

2

34

5

67

8

x輸出在最少移動步數(shù)的情況下的移動路徑[每次移動的方向上下左右依次表示為'u','d','l','r']雙向?qū)挾葍?yōu)先搜索求解8數(shù)碼問題給定3X3的矩陣如下:

2

3

4雙93#include<stdio.h>

#include<stdlib.h>

#include<string.h>#defineMAXN1000000#defineSWAP(a,b){chart=a;a=b;b=t;}typedefstruct_NodeNode;struct_Node

{

chartile[10];//representthetile

charpos;

//thepositionof'x'

chardir;

//themovingdirectionof'x'

intparent;//indexofparentnode

};inthead[2],tail[2];

Nodequeue[2][MAXN];//twoqueues//shiftofmovingup,down,left,right

intshift[4][2]={{-1,0},{1,0},{0,-1},{0,1}};//foroutputdirection!

chardir[4][2]={{'u','d'},{'d','u'},{'l','r'},{'r','l'}};//testcase

charstart[10]="23415x768";

charend[10]="12345678x";intmain(intargc,char**argv)

{

readtile();

if(!solve())

{

printf("unsolvable\n");

}

return0;

}//readatile3by3

voidreadtile()

{

inti;

chartemp[10];

for(i=0;i<9;++i)

{

scanf("%s",temp);

start[i]=temp[0];

}

start[9]='\0';

}#include<stdio.h>

#include<s94//callexpandtogeneratequeues

intsolve()

{

init(0,start);

init(1,end);

while(head[0]<=tail[0]&&head[1]<=tail[1])

{

//expandtheshorterqueuefirstly

if(tail[0]-head[0]>=tail[1]-head[1])

{