搜索算法講解課件

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

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

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

廣度優(yōu)先搜索:從初始狀態(tài)開始,通過規(guī)則來生成第一層結(jié)點(diǎn),同時(shí)檢查生成結(jié)點(diǎn)中是否有目標(biāo)結(jié)點(diǎn).若沒有則生成下一層接點(diǎn),并檢查是否有目標(biāo)結(jié)點(diǎn)…廣度優(yōu)先搜索廣度優(yōu)先搜索:從初始狀態(tài)開始,通過規(guī)則來生成6廣度優(yōu)先搜索采用隊(duì)列存儲(chǔ)每次擴(kuò)展出當(dāng)前結(jié)點(diǎn)的所有子結(jié)點(diǎn)0123456廣度優(yōu)先搜索采用隊(duì)列存儲(chǔ)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的方格棋盤上，分別放置了標(biāo)有數(shù)字1、2、3、4、5、6、7和8的八個(gè)棋子5847362158473621

S0初始狀態(tài)

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

優(yōu)先

搜索

算法

舉例23184765125673目標(biāo)840層1層2層3層

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

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

優(yōu)先

搜索

算法

舉例2312567310深度優(yōu)先搜索用堆棧存儲(chǔ)當(dāng)前結(jié)點(diǎn)為下一次擴(kuò)展結(jié)點(diǎn)的父結(jié)點(diǎn)0123456深度優(yōu)先搜索用堆棧存儲(chǔ)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目標(biāo)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題目的意思就是在給出的圖中@代表有石油,*代表沒有石油,而在一個(gè)有石油的地方它的周圍8個(gè)方向的地方如果也有石油,那么這2塊石油是屬于一塊的,給出圖,問圖中有幾塊石油田.若圖為下圖：＠＠＠＠＠是連成一塊的，所以圖中只有一個(gè)油田．解題方法：采用深度優(yōu)先搜索策略，對給出的圖中一旦出現(xiàn)一個(gè)＠則對其８個(gè)方向進(jìn)行搜索，并對搜索過的＠標(biāo)記，直到一次搜索結(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)點(diǎn)空間需求少，深度優(yōu)先搜索的存儲(chǔ)要求是深度約束的線性函數(shù)問題可能搜索到錯(cuò)誤的路徑上，在無限空間中可能陷入無限的搜索最初搜索到的結(jié)果不一定是最優(yōu)的深度優(yōu)先搜索優(yōu)點(diǎn)19廣度優(yōu)先搜索優(yōu)點(diǎn)目標(biāo)節(jié)點(diǎn)如果存在，用廣度優(yōu)先搜索算法總可以找到該目標(biāo)節(jié)點(diǎn)，而且是最?。醋疃搪窂剑┑墓?jié)點(diǎn)缺點(diǎn)當(dāng)目標(biāo)節(jié)點(diǎn)距離初始節(jié)點(diǎn)較遠(yuǎn)時(shí)，會(huì)產(chǎn)生許多無用的節(jié)點(diǎn)，搜索效率低廣度優(yōu)先搜索優(yōu)點(diǎn)20雙向廣度優(yōu)先搜索（DBFS）DBFS算法是對BFS算法的一種擴(kuò)展。BFS算法從起始節(jié)點(diǎn)以廣度優(yōu)先的順序不斷擴(kuò)展，直到遇到目的節(jié)點(diǎn)DBFS算法從兩個(gè)方向以廣度優(yōu)先的順序同時(shí)擴(kuò)展，一個(gè)是從起始節(jié)點(diǎn)開始擴(kuò)展，另一個(gè)是從目的節(jié)點(diǎn)擴(kuò)展，直到一個(gè)擴(kuò)展隊(duì)列中出現(xiàn)另外一個(gè)隊(duì)列中已經(jīng)擴(kuò)展的節(jié)點(diǎn)，也就相當(dāng)于兩個(gè)擴(kuò)展方向出現(xiàn)了交點(diǎn)，那么可以認(rèn)為找到了一條路徑。比較DBFS算法相對于BFS算法來說，由于采用了從兩個(gè)根開始擴(kuò)展的方式，搜索樹的寬度得到了明顯的減少，所以在算法的時(shí)間復(fù)雜度和空間復(fù)雜度上都有優(yōu)勢！技巧:每次擴(kuò)展結(jié)點(diǎn)總是選擇結(jié)點(diǎn)比較少的那邊進(jìn)行下次搜索，并不是機(jī)械的兩邊交替。雙向廣度優(yōu)先搜索（DBFS）DBFS算法是對BFS算法的一種21雙向廣度優(yōu)先搜索算法是對廣度優(yōu)先算法的一種擴(kuò)展。廣度優(yōu)先算法從起始節(jié)點(diǎn)以廣度優(yōu)先的順序不斷擴(kuò)展，直到遇到目的節(jié)點(diǎn)；而雙向廣度優(yōu)先算法從兩個(gè)方向以廣度優(yōu)先的順序同時(shí)擴(kuò)展，一個(gè)是從起始節(jié)點(diǎn)開始擴(kuò)展，另一個(gè)是從目的節(jié)點(diǎn)擴(kuò)展，直到一個(gè)擴(kuò)展隊(duì)列中出現(xiàn)另外一個(gè)隊(duì)列中已經(jīng)擴(kuò)展的節(jié)點(diǎn)，也就相當(dāng)于兩個(gè)擴(kuò)展方向出現(xiàn)了交點(diǎn)，那么可以認(rèn)為我們找到了一條路徑。雙向廣度優(yōu)先算法相對于廣度優(yōu)先算法來說，由于采用了從兩個(gè)根開始擴(kuò)展的方式，搜索樹的深度得到了明顯的減少，所以在算法的時(shí)間復(fù)雜度和空間復(fù)雜度上都有較大的優(yōu)勢！雙向廣度優(yōu)先算法特別適合于給出了起始節(jié)點(diǎn)和目的節(jié)點(diǎn)，要求他們之間的最短路徑的問題。雙向廣度優(yōu)先搜索雙向廣度優(yōu)先搜索算法是對廣度優(yōu)先算法的一種擴(kuò)22雙向廣度優(yōu)先搜索雙向廣度優(yōu)先算法編程的基本框架如下：數(shù)據(jù)結(jié)構(gòu)：Queueq1,q2;//兩個(gè)隊(duì)列分別用于兩個(gè)方向的擴(kuò)展（注意在一般的廣度優(yōu)先算法中，只需要一個(gè)隊(duì)列）inthead[2],tail[2];//兩個(gè)隊(duì)列的頭指針和尾指針雙向廣度優(yōu)先搜索雙向廣度優(yōu)先算法編程的基本框架如下：23算法流程:一、主控函數(shù):voidsolve(){1.將起始節(jié)點(diǎn)放入隊(duì)列q1,將目的節(jié)點(diǎn)放入隊(duì)列q22.當(dāng)兩個(gè)隊(duì)列都未空時(shí)，作如下循環(huán)

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

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

取隊(duì)列qi的頭結(jié)點(diǎn)H

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

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

2如果adj在隊(duì)列qi中不存在

1）將adj放入隊(duì)列qi

2)

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

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

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

2

3

41

5

x7

6

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

2

34

5

67

8

x輸出在最少移動(dòng)步數(shù)的情況下的移動(dòng)路徑[每次移動(dòng)的方向上下左右依次表示為'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)先搜索未必總能達(dá)到好的效果雙向廣搜一般來說可以少擴(kuò)展不到一倍的節(jié)點(diǎn)，個(gè)別時(shí)候甚至擴(kuò)展出來的節(jié)點(diǎn)更多。考慮到程序執(zhí)行邏輯更復(fù)雜，寫得稍微不好就會(huì)導(dǎo)致雙向廣搜比單向更慢。在ACM競賽中，一般來說不會(huì)因?yàn)閺?fù)雜度上常數(shù)的差別而超時(shí)，所以實(shí)際上用到雙向廣搜的時(shí)候不多。雙向廣度優(yōu)先搜索未必總能達(dá)到好的效果雙向廣搜一般來說可以少擴(kuò)33回溯算法回溯算法34回溯算法回溯算法的基本思想是：從一條路往前走，能進(jìn)則進(jìn)，不能進(jìn)則退回來，換一條路再試?；厮菟惴ɑ厮菟惴ǖ幕舅枷胧牵簭囊粭l路往前走，能進(jìn)則進(jìn)，不能35遞歸類問題對下列步驟循環(huán)執(zhí)行，直到遍歷完解空間：

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

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

如果可行，對本步驟進(jìn)行標(biāo)記;

試探下一步；

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

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

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

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

試探此步是否可走

thenbegin

放置第I個(gè)皇后；

對放置皇后的位置進(jìn)行標(biāo)記；

做標(biāo)記Try（I+1）

試探下一步

對放置皇后的位置釋放標(biāo)記；

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

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

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

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

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

算起點(diǎn)的估價(jià)值;將起點(diǎn)放入OPEN表;

while(OPEN!=NULL)

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

if(n節(jié)點(diǎn)==目標(biāo)節(jié)點(diǎn))

break;

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

{

算X的估價(jià)值;

if(XinOPEN){

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

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

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

}

if(Xin

CLOSE)continue;

if(Xnotinboth){

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

求X的估價(jià)值;

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

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

按照估價(jià)值將OPEN表中的節(jié)點(diǎn)排序;//實(shí)際上是比較OPEN表內(nèi)節(jié)點(diǎn)f的大小，從最小路徑的節(jié)點(diǎn)向下進(jìn)行。}//endwhile(OPEN!=NULL)主要搜索過程偽代碼如下：創(chuàng)建兩個(gè)表，OPEN表保存所有已生62A*算法求解8數(shù)碼問題f(x)=g(x)+h(x)g(x)為經(jīng)過上下左右移動(dòng)空格附近的數(shù)字來得到新狀態(tài)所需步數(shù)，h(x)為當(dāng)前狀態(tài)與目標(biāo)狀態(tài)的距離，就是所有不在目標(biāo)位置的數(shù)字個(gè)數(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ì)算機(jī)的高性能來有目的地窮舉一個(gè)問題的部分或所有的可能情況，從而求出問題的解的一種方法。

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

廣度優(yōu)先搜索:從初始狀態(tài)開始,通過規(guī)則來生成第一層結(jié)點(diǎn),同時(shí)檢查生成結(jié)點(diǎn)中是否有目標(biāo)結(jié)點(diǎn).若沒有則生成下一層接點(diǎn),并檢查是否有目標(biāo)結(jié)點(diǎn)…廣度優(yōu)先搜索廣度優(yōu)先搜索:從初始狀態(tài)開始,通過規(guī)則來生成72廣度優(yōu)先搜索采用隊(duì)列存儲(chǔ)每次擴(kuò)展出當(dāng)前結(jié)點(diǎn)的所有子結(jié)點(diǎn)0123456廣度優(yōu)先搜索采用隊(duì)列存儲(chǔ)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的方格棋盤上，分別放置了標(biāo)有數(shù)字1、2、3、4、5、6、7和8的八個(gè)棋子5847362158473621

S0初始狀態(tài)

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

優(yōu)先

搜索

算法

舉例23184765125673目標(biāo)840層1層2層3層

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

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

優(yōu)先

搜索

算法

舉例2312567376深度優(yōu)先搜索用堆棧存儲(chǔ)當(dāng)前結(jié)點(diǎn)為下一次擴(kuò)展結(jié)點(diǎn)的父結(jié)點(diǎn)0123456深度優(yōu)先搜索用堆棧存儲(chǔ)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目標(biāo)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題目的意思就是在給出的圖中@代表有石油,*代表沒有石油,而在一個(gè)有石油的地方它的周圍8個(gè)方向的地方如果也有石油,那么這2塊石油是屬于一塊的,給出圖,問圖中有幾塊石油田.若圖為下圖：＠＠＠＠＠是連成一塊的，所以圖中只有一個(gè)油田．解題方法：采用深度優(yōu)先搜索策略，對給出的圖中一旦出現(xiàn)一個(gè)＠則對其８個(gè)方向進(jìn)行搜索，并對搜索過的＠標(biāo)記，直到一次搜索結(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)點(diǎn)空間需求少，深度優(yōu)先搜索的存儲(chǔ)要求是深度約束的線性函數(shù)問題可能搜索到錯(cuò)誤的路徑上，在無限空間中可能陷入無限的搜索最初搜索到的結(jié)果不一定是最優(yōu)的深度優(yōu)先搜索優(yōu)點(diǎn)85廣度優(yōu)先搜索優(yōu)點(diǎn)目標(biāo)節(jié)點(diǎn)如果存在，用廣度優(yōu)先搜索算法總可以找到該目標(biāo)節(jié)點(diǎn)，而且是最?。醋疃搪窂剑┑墓?jié)點(diǎn)缺點(diǎn)當(dāng)目標(biāo)節(jié)點(diǎn)距離初始節(jié)點(diǎn)較遠(yuǎn)時(shí)，會(huì)產(chǎn)生許多無用的節(jié)點(diǎn)，搜索效率低廣度優(yōu)先搜索優(yōu)點(diǎn)86雙向廣度優(yōu)先搜索（DBFS）DBFS算法是對BFS算法的一種擴(kuò)展。BFS算法從起始節(jié)點(diǎn)以廣度優(yōu)先的順序不斷擴(kuò)展，直到遇到目的節(jié)點(diǎn)DBFS算法從兩個(gè)方向以廣度優(yōu)先的順序同時(shí)擴(kuò)展，一個(gè)是從起始節(jié)點(diǎn)開始擴(kuò)展，另一個(gè)是從目的節(jié)點(diǎn)擴(kuò)展，直到一個(gè)擴(kuò)展隊(duì)列中出現(xiàn)另外一個(gè)隊(duì)列中已經(jīng)擴(kuò)展的節(jié)點(diǎn)，也就相當(dāng)于兩個(gè)擴(kuò)展方向出現(xiàn)了交點(diǎn)，那么可以認(rèn)為找到了一條路徑。比較DBFS算法相對于BFS算法來說，由于采用了從兩個(gè)根開始擴(kuò)展的方式，搜索樹的寬度得到了明顯的減少，所以在算法的時(shí)間復(fù)雜度和空間復(fù)雜度上都有優(yōu)勢！技巧:每次擴(kuò)展結(jié)點(diǎn)總是選擇結(jié)點(diǎn)比較少的那邊進(jìn)行下次搜索，并不是機(jī)械的兩邊交替。雙向廣度優(yōu)先搜索（DBFS）DBFS算法是對BFS算法的一種87雙向廣度優(yōu)先搜索算法是對廣度優(yōu)先算法的一種擴(kuò)展。廣度優(yōu)先算法從起始節(jié)點(diǎn)以廣度優(yōu)先的順序不斷擴(kuò)展，直到遇到目的節(jié)點(diǎn)；而雙向廣度優(yōu)先算法從兩個(gè)方向以廣度優(yōu)先的順序同時(shí)擴(kuò)展，一個(gè)是從起始節(jié)點(diǎn)開始擴(kuò)展，另一個(gè)是從目的節(jié)點(diǎn)擴(kuò)展，直到一個(gè)擴(kuò)展隊(duì)列中出現(xiàn)另外一個(gè)隊(duì)列中已經(jīng)擴(kuò)展的節(jié)點(diǎn)，也就相當(dāng)于兩個(gè)擴(kuò)展方向出現(xiàn)了交點(diǎn)，那么可以認(rèn)為我們找到了一條路徑。雙向廣度優(yōu)先算法相對于廣度優(yōu)先算法來說，由于采用了從兩個(gè)根開始擴(kuò)展的方式，搜索樹的深度得到了明顯的減少，所以在算法的時(shí)間復(fù)雜度和空間復(fù)雜度上都有較大的優(yōu)勢！雙向廣度優(yōu)先算法特別適合于給出了起始節(jié)點(diǎn)和目的節(jié)點(diǎn)，要求他們之間的最短路徑的問題。雙向廣度優(yōu)先搜索雙向廣度優(yōu)先搜索算法是對廣度優(yōu)先算法的一種擴(kuò)88雙向廣度優(yōu)先搜索雙向廣度優(yōu)先算法編程的基本框架如下：數(shù)據(jù)結(jié)構(gòu)：Queueq1,q2;//兩個(gè)隊(duì)列分別用于兩個(gè)方向的擴(kuò)展（注意在一般的廣度優(yōu)先算法中，只需要一個(gè)隊(duì)列）inthead[2],tail[2];//兩個(gè)隊(duì)列的頭指針和尾指針雙向廣度優(yōu)先搜索雙向廣度優(yōu)先算法編程的基本框架如下：89算法流程:一、主控函數(shù):voidsolve(){1.將起始節(jié)點(diǎn)放入隊(duì)列q1,將目的節(jié)點(diǎn)放入隊(duì)列q22.當(dāng)兩個(gè)隊(duì)列都未空時(shí)，作如下循環(huán)

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

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

取隊(duì)列qi的頭結(jié)點(diǎn)H

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

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

2如果adj在隊(duì)列qi中不存在

1）將adj放入隊(duì)列qi

2)

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

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

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

2

3

41

5

x7

6

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

2

34

5

67

8

x輸出在最少移動(dòng)步數(shù)的情況下的移動(dòng)路徑[每次移動(dòng)的方向上下左右依次表示為'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])

{