搜索专题

迷南。 2021-09-21 03:02 342阅读 0赞

> ### 搜索 ###
> 
>  *   *  深度优先搜索
>      *   *   *  最优解的问题
>              *  树的遍历
>              *  图的遍历
>      *  广度优先搜索
>      *   *   *  迷宫问题
>              *  树的遍历
>              *  图的遍历

在算法中搜索是一个很常见的操作，比如在树的遍历，图的遍历中，都会用到搜索。在程序设计中一般有两种搜索方式：深度优先搜索和广度优先搜索。深度优先搜索是以"深度"来度量，一般通过递归来实现。而广度优先搜索则是通过"广度"来类比，通过队列来实现。  
无论是深度优先搜索还是广度优先搜索，都是可以通过迷宫问题来形象化。这里就不在多写，下面主要总结一下深搜和广搜的常见解题方法和代码。

## 深度优先搜索 ##

深度优先搜索是以“深度”作为第一关键词,当碰到岔路口时，总是选择其中的一条岔路口前进，直到碰到死胡同才回退到最近的岔路口选择另一条道路。

#### 最优解的问题 ####

深度优先搜索可以解决一类问题就是：给定了一个序列，要求选择若干个元素，使得这若干个元素满足某种"最优方案"。这种问题的本质就是枚举出所有情况，筛选出“最优的答案”。因此，深度优先搜索是一种“遍历完所有情况的操作”（当然，在满足某种具体条件的时候可以进行“剪支”操作）。深度优先搜索是栈的应用，在实现过程会调用系统栈来实现。下面是一个例题 For Example:

> 有n件物品，每件物品的重量为w\[i\],价值为c\[i\]。现在需要选择若干件物品放入一个容量为V的背包中，使得在选入背包的物品和重量不超过V的前提下，让背包的价值最大，求最大的价值（1<=n<=20）

这是一个"背包问题"，可以用动态规划的方法来求解。这里用“深度优先搜索”来试一下。  
思路：从第一个物品开始枚举，每种物品都有选择和不选择两种方案，在满足物品重量不超过V的情况下，得到每种方案的价值之和，然后比较每种方案，选择出价值最大的。因此，对于函数DFS（），需要的参数有：index（用来标识物品），sumW(用来记录选择了的物品质量和)，sumC(用来记录选择了的物品的价值和)

#include<cstdio>
    const int maxn = 24;
    int n,V,ans=0;//分别代表物品数,背包容量,最大价值
    int w[maxn],c[maxn];//用于记录每件物品的重量和价值 
    
    void DFS(int index,int sumW, int sumC){  
    	if(index == n){ //当枚举到了最后一件物品的时候,结束选择（边界）
    		return; 
    	}
    	//不选择第index件物品
    	DFS(index+1,sumW,sumC);
    	//只有加入第index件物品后未超过容量V,才能继续 
    	if( sumW + w[index] <= V){ 
    		if(sumC+c[index] > ans){ 
    			ans = sumC + c[index]; 	
    		}
    		DFS(index+1,sumW+w[index],sumC+c[index]);
    	}
    }
    
    int main(){ 
    	scanf("%d%d",&n,&V);
    	for(int i=0; i<n; i++){ 
    		scanf("%d",&w[i]);
    	}
    	for(int i=0; i<n; i++){ 
    		scanf("%d",&c[i]);
    	}
    	DFS(0,0,0); //初始第0件物品，重量和价值都为0
    	printf("%d\n",ans);
    	return 0;	
    }

输入数据

> 5 8  
> 3 5 1 2 2  
> 4 5 2 1 3

输出数据

> 10

#### 树的遍历 ####

常见的树的遍历方法有：先序，中序，后序和层序遍历。其中对于先序，中序，后序，都可以用递归来实现（深度优先搜索体现的思想也是递归）

//先序
    void preorder(node* root){ 
    	if(root == NULL) return ; //递归边界
    	printf("%d ",root->data);
    	preorder(root->lchild);
    	preorder(root->rchild);
    }
    
    //中序
    void inorder(node* root){ 
    	if(root==NULL)return;
    	inorder(root->lchild);
    	printf("%d ",root->data);
    	inorder(root->rchild);
    }
    
    //后序
    void postorder(node* root){ 
    	if(root==NULL)return;
    	postorder(root->lchild);
    	postorder(root->rchild);
    	printf("%d ",root->data);
    }

#### 图的遍历 ####

对于图的遍历，用DFS的思想就是每次都是沿着路径到不能再前进时才返回到最近的岔道口。要遍历整个图，就需要对所有的连通块进行遍历，基本思想就是将已经过的顶点设置已访问，下次递归的时候就不需要再次访问，一直到整个图的顶点都被标记。

const int MAXV = 100;//顶点数 
    const int INF = 100000000; //表示不可达 
    bool vis[MAXV] = { false}; //初始化未访问 
    G[MAXV][MAXV];
    
    //遍历一个连通块 
    void DFS(int u,int depth){ //u为当前访问顶点的编号,depth为深度 
    	vis[u] = true; //标记为已访问
    	for(int v=0; v<n; v++){ 
    		if(vis[v] == false && G[u][v] != INF){ 
    			DFS(v,depth +1);
    		}
    	} 
    }
    
    void DFSTrave(){ //遍历图
    	for(int u=0; u<n; u++){ 
    		if(vis[u] == false){ 
    			DFS(u,1); //访问u所在的连通块,1表示是第一层 
    		}
    	} 
    	
    }

## 广度优先搜索 ##

广度优先搜索是以广度作为第一关键词，当碰到岔道口时，总是先访问从该岔道口能直接到达的所有结点。

#### 迷宫问题 ####

> 给出一个`m*n`的矩阵，矩阵中的元素为0或1。称位置(x,y)与其上下左右四个位置(x,y+1),(x,y-1),(x-1,y),(x+1,y)是相邻的。若矩阵中若干的1是相邻的(不必两两相邻)，那么称这些1构成了一个“块”，求给定矩阵中"块"的个数。例:  
> 0 1 1 1 0 0 1  
> 0 0 1 0 0 0 0  
> 0 0 0 0 1 0 0  
> 0 0 0 1 1 1 0  
> 1 1 1 0 1 0 0  
> 1 1 1 1 0 0 0  
> 上面的`6*7`矩阵中“块”数为4.

思路：通过遍历每个二维数组中的每个元素，当该元素为1并且还没有访问的时候，将它放到队列中。并且把该元素上下左右为1且不越界的元素找到也放入队列，最后统计循化的次数就是“块数”。其中某元素的上下左右可以用两个数组来表示：

int X[] = {0,0,-1,1};
    int Y[] = {1,-1,0,0};
    for(int i=0; i<4; i++){
    	newX = x + X[i];
    	newY = y + Y[i];
    }

#include<cstdio>
    #include<queue>
    using namespace std;
    const int MAXV = 100;//顶点数 
    int matrix[MAXV][MAXV];//存储图
    int m,n;//矩阵的行数和列数
    bool inqu[MAXV][MAXV] ={ false};
    int X[] = { 0,0,-1,1};
    int Y[] = { 1,-1,0,0}; 
    struct node{ 
    	int x,y;
    }Node;
    
    
    bool judge(int x,int y){  //判断该点是否满足条件 
    	if(x<0||x>=m||y<0||y>=n)return false;
    	if(inqu[x][y]==true||matrix[x][y]==0) return false;
    	return true; 
    }
    
    void BFS(int x,int y){ 
    	Node.x = x;
    	Node.y = y;
    	queue<node>q;
    	q.push(Node);
    	inqu[x][y]=true;
    	while(!q.empty()){ 
    		node top = q.front();
    		q.pop();
    		for(int i=0;i<4; i++){ 
    			int newX = top.x + X[i];
    			int newY = top.y + Y[i];
    			if(judge(newX,newY)==true){ 
    				Node.x = newX;
    				Node.y = newY;
    				q.push(Node);
    				inqu[newX][newY] = true;
    			}
    		}
    	}
    }
    
    int main(){ 
    	scanf("%d%d",&m,&n);
    	for(int i=0;i<m; i++){ 
    		for(int j=0; j<n; j++){ 
    			scanf("%d",&matrix[i][j]);
    		}
    	}
    	int count = 0;
    	for(int i=0; i<m; i++){ 
    		for(int j=0; j<n; j++){ 
    			if(inqu[i][j]==false && matrix[i][j]==1 ){ 
    				BFS(i,j);
    				count++;
    			}
    		}
    	}
    	printf("%d",count);
    	return 0;
    }

#### 树的遍历 ####

这里体现在树的层序遍历，比如下面这棵二叉树：  
![二叉树][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ljemZ5NTg1_size_16_color_FFFFFF_t_70]  
层序遍历的结果就是 0>1>2>3>4>5>6>7>8>9  
用代码来实现一下：

void BFS(node* root){ 
    	if(root == NULL) return;
    	queue<node*>Q; //队列中存放的是节点的地址
    	Q.push(root);//将根节点加入到队列中
    	while(!Q.empty()){ 
    		node* now = Q.front();
    		Q.pop();
    		printf("%d ",now->data);
    		if(now->lchild != NULL) Q.push(now->lchild);
    		if(now->rchild != NULL) Q.push(now->rchild);
    	} 
    }

#### 图的遍历 ####

BFS遍历图通过队列来实现

const int MAXV = 100;//顶点数 
    const int INF = 100000000; //表示不可达 
    bool vis[MAXV] = { false}; //初始化未访问 
    G[MAXV][MAXV];
    
    void BFS(int index){ 
    	queue<int>q;
    	q.push(Node);
    	vis[index] = true;
    	while(!q.empty()){ 
    		int u = q.front();
    		q.pop();
    		for(int v=0; v<n; v++){ 
    			if(vis[v]==false && G[u][v] !=INF){ 
    				vis[v]=true;
    				q.push(v);
    			}
    		}
    	}
    }
    void BFSTravel(){ 
    	for(int v=0; v<n; v++){ 
    		if(vis[v]==false){ 
    			BFS(v);
    		}
    	}
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ljemZ5NTg1_size_16_color_FFFFFF_t_70]: /images/20210920/41dd2776902844da8ca48fe561256301.png