搜索算法-主要培训.ppt

深度优先搜索全过程 void search(){ int res=0,i; for(i=0;iMAXN;++i) mark[i]=false; for(i=1;i=n;++i){ if(!mark[i]){ ++res; dfs(i); } } coutresendl; } 主程序 int main(){ while(cinne) { input(); search(); } return 0; } 2、通讯团体 问题描述： 有一家通讯公司近来要推出一项优惠活动，凡是在某个群体中相互通话的用户可以得到某种通话费折扣优惠。A、B两个用户相互通话是指其中之一（如A）与另一个人（如B）打过电话，而不必要求B打电话给A。 一个群体G要满足通讯公司的优惠政策，它必须满足两个条件： （1）G中任何两个用户通过话； （2）G是团体，即，如再加一个G外的人进去，所得新群体是不满足条件（1）的。 任务：计算出这公司的所有用户构成的群体中最大团体的用户数。最大团体是所有团体中用户数最多的团体，可能不止一个，但所有最大团体中用户数是一样的。 输入： 输入有若干组测试数据，每组测试数据的第一行上有一个整数n，(1=n=50)，是通讯公司的用户数。接下来的n行是这n个人的通讯状况，其第i行是0、1序列，长为n，序列之间无空格。该行第j个位置的数如为1表示i与j通过电话；如为0则表示未通过话。相邻两组测试之间无空行。输入直到文件结束。 输出： 对输入中的每组测试数据，在输出文件中输出对应的最大团体的用户数m。对第i组测试数据，先在一行上输出“Case i：”，接着输出m，见样例。 输入样例： 5 01011 10101 01001 10001 11110 输出样例： Case 1: 3 分析 本题要确定最大团体人员数，基本的思想是从第一个人开始考察他是否在最大团体中。如前面的i-1人已被考察过，且前面的i-1人中已有cnt人构成一个团，现考察第i人能否在该团中。继续这个工作，直到所有人都被考察一遍。 用深度优先回溯方法。 #includeiostream using namespace std; const int MAXN=100; int x[MAXN],bestx[MAXN], n, a[MAXN][MAXN], bestn,cn; void backtrack(int i) { if (i n-1) { // 到达叶结点 for (int j = 0; j n; j++) bestx[j] = x[j]; bestn = cn; return; } // 检查顶点 i 与当前团的连接 int ok = 1; for (int j =0; j i; j++) if ((x[j] == 1) (!a[i][j]) ) { //考察： i与前面的j是否相连 ok = 0; break; } // i与前面的j不相连，舍弃i if (ok){ // 进入左子树 x[i] = 1; cn++; backtrack(i + 1); cn--; } if (cn + n - i bestn){ // 进入右子树 x[i] = 0; backtrack(i + 1); } return ; } ACM程序设计 （2013. 7.13 ~2013.7.31） 搜索算法 沈云付 主要的搜索方法 广度优先搜索 BFS 深度优先搜索 DFS 双向广度优先算法 A*算法 广度优先搜索算法BFS框架 记Q为队列或堆，s是为开始搜索的点 void branchBound (){ Node *Q=NULL; for(s的所有儿子节点w) if (w是活结点且符合要求) w入队列Q; else 舍去w; while (Q！=NULL){ 取Q的头元素t; 对t的所有儿子节点w{ if (w是叶结点) 计算值及判断是否当前最优； else { if (w是且符合要求) w入队列Q; else 舍去w； } } } BFS实现过程 void BFS(){ 初始化表开表OPEN、闭表CLOSED;将s放入OPEN； wh