搜索算法分析 (题解)

tzr789 贡献于2014-07-26

作者 lenovo  创建于2014-05-16 07:00:00   修改者lenovo  修改于2014-05-16 09:05:00字数10959

文档摘要:摘要本文主要针对搜索算法,对一些典型题目进行分析。简介搜索是图论算法中的核心,掌握搜索算法是进行各种图算法的前提。首先我们要考虑的是三个问题(1)算法的完全性:提出一个问题,该问题存在答案,该算法能够保证找到相应的答案。算法的完全性强是算法性能优秀的指标之一。
关键词:

搜索算法分析(题解) 摘要 本文主要针对搜索算法,对一些典型题目进行分析。 简介 搜索是图论算法中的核心,掌握搜索算法是进行各种图算法的前提。 首先我们要考虑的是三个问题(1)算法的完全性:提出一个问题,该问题存在答案,该算法能够保证找到相应的答案。算法的完全性强是算法性能优秀的指标之一。 (2)算法的时间复杂性: 提出一个问题,该算法需要多长时间可以找到相应的答案。算法速度的快慢是算法优劣的重要体现。 (3)算法的空间复杂性:算法在执行搜索问题答案的同时,需要多少存储空间。算法占用资源越少,算法的性能越好。 对于搜索,常用的算法是BFS与DFS 1、广度优先算法 广度优先算法(Breadth-First-Search),又称作宽度优先搜索,或横向优先搜索,是最简便的图的搜索算法之一,这一算法也是很多重要的图的算法的原型,Dijkstra单源最短路径算法和Prim最小生成树算法都采用了和宽度优先搜索类似的思想。广度优先算法其别名又叫BFS,属于一种盲目搜寻法,目的是系统地展开并检查图中的所有节点,以找寻结果。换句话说,它并不考虑结果的可能位址,彻底地搜索整张图,直到找到结果为止。BFS并不使用经验法则算法。 完全性:广度优先搜索算法具有完全性。这意指无论图形的种类如何,只要目标存在,则BFS一定会找到。然而,若目标不存在,且图为无限大,则BFS将不收敛(不会结束)。 时间复杂度:最差情形下,BFS必须寻找所有到可能节点的所有路径,因此其时间复杂度为,其中|V|是节点的数目,而 |E| 是图中边的数目。 空间复杂度:因为所有节点都必须被储存,因此BFS的空间复杂度为,其中|V|是节点的数目,而|E|是图中边的数目。另一种说法称BFS的空间复杂度为O(B),其中B是最大分支系数,而M是树的最长路径长度。由于对空间的大量需求,因此BFS并不适合解非常大的问题。[4-5] 2、深度优先算法 深度优先搜索算法(Depth First Search)英文缩写为DFS,属于一种回溯算法,正如算法名称那样,深度优先搜索所遵循的搜索策略是尽可能“深”地搜索图。[6]其过程简要来说是沿着顶点的邻点一直搜索下去,直到当前被搜索的顶点不再有未被访问的邻点为止,此时,从当前辈搜索的顶点原路返回到在它之前被搜索的访问的顶点,并以此顶点作为当前被搜索顶点。继续这样的过程,直至不能执行为止。 作为搜索算法的一种,DFS对于寻找一个解的NP(包括NPC)问题作用很大。但是,搜索算法毕竟是时间复杂度是O(n!)的阶乘级算法,它的效率比较低,在数据规模变大时,这种算法就显得力不从心了。[8]关于深度优先搜索的效率问题,有多种解决方法。最具有通用性的是剪枝,也就是去除没有用的搜索分支。有可行性剪枝和最优性剪枝两种。(摘自百度) 题目相关分析 在解题时,对图的表示常常是邻接矩阵,当我们采用邻接矩阵表示图时我们来分析下采用邻接矩阵时dfs与bfs的时间复杂度。(空间复杂度基本不需要考虑) 我们去图(a)为研究对象进行dfs搜索 由于在邻接矩阵中只是间接的存储了边的信息。在对某个顶点进行DFS 搜索时,要检查其他每个顶点,包括它的邻接顶点和非邻接顶点,所需时间为O(n)。例如 在图2.4(b)中,执行DFS(A)时,要在邻接矩阵中的第0 行检查顶点A~I 与顶点A 是否相邻且是否已经访问过。另外,整个DFS 过程,对每个顶点都要递归进行DFS 搜索,因此遍历图中所有的顶点所需的时间为O(n2)。 同样,我们再以图(a)为研究对象进行bfs搜索 由于在邻接矩阵中只是间接地存储了边的信息,所以对从队列头取出来的每个顶点k,要循环检测无向图中的其他每个顶点j(不管是否与顶点k 相邻),判断j 是否跟k 相邻且是否访问过;另外,每个顶点都要入队列,都要从队列头取出,进行判断,所以总的时间代价为O(n2)。 那么究竟何时选择dfs,还是bfs呢? 选择dfs! 深度优先搜索算法的思路很简单,因此很好理解,但它求得的解不是最优的;并且一旦某个分支可以无限地搜索下去(假定结点有无穷多个),但沿着这个分支搜索找不到解,则算法将不会停止、也找不到解。 故一个有限节点的图,规模比较小,且并不需要找最优解而是去找一个可行解时,我们可以选择dfs搜索思路。 选择bfs! 如果某个问题有解,则采用广度优先搜索必能找到解,且找到的解的步数是最少的,解是最优的,当我们所求的解是最优解而不是可行解时,我们可以选择bfs来进行求解,只要对节点进行维护,我们就能得到最优解。 简单题目分析 1、 显式图的求解问题 分析:显示图求解问题属于搜索中最基本的问题,我们并不需要对题目要求进行抽象,而是直接采用搜索策略满足题目中的要求从而最终得出程序。 题目1  解救小Q 小Q被邪恶的大魔王困在了迷宫里,love8909决定去解救她。 迷宫里面有一些陷阱,一旦走到陷阱里,就会被困身亡:(,迷宫 里还有一些古老的传送阵,一旦走到传送阵上,会强制被传送到 传送阵的另一头。 现在请你帮助love8909算一算,他至少需要走多少步才能解 救到小Q? Input 第一行为一个整数T,表示测试数据组数。 每组测试数据第一行为两个整数N,M,(1≤N,M≤50)表示 迷宫的长和宽。 接下来有N行,每行M个字符,是迷宫的具体描述。 · .表示安全的位置 · #表示陷阱, · Q表示小Q的位置 · L表示love8909所在位置, 数据保证love8909只有一个,数据也保证小Q只有一个。 小写字母a-z表示分别表示不同的传送阵,数据保证传送阵 两两配对。 Output 每组数据输出一行,解救小Q所需的最少步数,如果无论如何都 无法救小Q,输出-1。 题解 这是一道搜索水题,我们先看题目规模,N,M<50,而且我们所求的解是解救小q的步数,为最优解,选择bfs搜索策略完全符合要求,于是直接用bfs水过该题。 源程序 #include #include #define MAXN 100 #define INF 100000000 using namespace std; struct point { int x,y; int step; char chara; }; queueQ; int dir[4][2]={{-1,0},{0,1},{1,0},{0,-1}}; int N,M; int ax,ay,bx,by; struct point b; char map[MAXN][MAXN]; int minstep[MAXN][MAXN]={INF}; int bfs(point s) {Q.push(s); point hd; while(!Q.empty()) { //printf("dui%d %d\n",Q.front().x,Q.front().y); hd=Q.front();Q.pop(); for(int i=0;i<4;i++) { int x=hd.x+dir[i][0];int y=hd.y+dir[i][1]; //printf("%d %d\n",x,y); if(x>=0&&x<=N-1&&y>=0&&y<=M-1&&map[x][y]!='#'&&map[x][y]!='b'&&map[x][y]!='a'&&map[x][y]!='c'&&map[x][y]!='d'&&map[x][y]!='e'&&map[x][y]!='f'&&map[x][y]!='g'&&map[x][y]!='h'&&map[x][y]!='i'&&map[x][y]!='j'&&map[x][y]!='k'&&map[x][y]!='l'&&map[x][y]!='m'&&map[x][y]!='n'&&map[x][y]!='o'&&map[x][y]!='p'&&map[x][y]!='q'&&map[x][y]!='r'&&map[x][y]!='s'&&map[x][y]!='t'&&map[x][y]!='u'&&map[x][y]!='v'&&map[x][y]!='w'&&map[x][y]!='x'&&map[x][y]!='y'&&map[x][y]!='z') { //printf("ha\n"); point t; t.x=x;t.y=y; //printf("%d %d\n",t.x,t.y); t.step=hd.step+1; //printf("%d\n",t.step); // printf("%d\n",minstep[t.x][t.y]); if(t.step=0&&x<=N-1&&y>=0&&y<=M-1&&map[x][y]!='.'&&map[x][y]!='#'&&map[x][y]!='Q'&&map[x][y]!='1') { char c; c=map[x][y]; int x1;int y1; for(int i=0;i char grid[101][101]; int m, n; int dir[8][2] = { {-1,-1}, {-1,0}, {-1,1}, {0,1}, {1,1}, {1,0}, {1,-1}, {0,-1} }; void DFS( int x, int y ) //从(x,y) { int i, xx, yy; grid[x][y] = '*'; //将grid[x][y] for( i=0; i<8; i++ ) { xx = x + dir[i][0]; yy = y + dir[i][1]; if( xx<0 || yy<0 || xx>=m || yy>=n ) continue; if( grid[xx][yy] == '@' ) DFS(xx, yy); } } int main( ) { int i, j; int count; while( 1 ) { scanf( "%d%d", &m, &n ); if( m==0 ) break; for( i=0; i10^9复杂度爆了!!!于是再看题,由于总水量不变,我们可以发现状态最终只有(b+1)* (c+1)为6*10^6,直接用bfs水过。 #include #include #include using namespace std; int val[3],goal,s,flag; int vis[205][205],front,rear; class Node { public: int v[3],dist; }node[1005]; void bfs() { front=0,rear=1; node[0].v[2]=val[2]; vis[0][0]=1; while(front>s; while(s--) { cin>>val[0]>>val[1]>>val[2]>>goal; memset(vis,0,sizeof(vis)); memset(node,0,sizeof(node)); bfs(); int i,j; if(flag) { cout<=0;i--) { for(j=0;j<=rear;j++) { if(node[j].v[0]==i||node[j].v[1]==i||node[j].v[2]==i) { flag=1; break; } } if(flag) break; } cout< using namespace std; bool bl[10000]; int n,a[10000]; int search(int k) { int Max=0; if(k==n) return 0; Max=max(search(k+1),Max); if(bl[k-1]==false) { bl[k]=true; Max=max(search(k+1)+a[k],Max); bl[k]=false; } return Max; } int main() { int i,Max=0; cin>>n; for(i=0;i>a[i]; Max=max(search(1),Max); bl[0]=true; Max=max(search(1)+a[0],Max); cout< using namespace std; int n,a[10000],f[10000][2]; int search(int k,bool left) { if(f[k][left]!=-1)return f[k][left]; int Max=0; if(k==n) return f[k][left]=0; Max=max(search(k+1,false),Max); if(left==false) { Max=max(search(k+1,true)+a[k],Max); } return f[k][left]=Max; } int main() { int i,Max=0; for(i=0;i<10000;i++) f[i][0]=f[i][1]=-1; cin>>n; for(i=0;i>a[i]; Max=max(search(1,0),Max); Max=max(search(1,1)+a[0],Max); cout<

下载文档到电脑,查找使用更方便

文档的实际排版效果,会与网站的显示效果略有不同!!

需要 8 金币 [ 分享文档获得金币 ] 0 人已下载

下载文档