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

1、ACM程序設(shè)計程序設(shè)計 （2013. 7.13 2013.7.31）搜索算法搜索算法沈云付沈云付主要的搜索方法主要的搜索方法 廣度優(yōu)先搜索廣度優(yōu)先搜索 BFSBFS 深度優(yōu)先搜索深度優(yōu)先搜索 DFSDFS 雙向廣度優(yōu)先算法雙向廣度優(yōu)先算法 A A* *算法算法 廣度優(yōu)先搜索算法廣度優(yōu)先搜索算法BFSBFS框架框架 記記Q為隊列或堆，為隊列或堆，s是為開始搜索的點是為開始搜索的點void branchBound ()void branchBound () Node Node * *Q=NULL; Q=NULL; for(s for(s的所有兒子節(jié)點的所有兒子節(jié)點w) w) if (w if (w

2、是活結(jié)點且符合要求是活結(jié)點且符合要求) ) w w入隊列入隊列Q;Q; else else 舍去舍去w;w; while (Q while (Q！=NULL) =NULL) 取取Q Q的頭元素的頭元素t; t; 對對t t的所有兒子節(jié)點的所有兒子節(jié)點ww if (w if (w是葉結(jié)點是葉結(jié)點) ) 計算值及判斷是否當(dāng)前最優(yōu)；計算值及判斷是否當(dāng)前最優(yōu)； else if (w else if (w是且符合要求是且符合要求) ) w w入隊列入隊列Q;Q; else else 舍去舍去w w； BFS實現(xiàn)過程實現(xiàn)過程 void BFS() 初始化表開表初始化表開表OPEN、閉表閉表CLOSED;將

3、將s放入放入OPEN； while(OPEN表不空表不空) 從從OPEN中取頭結(jié)點中取頭結(jié)點node,并從并從OPEN表刪除表刪除node; for (node的子節(jié)點的子節(jié)點newNode) if (newNode滿足最優(yōu)值要求滿足最優(yōu)值要求) 打印輸出打印輸出; found = true; 結(jié)束搜索結(jié)束搜索; if(newNode不在不在CLOSED中中) 將將newNode插入插入OPEN中中; 若若node不在不在CLOSED中中,將其插入將其插入CLOSED中；中； 確定是否有解確定是否有解; 深度優(yōu)先搜索算法深度優(yōu)先搜索算法DFSDFS實現(xiàn)過程實現(xiàn)過程 初始化表初始化表OPEN、C

4、LOSED;將將s放入放入OPEN; void DFS(Node node) /遞歸算法遞歸算法 if(node不在不在CLOSED中中) 將將node插入插入CLOSED中中; for (node的子節(jié)點的子節(jié)點newNode) if (newNode滿足最優(yōu)值要求滿足最優(yōu)值要求) 調(diào)整最優(yōu)值和路徑標(biāo)記，或輸出調(diào)整最優(yōu)值和路徑標(biāo)記，或輸出; if(newNode不在不在CLOSED中中) /可檢查是否在可檢查是否在OPEN中中 將將newNode壓入壓入OPEN中中; DFS(newNode); 從從OPEN表中移除頭結(jié)點表中移除頭結(jié)點node, 并取頭結(jié)點并取頭結(jié)點NewNode; DFS

5、(NewNode); 深度優(yōu)先搜索深度優(yōu)先搜索DFSDFS 對于當(dāng)前頂點對于當(dāng)前頂點u u，如果如果u u還有以此為起點而未搜還有以此為起點而未搜索到的邊索到的邊( (u u, ,v v) )，那么就沿邊那么就沿邊( (u u, ,v v) )繼續(xù)搜索下繼續(xù)搜索下去，即立即搜索頂點去，即立即搜索頂點v v。當(dāng)當(dāng)v v及及v v的所有兒子結(jié)的所有兒子結(jié)點都被搜索過后，接著搜索點都被搜索過后，接著搜索u u的其他兒子結(jié)點。的其他兒子結(jié)點。當(dāng)結(jié)點當(dāng)結(jié)點u u的所有邊都已被探尋過，搜索將回溯的所有邊都已被探尋過，搜索將回溯到結(jié)點到結(jié)點u u的父結(jié)點。這一過程一直進行到找到的父結(jié)點。這一過程一直進行到找

6、到從源結(jié)點從源結(jié)點s s可達的滿足要求的結(jié)點或路徑為止。可達的滿足要求的結(jié)點或路徑為止。遞歸回溯遞歸回溯DFSDFS算法的兩種主要框架算法的兩種主要框架 子集樹問題算法框架子集樹問題算法框架void backtrack (int t)void backtrack (int t) if (tn) if (tn) output(x); output(x); else else for (int i=0;i=1;i+) for (int i=0;in) output(x); if (tn) output(x); else for (int i=t;i=n;i+) else for (int i=t;

7、i=n;i+) swap(xt, xi); swap(xt, xi); if (legal(t) / if (legal(t) /若合法若合法 backtrack(t+1);backtrack(t+1); swap(xt, xi); swap(xt, xi); 雙向廣度搜索算法雙向廣度搜索算法 BFS：從初始結(jié)點開始一層層擴展直到找到目標(biāo)結(jié)從初始結(jié)點開始一層層擴展直到找到目標(biāo)結(jié)點，它能較好地解決狀態(tài)不是太多的情況。點，它能較好地解決狀態(tài)不是太多的情況。 雙向廣度優(yōu)先算法：可用于操作可逆的廣度優(yōu)先搜雙向廣度優(yōu)先算法：可用于操作可逆的廣度優(yōu)先搜索問題。在尋找目標(biāo)結(jié)點或路徑的搜索過程中，初索問題。在

8、尋找目標(biāo)結(jié)點或路徑的搜索過程中，初始結(jié)點向目標(biāo)結(jié)點和目標(biāo)結(jié)點向初始結(jié)點同時進行始結(jié)點向目標(biāo)結(jié)點和目標(biāo)結(jié)點向初始結(jié)點同時進行擴展，直至在兩個擴展方向上出現(xiàn)同一個子結(jié)點，擴展，直至在兩個擴展方向上出現(xiàn)同一個子結(jié)點，搜索結(jié)束，這就是雙向搜索過程。搜索結(jié)束，這就是雙向搜索過程。 雙向搜索雙向搜索過程過程K B C D E F H A I S J O Y R1 U V W L X M N R J1 K1 C1 D1 F1 A1 G1 T B1 L1 P1 M1 N1 O1 Q1 H1 G I1 E1 雙向搜索雙向搜索TBFS()TBFS()初始工作初始工作 建立兩組結(jié)點表建立兩組結(jié)點表 OPEN_SOP

9、EN_S、CLOSED_SCLOSED_S與與OPEN_DOPEN_D、CLOSED_DCLOSED_D，分別存儲兩個方向上的生成結(jié)點和已分別存儲兩個方向上的生成結(jié)點和已擴展結(jié)點。擴展結(jié)點。 OPENOPEN型表具有型表具有“先進先出先進先出”的隊列（鏈表）結(jié)構(gòu)，的隊列（鏈表）結(jié)構(gòu)，稱為稱為“開表開表”，而，而CLOSEDCLOSED型表稱為型表稱為“閉表閉表”。 將起始結(jié)點放入將起始結(jié)點放入OPEN_SOPEN_S、CLOSED_SCLOSED_S表、目標(biāo)結(jié)點表、目標(biāo)結(jié)點放入放入OPEN_DOPEN_D、CLOSED_DCLOSED_D表；表； 檢查起始結(jié)點與目標(biāo)結(jié)點是否相同；若相同則找檢查

10、起始結(jié)點與目標(biāo)結(jié)點是否相同；若相同則找到解到解，完成，完成； 雙向搜索雙向搜索TBFS()TBFS()主要工作主要工作found = false; while(!found) if (OPEN_S不空且不空且len(OPEN_S)len(OPEN_D) BFS_expand(OPEN_S,CLOSED_S，OPEN_D,CLOSED_D); else if(OPEN_D不空且不空且len(OPEN_D)a2: 3 movesa1=a2: 3 moves”表示表示從位置從位置a1a1跳到跳到a2a2所需的所需的最少步數(shù)是最少步數(shù)是3 3。輸入樣例輸入樣例a1 a2a1 a2a1 a3a1 a3a

11、1 h8a1 h8g2 b8g2 b8 輸出樣例輸出樣例a1=a2: 3 movesa1=a2: 3 movesa1=a3: 2 movesa1=a3: 2 movesa1=h8: 6 movesa1=h8: 6 movesg2=b8: 5 movesg2=b8: 5 moves 跳馬問題的廣度優(yōu)先搜索跳馬問題的廣度優(yōu)先搜索分析分析建立一個隊列建立一個隊列Q Q，用于存放搜索到的位置，并考慮限界剪枝用于存放搜索到的位置，并考慮限界剪枝解空間是一個圖，解空間是一個圖，8 8叉樹叉樹求解方法求解方法S0S0：起始位置起始位置startstart第一個擴展第一個擴展S1S1：依次考慮從依次考慮從A

12、A 1 1步可達的方格，標(biāo)記并存入隊列步可達的方格，標(biāo)記并存入隊列Q Q。S2S2：從隊列中取出一個結(jié)點從隊列中取出一個結(jié)點B B，作處理標(biāo)記，并標(biāo)記所有從作處理標(biāo)記，并標(biāo)記所有從B B 1 1步可達的未被標(biāo)記的方格步可達的未被標(biāo)記的方格C C，步數(shù)是步數(shù)是B B的步數(shù)加的步數(shù)加1 1，存入，存入活結(jié)點隊列活結(jié)點隊列Q QS3S3：如果如果Q Q不空并且未到達目標(biāo)方格不空并且未到達目標(biāo)方格finishfinish，轉(zhuǎn)轉(zhuǎn)S2S2，否則結(jié)否則結(jié)束搜索束搜索圖示圖示23232323132323232333 二二維數(shù)組維數(shù)組grid1313:grid1313:表示棋盤陣列表示棋盤陣列 初始時，最外圍的

13、初始時，最外圍的2 2層被封鎖層被封鎖gridij=gridij= 0：該方格允許放棋子該方格允許放棋子gridij=gridij= 1：該方格被封鎖，不允許放該方格被封鎖，不允許放棋子棋子 方向標(biāo)志為方向標(biāo)志為offset8#include #include using namespace std; struc Position public: int row; int col; ; bool FindPath(Position start,Position finish, int& PathLen) if (start.row = finish.row) & (start.

14、col = finish.col) PathLen =0; return true; int i,j, grid1313; for(i = 1; i = 12; i+) grid1i=grid2i=grid11i=grid12i=1; for(i = 3; i = 10; i+) gridi1=gridi2=gridi11=gridi12=1; for(i = 3; i = 10; i+) for(j = 3; j = 10; j+) gridij = 0; Position offset8; offset0.row = -2; offset0.col = 1; offset1.row = -

15、1; offset1.col = 2; offset2.row = 1; offset2.col = 2; offset3.row = 2; offset3.col = 1; offset4.row = 2; offset4.col = -1; offset5.row = 1; offset5.col = -2; offset6.row = -1; offset6.col = -2; offset7.row = -2; offset7.col = -1; int NumOfNbrs = 8; Position here, nbr; here.row = start.row; here.col

16、= start.col; gridstart.rowstart.col=2; queue Q; do for (i=0; ics) for ( int a=0;arscfrf; Position start,finish; start.row=rs+2; start.col=cs-a+3; finish.row=rf+2; finish.col=cf-a+3; FindPath(start,finish,PathLen); coutcsrscfrf: PathLen movesendl; return 0; 跳馬問題的深度優(yōu)先搜索跳馬問題的深度優(yōu)先搜索#include using namesp

17、ace std;const int ROW, COL=8;int tableROWCOL;int offc8 = 1,2, -1, 1, 2, -2, -2, -1, offl8 = 2,1, 2, -2, -1, 1, -1, -2;int newx, newy;int find(int x, int y, int c) for (int i = 0; i ROW; i+) newx = x + offci; newy = y + offli; if (newx = 0)&(newy = 0) if (tablenewxnewy c) tablenewxnewy = c; find(

18、newx, newy, c + 1); return 0; int main() char x10, y10; int c1, l1, c2, l2, i, j; while(cinxy) c1 = x0 - a; c2 = y0 - a; l1 = x1 - 0 - 1; l2 = y1 - 0 - 1; for (i = 0; i ROW; i+) for (j = 0; j COL; j+) tableij = 1000; tablec1l1 = 0; find(c1, l1, 1); coutxy: tablec2l2 moves endl; return 0; 無向圖的連通分支無向圖

19、的連通分支 問題描述問題描述 輸入一個無向圖G，計算G的連通分支數(shù)。 輸入輸入 有多個無向圖數(shù)據(jù)。每個無向描述的第1行是兩個整數(shù)n和e，分別表示頂點數(shù)和邊數(shù)。接著有e行，每行有2個整數(shù)a、b，分別是一條邊的兩個端點（起點和終點）。兩個圖之間空一行。輸出輸出 對每個無向圖，輸出圖中連通分支個數(shù)。 輸入輸出樣例輸入輸出樣例輸入樣例輸入樣例2 11 2 5 81 21 31 41 52 32 43 44 5輸出樣例輸出樣例11 輸入處理輸入處理#include using namespace std;const int MAXN=50;int n,e;int graphMAXNMAXN,markMA

20、XN;void input()int i,j,u,v;for(i=0;iMAXN;+i)for(j=0;jMAXN;+j)graphij=0; /初始化for(i=1;iuv; graphuv=graphvu=1;深度優(yōu)先搜索子過程void dfs(int s)int i;marks=true;for(i=1;i=n;+i)if(graphsi & !marki)dfs(i);深度優(yōu)先搜索全過程void search()int res=0,i;for(i=0;iMAXN;+i) marki=false;for(i=1;i=n;+i)if(!marki)+res; dfs(i);cout

21、resne)input();search();return 0;2 2、通訊團體、通訊團體 問題描述：問題描述： 有一家通訊公司近來要推出一項優(yōu)惠活動，凡是在某個群體中有一家通訊公司近來要推出一項優(yōu)惠活動，凡是在某個群體中相互通話的用戶可以得到某種通話費折扣優(yōu)惠。相互通話的用戶可以得到某種通話費折扣優(yōu)惠。A A、B B兩個用戶兩個用戶相互通話是指其中之一（如相互通話是指其中之一（如A A）與另一個人（如與另一個人（如B B）打過電話，打過電話，而不必要求而不必要求B B打電話給打電話給A A。 一個群體一個群體G G要滿足通訊公司的優(yōu)惠政策，它必須滿足兩個條件：要滿足通訊公司的優(yōu)惠政策，它必須

22、滿足兩個條件：（1 1）G G中任何兩個用戶通過話；中任何兩個用戶通過話；（2 2）G G是團體，即，如再加一個是團體，即，如再加一個G G外的人進去，所得新群體是不外的人進去，所得新群體是不滿足條件（滿足條件（1 1）的。）的。 任務(wù)：計算出這公司的所有用戶構(gòu)成的群體中最大團體的用戶任務(wù)：計算出這公司的所有用戶構(gòu)成的群體中最大團體的用戶數(shù)。最大團體是所有團體中用戶數(shù)最多的團體，可能不止一個，數(shù)。最大團體是所有團體中用戶數(shù)最多的團體，可能不止一個，但所有最大團體中用戶數(shù)是一樣的。但所有最大團體中用戶數(shù)是一樣的。輸入：輸入： 輸入有若干組測試數(shù)據(jù)，每組測試數(shù)據(jù)的第一行上有輸入有若干組測試數(shù)據(jù)，每

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

24、出文件中輸出對應(yīng)的最大團體的用戶數(shù)的最大團體的用戶數(shù)m。對第對第i組測試數(shù)據(jù)，先在一組測試數(shù)據(jù)，先在一行上輸出行上輸出“Case i：”，接著輸出接著輸出m，見樣例。見樣例。 輸入樣例：輸入樣例：5 5 01011010111010110101010010100110001100011111011110輸出樣例：輸出樣例：Case 1: 3 分析分析 本題要確定最大團體人員數(shù)，基本的思想是從第本題要確定最大團體人員數(shù)，基本的思想是從第一個人開始考察他是否在最大團體中。如前面的一個人開始考察他是否在最大團體中。如前面的i-1人已被考察過，且前面的人已被考察過，且前面的i-1人中已有人中已有cnt

25、人構(gòu)成人構(gòu)成一個團，現(xiàn)考察第一個團，現(xiàn)考察第i人能否在該團中。繼續(xù)這個工人能否在該團中。繼續(xù)這個工作，直到所有人都被考察一遍。作，直到所有人都被考察一遍。 用深度優(yōu)先回溯方法。用深度優(yōu)先回溯方法。 # #includeincludeusing namespace std;using namespace std;const int MAXN=100;const int MAXN=100;int xMAXN,bestxMAXN, n, int xMAXN,bestxMAXN, n, aMAXNMAXN, bestn,cn; aMAXNMAXN, bestn,cn;void backtrack(in

26、t i) void backtrack(int i) if (i n-1) / if (i n-1) / 到達葉結(jié)點到達葉結(jié)點 for (int j = 0; j n; j+) for (int j = 0; j n; j+) bestxj = xj; bestxj = xj; bestn = cn; return; bestn = cn; return; / / 檢查頂點檢查頂點 i i 與當(dāng)前團的連接與當(dāng)前團的連接int ok = 1;int ok = 1; for (int j =0; j i; j+) for (int j =0; j bestn) if (cn + n - i bes

27、tn) / / 進入右子樹進入右子樹 xi = 0; backtrack(i + 1); xi = 0; backtrack(i + 1); return ;return ; int main()int main()int i,j,num=0;int i,j,num=0;char cMAXNMAXN;char cMAXNMAXN;while (cinn)while (cinn) / /團體大小團體大小n n bestn=0; cn=0; num+; cin.get(); bestn=0; cn=0; num+; cin.get();for(i=0;in;i+) /for(i=0;in;i+)

28、/輸入團體中人員的關(guān)系信息輸入團體中人員的關(guān)系信息cin.getline(ci, MAXN); cin.getline(ci, MAXN); for(i=0;in;i+)for(i=0;in;i+)for(j=0;jn;j+)for(j=0;jn;j+)aij=cij-48; /aij=cij-48; /轉(zhuǎn)換為鄰接矩陣轉(zhuǎn)換為鄰接矩陣backtrack(0); /backtrack(0); /回溯法搜索回溯法搜索coutCase num: bestnendl;coutCase num: bestnendl; return 0;return 0; 3 3、緣份、緣份問題描述：問題描述：給出給出n

29、n個男女生之間的緣分值，按一定的個男女生之間的緣分值，按一定的規(guī)則對男女生配對，求所有配對男女生間的男女緣規(guī)則對男女生配對，求所有配對男女生間的男女緣分和的最大值。規(guī)則是：每一個男生只可選擇一位分和的最大值。規(guī)則是：每一個男生只可選擇一位女生，兩個男生不可選擇同一位女生。女生，兩個男生不可選擇同一位女生。輸入：輸入：輸入有若干測試數(shù)據(jù)。每一組測試數(shù)據(jù)的第一輸入有若干測試數(shù)據(jù)。每一組測試數(shù)據(jù)的第一行為一個整數(shù)行為一個整數(shù)n n，表示分別有表示分別有n n個男生與個男生與n n個女生；個女生；接下來的接下來的n n行中每行有行中每行有n n個整數(shù)，之間用空格隔開，個整數(shù)，之間用空格隔開，依次表示第

30、依次表示第i i個男生對第個男生對第1,2,1,2, ,n n個女生的緣分值個女生的緣分值t ti1i1，t ti2i2，, t, tinin。當(dāng)輸入的整數(shù)當(dāng)輸入的整數(shù)n n均為均為0 0時，表示時，表示輸入結(jié)束。輸入結(jié)束。輸出：輸出：對每組測試數(shù)據(jù)，輸出一行，內(nèi)容是該測試數(shù)對每組測試數(shù)據(jù)，輸出一行，內(nèi)容是該測試數(shù)據(jù)下男女生間的男女緣分和的最大值。據(jù)下男女生間的男女緣分和的最大值。輸入樣例：輸入樣例： 5 57 3 2 4 17 3 2 4 12 5 4 0 32 5 4 0 37 3 4 4 57 3 4 4 54 1 9 3 64 1 9 3 62 5 5 1 72 5 5 1 70 0輸

31、出樣例：輸出樣例：3232分析分析用數(shù)組用數(shù)組tMAXNMAXN記錄男女生的緣分值，即記錄男女生的緣分值，即tij表示第表示第i個男生與第個男生與第j個女生的緣分值。個女生的緣分值。用用visitedj記錄第記錄第j個已被選擇與否個已被選擇與否1 2 3 4 517 3 2 4 122 5 4 0 337 3 4 4 544 1 9 3 652 5 5 1 7分析分析-遞歸回溯遞歸回溯從第從第1個男生開始，每個嘗試選擇個男生開始，每個嘗試選擇0n-1中的女生中的女生之一，模仿之一，模仿n皇后問題?；屎髥栴}。如果第如果第j個女生未被選擇，那么選擇她，即使個女生未被選擇，那么選擇她，即使visit

32、edj=true；緣分和緣分和sum增加。假如還沒有增加。假如還沒有選完所有女生，那么繼續(xù)進行選擇；否則將當(dāng)選完所有女生，那么繼續(xù)進行選擇；否則將當(dāng)前的緣分值與目前最大的緣分值前的緣分值與目前最大的緣分值maximum比比較，看是否需要修正。較，看是否需要修正。假如第假如第j個女生的選擇無法獲得更大的緣分值，個女生的選擇無法獲得更大的緣分值，那么應(yīng)該回退，此時將女生那么應(yīng)該回退，此時將女生j標(biāo)識不被選擇；標(biāo)識不被選擇；且緣分值和扣除且緣分值和扣除#include using namespace std;int t1010, num,maximum,sum;bool visited10;void

33、 love(int i)int j;for(j=0;jnum;j+)if(!visitedj) visitedj=true; sum+=tij;if(imaximum) maximum=sum;visitedj=false; sum-=tij;int main()cinnum;while(num!=0) for(int i=0;inum;i+)visitedi=false;for(int j=0;jtij;maximum=0; sum=0;love(0);coutmaximumnum;return 0;4 4、相異數(shù)字序列問題、相異數(shù)字序列問題 問題描述問題描述 給定整數(shù)給定整數(shù)m=2，長度為

34、長度為4的的0-1序列序列0011。假如把該序列頭尾。假如把該序列頭尾相接，構(gòu)成環(huán)狀，如圖（相接，構(gòu)成環(huán)狀，如圖（a）所示。如果沿著該環(huán)的某個位所示。如果沿著該環(huán)的某個位置，如頂上開始，以順（逆）時針方向，取置，如頂上開始，以順（逆）時針方向，取m個元素，可得個元素，可得00，再變動一個位置，又可得，再變動一個位置，又可得01，用同樣方法可得，用同樣方法可得11，10。有有4 4 個長度為個長度為2的的0- -1序列序列00，01，11，10，表示不同的十進，表示不同的十進制數(shù)制數(shù)0，1，3，2。 對于整數(shù)對于整數(shù)m=3，長度為長度為8的的0-1序列序列00010111頭尾相接構(gòu)成環(huán)頭尾相接構(gòu)成環(huán)狀后如圖（狀后如圖（b）所示。取到所示。取到8個長度為個長度為m=3的的0- -1序列序列 000、001、010、101、011、111、110、100 它們代表了不相同的十進制數(shù)它們代表了不相同的十進制數(shù)0，1，2，5，3，7，6，4，且，且均小于均小于8。 0 1 0 1 （a) m=2 0 1 0 0 （b） m=3 0 1 1 1 你的任務(wù)是，給你一個整數(shù)你的任務(wù)是，給你一個整數(shù)m，找出這樣一個找出這樣一個長為長為2m的的0- -1序列，使得依次取長為序列，使得依次取