搜索算法-培训

1、ACM程序设计程序设计 （2013. 7.13 2013.7.31）搜索算法搜索算法沈云付沈云付主要的搜索方法主要的搜索方法 广度优先搜索广度优先搜索 BFSBFS 深度优先搜索深度优先搜索 DFSDFS 双向广度优先算法双向广度优先算法 A A* *算法算法 广度优先搜索算法广度优先搜索算法BFSBFS框架框架 记记Q为队列或堆，为队列或堆，s是为开始搜索的点是为开始搜索的点void branchBound ()void branchBound () Node Node * *Q=NULL; Q=NULL; for(s for(s的所有儿子节点的所有儿子节点w) w) if (w if (w

2、是活结点且符合要求是活结点且符合要求) ) w w入队列入队列Q;Q; else else 舍去舍去w;w; while (Q while (Q！=NULL) =NULL) 取取Q Q的头元素的头元素t; t; 对对t t的所有儿子节点的所有儿子节点ww if (w if (w是叶结点是叶结点) ) 计算值及判断是否当前最优；计算值及判断是否当前最优； else if (w else if (w是且符合要求是且符合要求) ) w w入队列入队列Q;Q; else else 舍去舍去w w； BFS实现过程实现过程 void BFS() 初始化表开表初始化表开表OPEN、闭表闭表CLOSED;将

3、将s放入放入OPEN； while(OPEN表不空表不空) 从从OPEN中取头结点中取头结点node,并从并从OPEN表删除表删除node; for (node的子节点的子节点newNode) if (newNode满足最优值要求满足最优值要求) 打印输出打印输出; found = true; 结束搜索结束搜索; if(newNode不在不在CLOSED中中) 将将newNode插入插入OPEN中中; 若若node不在不在CLOSED中中,将其插入将其插入CLOSED中；中； 确定是否有解确定是否有解; 深度优先搜索算法深度优先搜索算法DFSDFS实现过程实现过程 初始化表初始化表OPEN、C

4、LOSED;将将s放入放入OPEN; void DFS(Node node) /递归算法递归算法 if(node不在不在CLOSED中中) 将将node插入插入CLOSED中中; for (node的子节点的子节点newNode) if (newNode满足最优值要求满足最优值要求) 调整最优值和路径标记，或输出调整最优值和路径标记，或输出; if(newNode不在不在CLOSED中中) /可检查是否在可检查是否在OPEN中中 将将newNode压入压入OPEN中中; DFS(newNode); 从从OPEN表中移除头结点表中移除头结点node, 并取头结点并取头结点NewNode; DFS

5、(NewNode); 深度优先搜索深度优先搜索DFSDFS 对于当前顶点对于当前顶点u u，如果如果u u还有以此为起点而未搜还有以此为起点而未搜索到的边索到的边( (u u, ,v v) )，那么就沿边那么就沿边( (u u, ,v v) )继续搜索下继续搜索下去，即立即搜索顶点去，即立即搜索顶点v v。当当v v及及v v的所有儿子结的所有儿子结点都被搜索过后，接着搜索点都被搜索过后，接着搜索u u的其他儿子结点。的其他儿子结点。当结点当结点u u的所有边都已被探寻过，搜索将回溯的所有边都已被探寻过，搜索将回溯到结点到结点u u的父结点。这一过程一直进行到找到的父结点。这一过程一直进行到找

6、到从源结点从源结点s s可达的满足要求的结点或路径为止。可达的满足要求的结点或路径为止。递归回溯递归回溯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：从初始结点开始一层层扩展直到找到目标结从初始结点开始一层层扩展直到找到目标结点，它能较好地解决状态不是太多的情况。点，它能较好地解决状态不是太多的情况。 双向广度优先算法：可用于操作可逆的广度优先搜双向广度优先算法：可用于操作可逆的广度优先搜索问题。在寻找目标结点或路径的搜索过程中，初索问题。在

8、寻找目标结点或路径的搜索过程中，初始结点向目标结点和目标结点向初始结点同时进行始结点向目标结点和目标结点向初始结点同时进行扩展，直至在两个扩展方向上出现同一个子结点，扩展，直至在两个扩展方向上出现同一个子结点，搜索结束，这就是双向搜索过程。搜索结束，这就是双向搜索过程。 双向搜索双向搜索过程过程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()初始工作初始工作 建立两组结点表建立两组结点表 OPEN_SOP

9、EN_S、CLOSED_SCLOSED_S与与OPEN_DOPEN_D、CLOSED_DCLOSED_D，分别存储两个方向上的生成结点和已分别存储两个方向上的生成结点和已扩展结点。扩展结点。 OPENOPEN型表具有型表具有“先进先出先进先出”的队列（链表）结构，的队列（链表）结构，称为称为“开表开表”，而，而CLOSEDCLOSED型表称为型表称为“闭表闭表”。 将起始结点放入将起始结点放入OPEN_SOPEN_S、CLOSED_SCLOSED_S表、目标结点表、目标结点放入放入OPEN_DOPEN_D、CLOSED_DCLOSED_D表；表； 检查起始结点与目标结点是否相同；若相同则找检查

10、起始结点与目标结点是否相同；若相同则找到解到解，完成，完成； 双向搜索双向搜索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所需的所需的最少步数是最少步数是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 跳马问题的广度优先搜索跳马问题的广度优先搜索分析分析建立一个队列建立一个队列Q Q，用于存放搜索到的位置，并考虑限界剪枝用于存放搜索到的位置，并考虑限界剪枝解空间是一个图，解空间是一个图，8 8叉树叉树求解方法求解方法S0S0：起始位置起始位置startstart第一个扩展第一个扩展S1S1：依次考虑从依次考虑从A

12、A 1 1步可达的方格，标记并存入队列步可达的方格，标记并存入队列Q Q。S2S2：从队列中取出一个结点从队列中取出一个结点B B，作处理标记，并标记所有从作处理标记，并标记所有从B B 1 1步可达的未被标记的方格步可达的未被标记的方格C C，步数是步数是B B的步数加的步数加1 1，存入，存入活结点队列活结点队列Q QS3S3：如果如果Q Q不空并且未到达目标方格不空并且未到达目标方格finishfinish，转转S2S2，否则结否则结束搜索束搜索图示图示23232323132323232333 二二维数组维数组grid1313:grid1313:表示棋盘阵列表示棋盘阵列 初始时，最外围的

13、初始时，最外围的2 2层被封锁层被封锁gridij=gridij= 0：该方格允许放棋子该方格允许放棋子gridij=gridij= 1：该方格被封锁，不允许放该方格被封锁，不允许放棋子棋子 方向标志为方向标志为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; 跳马问题的深度优先搜索跳马问题的深度优先搜索#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的连通分支数。 输入输入 有多个无向图数据。每个无向描述的第1行是两个整数n和e，分别表示顶点数和边数。接着有e行，每行有2个整数a、b，分别是一条边的两个端点（起点和终点）。两个图之间空一行。输出输出 对每个无向图，输出图中连通分支个数。 输入输出样例输入输出样例输入样例输入样例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;深度优先搜索子过程void dfs(int s)int i;marks=true;for(i=1;i=n;+i)if(graphsi & !marki)dfs(i);深度优先搜索全过程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、通讯团体、通讯团体 问题描述：问题描述： 有一家通讯公司近来要推出一项优惠活动，凡是在某个群体中有一家通讯公司近来要推出一项优惠活动，凡是在某个群体中相互通话的用户可以得到某种通话费折扣优惠。相互通话的用户可以得到某种通话费折扣优惠。A A、B B两个用户两个用户相互通话是指其中之一（如相互通话是指其中之一（如A A）与另一个人（如与另一个人（如B B）打过电话，打过电话，而不必要求而不必要求B B打电话给打电话给A A。 一个群体一个群体G G要满足通讯公司的优惠政策，它必须满足两个条件：要满足通讯公司的优惠政策，它必须

22、满足两个条件：（1 1）G G中任何两个用户通过话；中任何两个用户通过话；（2 2）G G是团体，即，如再加一个是团体，即，如再加一个G G外的人进去，所得新群体是不外的人进去，所得新群体是不满足条件（满足条件（1 1）的。）的。 任务：计算出这公司的所有用户构成的群体中最大团体的用户任务：计算出这公司的所有用户构成的群体中最大团体的用户数。最大团体是所有团体中用户数最多的团体，可能不止一个，数。最大团体是所有团体中用户数最多的团体，可能不止一个，但所有最大团体中用户数是一样的。但所有最大团体中用户数是一样的。输入：输入： 输入有若干组测试数据，每组测试数据的第一行上有输入有若干组测试数据，每

23、组测试数据的第一行上有一个整数一个整数n n，(1=n=50)(1=n=50)，是通讯公司的用户数。是通讯公司的用户数。接下来的接下来的n n行是这行是这n n个人的通讯状况，其第个人的通讯状况，其第i i行是行是0 0、1 1序列，长为序列，长为n n，序列之间无空格。该行第序列之间无空格。该行第j j个位置的个位置的数如为数如为1 1表示表示i i与与j j通过电话；如为通过电话；如为0 0则表示未通过话。则表示未通过话。相邻两组测试之间无空行。输入直到文件结束。相邻两组测试之间无空行。输入直到文件结束。输出：输出： 对输入中的每组测试数据，在输出文件中输出对应对输入中的每组测试数据，在输

24、出文件中输出对应的最大团体的用户数的最大团体的用户数m。对第对第i组测试数据，先在一组测试数据，先在一行上输出行上输出“Case i：”，接着输出接着输出m，见样例。见样例。 输入样例：输入样例：5 5 01011010111010110101010010100110001100011111011110输出样例：输出样例：Case 1: 3 分析分析 本题要确定最大团体人员数，基本的思想是从第本题要确定最大团体人员数，基本的思想是从第一个人开始考察他是否在最大团体中。如前面的一个人开始考察他是否在最大团体中。如前面的i-1人已被考察过，且前面的人已被考察过，且前面的i-1人中已有人中已有cnt

25、人构成人构成一个团，现考察第一个团，现考察第i人能否在该团中。继续这个工人能否在该团中。继续这个工作，直到所有人都被考察一遍。作，直到所有人都被考察一遍。 用深度优先回溯方法。用深度优先回溯方法。 # #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) / 到达叶结点到达叶结点 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 与当前团的连接与当前团的连接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、/输入团体中人员的关系信息输入团体中人员的关系信息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; /转换为邻接矩阵转换为邻接矩阵backtrack(0); /backtrack(0); /回溯法搜索回溯法搜索coutCase num: bestnendl;coutCase num: bestnendl; return 0;return 0; 3 3、缘份、缘份问题描述：问题描述：给出给出n

29、n个男女生之间的缘分值，按一定的个男女生之间的缘分值，按一定的规则对男女生配对，求所有配对男女生间的男女缘规则对男女生配对，求所有配对男女生间的男女缘分和的最大值。规则是：每一个男生只可选择一位分和的最大值。规则是：每一个男生只可选择一位女生，两个男生不可选择同一位女生。女生，两个男生不可选择同一位女生。输入：输入：输入有若干测试数据。每一组测试数据的第一输入有若干测试数据。每一组测试数据的第一行为一个整数行为一个整数n n，表示分别有表示分别有n n个男生与个男生与n n个女生；个女生；接下来的接下来的n n行中每行有行中每行有n n个整数，之间用空格隔开，个整数，之间用空格隔开，依次表示第

30、依次表示第i i个男生对第个男生对第1,2,1,2, ,n n个女生的缘分值个女生的缘分值t ti1i1，t ti2i2，, t, tinin。当输入的整数当输入的整数n n均为均为0 0时，表示时，表示输入结束。输入结束。输出：输出：对每组测试数据，输出一行，内容是该测试数对每组测试数据，输出一行，内容是该测试数据下男女生间的男女缘分和的最大值。据下男女生间的男女缘分和的最大值。输入样例：输入样例： 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分析分析用数组用数组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增加。假如还没有增加。假如还没有选完所有女生，那么继续进行选择；否则将当选完所有女生，那么继续进行选择；否则将当前的缘分值与目前最大的缘分值前的缘分值与目前最大的缘分值maximum比比较，看是否需要修正。较，看是否需要修正。假如第假如第j个女生的选择无法获得更大的缘分值，个女生的选择无法获得更大的缘分值，那么应该回退，此时将女生那么应该回退，此时将女生j标识不被选择；标识不被选择；且缘分值和扣除且缘分值和扣除#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、相异数字序列问题、相异数字序列问题 问题描述问题描述 给定整数给定整数m=2，长度为

34、长度为4的的0-1序列序列0011。假如把该序列头尾。假如把该序列头尾相接，构成环状，如图（相接，构成环状，如图（a）所示。如果沿着该环的某个位所示。如果沿着该环的某个位置，如顶上开始，以顺（逆）时针方向，取置，如顶上开始，以顺（逆）时针方向，取m个元素，可得个元素，可得00，再变动一个位置，又可得，再变动一个位置，又可得01，用同样方法可得，用同样方法可得11，10。有有4 4 个长度为个长度为2的的0- -1序列序列00，01，11，10，表示不同的十进，表示不同的十进制数制数0，1，3，2。 对于整数对于整数m=3，长度为长度为8的的0-1序列序列00010111头尾相接构成环头尾相接构成环状后如图（状后如图（b）所示。取到所示。取到8个长度为个长度为m=3的的0- -1序列序列 000、001、010、101、011、111、110、100 它们代表了不相同的十进制数它们代表了不相同的十进制数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 你的任务是，给你一个整数你的任务是，给你一个整数m，找出这样一个找出这样一个长为长为2m的的0- -1序列，使得依次取长为序列，使得依次取