搜索算法-培訓(xùn)

ACM程序設(shè)計

（2013.7.13~2013.7.31）搜索算法沈云付主要的搜索方法廣度優(yōu)先搜索BFS

深度優(yōu)先搜索DFS

雙向廣度優(yōu)先算法A*算法

廣度優(yōu)先搜索算法BFS框架

記Q為隊列或堆，s是為開始搜索的點voidbranchBound(){Node*Q=NULL;for(s的所有兒子節(jié)點w)if(w是活結(jié)點且符合要求)w入隊列Q;else舍去w;while(Q！=NULL){取Q的頭元素t;

對t的所有兒子節(jié)點w{if(w是葉結(jié)點)計算值及判斷是否當(dāng)前最優(yōu)；else{if(w是且符合要求)w入隊列Q;else舍去w；}}}

BFS實現(xiàn)過程

voidBFS(){初始化表開表OPEN、閉表CLOSED;將s放入OPEN；while(OPEN表不空){從OPEN中取頭結(jié)點node,并從OPEN表刪除node;for(node的子節(jié)點newNode){if(newNode滿足最優(yōu)值要求){打印輸出;found=true;結(jié)束搜索;}

if(newNode不在CLOSED中)將newNode插入OPEN中;若node不在CLOSED中,將其插入CLOSED中；}確定是否有解;}深度優(yōu)先搜索算法DFS實現(xiàn)過程

初始化表OPEN、CLOSED;將s放入OPEN;voidDFS(Nodenode){//遞歸算法

if(node不在CLOSED中)將node插入CLOSED中;

for(node的子節(jié)點newNode){if(newNode滿足最優(yōu)值要求){ 調(diào)整最優(yōu)值和路徑標(biāo)記，或輸出;}

if(newNode不在CLOSED中){ //可檢查是否在OPEN中將newNode壓入OPEN中;DFS(newNode);}}

從OPEN表中移除頭結(jié)點node,并取頭結(jié)點NewNode;DFS(NewNode);}深度優(yōu)先搜索DFS

對于當(dāng)前頂點u，如果u還有以此為起點而未搜索到的邊(u,v)，那么就沿邊(u,v)繼續(xù)搜索下去，即立即搜索頂點v。當(dāng)v及v的所有兒子結(jié)點都被搜索過后，接著搜索u的其他兒子結(jié)點。當(dāng)結(jié)點u的所有邊都已被探尋過，搜索將回溯到結(jié)點u的父結(jié)點。這一過程一直進(jìn)行到找到從源結(jié)點s可達(dá)的滿足要求的結(jié)點或路徑為止。遞歸回溯DFS算法的兩種主要框架

子集樹問題算法框架voidbacktrack(intt){if(t>n)output(x);elsefor(inti=0;i<=1;i++){x[t]=i;if(legal(t))//若合法

backtrack(t+1);}}排列樹問題算法框架voidbacktrack(intt){if(t>n)output(x);elsefor(inti=t;i<=n;i++){swap(x[t],x[i]);if(legal(t))//若合法

backtrack(t+1);swap(x[t],x[i]);}}雙向廣度搜索算法BFS：從初始結(jié)點開始一層層擴展直到找到目標(biāo)結(jié)點，它能較好地解決狀態(tài)不是太多的情況。雙向廣度優(yōu)先算法：可用于操作可逆的廣度優(yōu)先搜索問題。在尋找目標(biāo)結(jié)點或路徑的搜索過程中，初始結(jié)點向目標(biāo)結(jié)點和目標(biāo)結(jié)點向初始結(jié)點同時進(jìn)行擴展，直至在兩個擴展方向上出現(xiàn)同一個子結(jié)點，搜索結(jié)束，這就是雙向搜索過程。雙向搜索過程雙向搜索TBFS()初始工作建立兩組結(jié)點表OPEN_S、CLOSED_S與OPEN_D、CLOSED_D，分別存儲兩個方向上的生成結(jié)點和已擴展結(jié)點。OPEN型表具有“先進(jìn)先出”的隊列（鏈表）結(jié)構(gòu)，稱為“開表”，而CLOSED型表稱為“閉表”。

將起始結(jié)點放入OPEN_S、CLOSED_S表、目標(biāo)結(jié)點放入OPEN_D、CLOSED_D表；檢查起始結(jié)點與目標(biāo)結(jié)點是否相同；若相同則找到解，完成；

雙向搜索TBFS()主要工作found=false;while(!found){if(OPEN_S不空且len(OPEN_S)<len(OPEN_D)){

BFS_expand(OPEN_S,CLOSED_S，OPEN_D,CLOSED_D);elseif(OPEN_D不空且len(OPEN_D)<=len（OPEN_S))BFS_expand(OPEN_D,CLOSED_D,OPEN_S,CLOSED_S); else輸出無解信息，退出循環(huán)；}單向廣度優(yōu)先搜索算法BFS_expand

BFS_expand(OPEN1,CLOSED1,OPEN2,CLOSED2){從OPEN1表中得到第1個結(jié)點tnmNode;

若tnmNode不在CLOSED1中將tnmNode插入CLOSED1中；從OPEN1表中刪除第1個結(jié)點;

for（每個tnmNode的子節(jié)點newNode）{

if(newNode在CLOSED2中){//即newNode是目標(biāo)節(jié)點

打印輸出;found=true;結(jié)束搜索;}

if(newNode不在CLOSED1中)將newNode插入OPEN1中;}}實例研究

1、跳馬問題

問題描述給定8*8方格棋盤，求棋盤上一只馬從一個位置到達(dá)另一位置的最短路徑長。注意馬是走“日”形的。輸入：輸入有若干測試數(shù)據(jù)。每組測試數(shù)據(jù)僅1行，每行上有2個方格pos1、pos2，之間用一個空格隔開，每格方格表示棋盤上的一個位置，該位置由表示列的1個字母（a-h）及表示行的一個數(shù)字（1-8）構(gòu)成，如“d7”表示第4列第7行。

輸出：對輸入中每行上的2個方格pos1、pos2，輸出馬從位置pos1跳到pos2所需的最短路徑長。如“a1==>a2:3moves”表示從位置a1跳到a2所需的最少步數(shù)是3。輸入樣例a1a2a1a3a1h8g2b8

輸出樣例a1==>a2:3movesa1==>a3:2movesa1==>h8:6movesg2==>b8:5moves

跳馬問題的廣度優(yōu)先搜索分析建立一個隊列Q，用于存放搜索到的位置，并考慮限界剪枝解空間是一個圖，8叉樹求解方法S0：起始位置start第一個擴展S1：依次考慮從A1步可達(dá)的方格，標(biāo)記并存入隊列Q。S2：從隊列中取出一個結(jié)點B，作處理標(biāo)記，并標(biāo)記所有從B1步可達(dá)的未被標(biāo)記的方格C，步數(shù)是B的步數(shù)加1，存入活結(jié)點隊列QS3：如果Q不空并且未到達(dá)目標(biāo)方格finish，轉(zhuǎn)S2，否則結(jié)束搜索圖示23232323132323232333二維數(shù)組grid[13][13]:表示棋盤陣列初始時，最外圍的2層被封鎖grid[i][j]=0：該方格允許放棋子grid[i][j]=1：該方格被封鎖，不允許放棋子方向標(biāo)志為offset[8]#include<iostream>#include<queue>usingnamespacestd;strucPosition{public:introw;intcol;};boolFindPath(Positionstart,Positionfinish,int&PathLen){if((start.row==finish.row)&&(start.col==finish.col)){PathLen=0;returntrue;}inti,j,grid[13][13];for(i=1;i<=12;i++)grid[1][i]=grid[2][i]=grid[11][i]=grid[12][i]=1;

for(i=3;i<=10;i++)grid[i][1]=grid[i][2]=grid[i][11]=grid[i][12]=1;for(i=3;i<=10;i++)for(j=3;j<=10;j++)grid[i][j]=0;Positionoffset[8];offset[0].row=-2;offset[0].col=1;offset[1].row=-1;offset[1].col=2;offset[2].row=1;offset[2].col=2;offset[3].row=2;offset[3].col=1;offset[4].row=2;offset[4].col=-1;offset[5].row=1;offset[5].col=-2;offset[6].row=-1;offset[6].col=-2;offset[7].row=-2;offset[7].col=-1;

intNumOfNbrs=8;Positionhere,nbr;here.row=start.row;here.col=start.col;grid[start.row][start.col]=2;queue<Position>Q;do{for(i=0;i<NumOfNbrs;i++){nbr.row=here.row+offset[i].row;nbr.col=here.col+offset[i].col;if(grid[nbr.row][nbr.col]==0){grid[nbr.row][nbr.col]=grid[here.row][here.col]+1;if((nbr.row==finish.row)&&(nbr.col==finish.col))break;Q.push(nbr);}}if((nbr.row==finish.row)&&(nbr.col==finish.col))break;if(Q.empty())returnfalse;here=Q.front();Q.pop();}while(true);PathLen=grid[finish.row][finish.col]-2;returntrue;}intmain(){charcs,cf;intrs,rf,PathLen;while(cin>>cs){ for(inta=0;a<500;a++)if(cs=='0')return0;cin>>rs>>cf>>rf;Positionstart,finish;start.row=rs+2;start.col=cs-'a'+3;finish.row=rf+2;finish.col=cf-'a'+3;FindPath(start,finish,PathLen);cout<<cs<<rs<<"==>"<<cf<<rf<<":"<<""<<PathLen<<"moves"<<endl;}return0;}跳馬問題的深度優(yōu)先搜索#include<iostream>usingnamespacestd;constintROW,COL=8;inttable[ROW][COL];intoffc[8]={1,2,-1,1,2,-2,-2,-1},offl[8]={2,1,2,-2,-1,1,-1,-2};intnewx,newy;intfind(intx,inty,intc){for(inti=0;i<ROW;i++){ newx=x+offc[i];newy=y+offl[i]; if((newx<ROW)&&(newx>=0)&&(newy<COL)&&(newy>=0)) if(table[newx][newy]>c){table[newx][newy]=c;

find(newx,newy,c+1);}} return0;}intmain(){ charx[10],y[10];intc1,l1,c2,l2,i,j;while(cin>>x>>y){c1=x[0]-'a'; c2=y[0]-'a';l1=x[1]-'0'-1;l2=y[1]-'0'-1; for(i=0;i<ROW;i++) for(j=0;j<COL;j++)table[i][j]=1000; table[c1][l1]=0;find(c1,l1,1); cout<<x<<"==>"<<y<<":"<<table[c2][l2]<<"moves"<<endl; }return0;}無向圖的連通分支

問題描述

輸入一個無向圖G，計算G的連通分支數(shù)。

輸入有多個無向圖數(shù)據(jù)。每個無向描述的第1行是兩個整數(shù)n和e，分別表示頂點數(shù)和邊數(shù)。接著有e行，每行有2個整數(shù)a、b，分別是一條邊的兩個端點（起點和終點）。兩個圖之間空一行。輸出對每個無向圖，輸出圖中連通分支個數(shù)。輸入輸出樣例輸入樣例2112

581213141523243445輸出樣例11

輸入處理#include<iostream>usingnamespacestd;constintMAXN=50;intn,e;intgraph[MAXN][MAXN],mark[MAXN];voidinput(){ inti,j,u,v; for(i=0;i<MAXN;++i) for(j=0;j<MAXN;++j)graph[i][j]=0;//初始化

for(i=1;i<=e;++i){ cin>>u>>v; graph[u][v]=graph[v][u]=1; }}深度優(yōu)先搜索子過程voiddfs(ints){ inti; mark[s]=true; for(i=1;i<=n;++i){ if(graph[s][i]&&!mark[i]) dfs(i); }}深度優(yōu)先搜索全過程voidsearch(){ intres=0,i; for(i=0;i<MAXN;++i) mark[i]=false; for(i=1;i<=n;++i){ if(!mark[i]){ ++res;dfs(i); } } cout<<res<<endl;}主程序intmain(){ while(cin>>n>>e) { input(); search(); } return0;}2、通訊團體

問題描述：有一家通訊公司近來要推出一項優(yōu)惠活動，凡是在某個群體中相互通話的用戶可以得到某種通話費折扣優(yōu)惠。A、B兩個用戶相互通話是指其中之一（如A）與另一個人（如B）打過電話，而不必要求B打電話給A。一個群體G要滿足通訊公司的優(yōu)惠政策，它必須滿足兩個條件：（1）G中任何兩個用戶通過話；（2）G是團體，即，如再加一個G外的人進(jìn)去，所得新群體是不滿足條件（1）的。任務(wù)：計算出這公司的所有用戶構(gòu)成的群體中最大團體的用戶數(shù)。最大團體是所有團體中用戶數(shù)最多的團體，可能不止一個，但所有最大團體中用戶數(shù)是一樣的。輸入：

輸入有若干組測試數(shù)據(jù)，每組測試數(shù)據(jù)的第一行上有一個整數(shù)n，(1<=n<=50)，是通訊公司的用戶數(shù)。接下來的n行是這n個人的通訊狀況，其第i行是0、1序列，長為n，序列之間無空格。該行第j個位置的數(shù)如為1表示i與j通過電話；如為0則表示未通過話。相鄰兩組測試之間無空行。輸入直到文件結(jié)束。輸出：

對輸入中的每組測試數(shù)據(jù)，在輸出文件中輸出對應(yīng)的最大團體的用戶數(shù)m。對第i組測試數(shù)據(jù)，先在一行上輸出“Casei：”，接著輸出m，見樣例。

輸入樣例：50101110101010011000111110輸出樣例：Case1:3

分析本題要確定最大團體人員數(shù)，基本的思想是從第一個人開始考察他是否在最大團體中。如前面的i-1人已被考察過，且前面的i-1人中已有cnt人構(gòu)成一個團，現(xiàn)考察第i人能否在該團中。繼續(xù)這個工作，直到所有人都被考察一遍。

用深度優(yōu)先回溯方法。

#include<iostream>usingnamespacestd;constintMAXN=100;intx[MAXN],bestx[MAXN],n,a[MAXN][MAXN],bestn,cn;voidbacktrack(inti){if(i>n-1){//到達(dá)葉結(jié)點

for(intj=0;j<n;j++)bestx[j]=x[j];bestn=cn;return;}//檢查頂點

i與當(dāng)前團的連接intok=1;for(intj=0;j<i;j++) if((x[j]==1)&&(!a[i][j])){//考察：

i與前面的j是否相連

ok=0; break; }//i與前面的j不相連，舍棄i if(ok){//進(jìn)入左子樹

x[i]=1;cn++; backtrack(i+1); cn--;}if(cn+n-i>bestn){//進(jìn)入右子樹x[i]=0;backtrack(i+1);} return;}intmain(){inti,j,num=0;charc[MAXN][MAXN];while(cin>>n) {//團體大小nbestn=0;cn=0;num++;cin.get(); for(i=0;i<n;i++)//輸入團體中人員的關(guān)系信息

cin.getline(c[i],MAXN); for(i=0;i<n;i++) for(j=0;j<n;j++) a[i][j]=c[i][j]-48;//轉(zhuǎn)換為鄰接矩陣

backtrack(0);//回溯法搜索

cout<<"Case"<<num<<":"<<bestn<<endl;} return0;}

3、緣份問題描述：給出n個男女生之間的緣分值，按一定的規(guī)則對男女生配對，求所有配對男女生間的男女緣分和的最大值。規(guī)則是：每一個男生只可選擇一位女生，兩個男生不可選擇同一位女生。輸入：輸入有若干測試數(shù)據(jù)。每一組測試數(shù)據(jù)的第一行為一個整數(shù)n，表示分別有n個男生與n個女生；接下來的n行中每行有n個整數(shù)，之間用空格隔開，依次表示第i個男生對第1,2,…,n個女生的緣分值ti1，ti2，…,tin。當(dāng)輸入的整數(shù)n均為0時，表示輸入結(jié)束。輸出：對每組測試數(shù)據(jù)，輸出一行，內(nèi)容是該測試數(shù)據(jù)下男女生間的男女緣分和的最大值。輸入樣例：573241254037344541936255170輸出樣例：32分析用數(shù)組t[MAXN][MAXN]記錄男女生的緣分值，即t[i][j]表示第i個男生與第j個女生的緣分值。用visited[j]記錄第j個已被選擇與否12345173241225403373445441936525517分析-遞歸回溯從第1個男生開始，每個嘗試選擇0~n-1中的女生之一，模仿n皇后問題。如果第j個女生未被選擇，那么選擇她，即使visited[j]=true；緣分和sum增加。假如還沒有選完所有女生，那么繼續(xù)進(jìn)行選擇；否則將當(dāng)前的緣分值與目前最大的緣分值maximum比較，看是否需要修正。假如第j個女生的選擇無法獲得更大的緣分值，那么應(yīng)該回退，此時將女生j標(biāo)識不被選擇；且緣分值和扣除#include<fstream>usingnamespacestd;intt[10][10],num,maximum,sum;boolvisited[10];voidlove(inti){ intj; for(j=0;j<num;j++) if(!visited[j]) { visited[j]=true;sum+=t[i][j]; if(i<num-1)love(i+1); elseif(sum>maximum)maximum=sum; visited[j]=false; sum-=t[i][j]; }}intmain(){ cin>>num; while(num!=0){ for(inti=0;i<num;i++){ visited[i]=false; for(intj=0;j<num;j++)cin>>t[i][j]; } maximum=0; sum=0; love(0); cout<<maximum<<endl; cin>>num; } return0;}4、相異數(shù)字序列問題

問題描述

給