搜索详解

- 日理万妓 2023-06-09 14:30 7阅读 0赞

## 搜索 ##

#### 一.dfs和bfs简介 ####

#### 深度优先遍历(dfs) ####

**本质：**

遍历每一个点。

**遍历流程：**

从起点开始，在其一条分支上一条路走到黑，走不通了就往回走，只要当前有分支就继续往下走，直到将所有的点遍历一遍。

**剪枝：**

如果已经确定这条路没有我们想要的答案，那么就不用继续在这条路上走下去了，于是我们就开始走其他的分支或者往回走，这样节省时间的方法称之为剪枝。

**回溯：**

当我们一条路走到头，往回走时，就叫做回溯。

**恢复现场：**

当我们回溯的时候，原来这个图是什么样的，我们还要变回什么样。这样做的**目的：** 当我们遍历完这条分支，去遍历下一条分支的时候，我们需要保证当前图其他条件的一致性，也就是遍历每一条分支的时候，当前图的状态都是一样的。保证遍历每一条分支的时候都是公平的。

#### 广度优先遍历(bfs) ####

**遍历流程：** 逐层逐层的遍历，先遍历第一层，再遍历第二层…，也就是遍历当前节点所能到达的所有子节点。直到遍历所有的点。不存在剪枝，回溯和恢复现场的操作。

#### 对比dfs和bfs ####

**时间复杂度：**

> dfs: 因为我们需要枚举每一个点，以及每一条边，所示它的时间复杂度为O(n + e) 即点的个数+边的个数
> 
> bfs:跟dfs时间复杂度一样，都为O(n + e) 不同的是对每个点的访问顺序是不一样的

**用到的数据结构**：

> dfs: stack
> 
> bfs: queue

**空间复杂度**：

> dfs: O(h) h为树的深度
> 
> bfs: O(2^h)

**特性**：

> dfs: 不具有最短性
> 
> bfs: 具有最短性

#### 二. 树与图的深度优先遍历(dfs) ####

**树与图的深度优先遍历**:  
树其实也是图的一种  
**图:** 分为有向图和无向图  
**图的储存:**

> 第一种：邻接矩阵，就是一个二维数组，缺点：当点和边特别多的时候，存不下，一般用的比较少，而且非常浪费空间  
> 第二种：邻接表:由n个单链表组成，也可以用vector动态数组来实现，但vector有很大的缺点，当点和边非常大时，用vector动态数组的方法很容易超时，所以我们常用n个但链表的方式来存储图

**邻接表如何存图呢：**  
假设有这样一个图:  
![在这里插入图片描述][format_png]  
那么我们可以给每个节点开一个单链表，如下图所示：  
![在这里插入图片描述][format_png 1]  
这样我们就把图用邻接表的方法存了下来  
树与图深度优先遍历的大致流程：一条路走到黑，直到撞到南墙，走不通了，然后往回走，只要有分支就继续往下走

**1.树与图的遍历模板：**

邻接表以h数组为表头，使用 e 和 ne 数组分别存储边的终点和下一个节点

#include<iostream>
    #include<cstring>
    using namespace std;
    const int N  = 1e6 + 10;
    int h[N], e[N], ne[N], idx, n;//这里跟单链表一样，只不过这里是N个头节点，H[N]
    bool vis[N];  //判断是否遍历过
    void add(int a, int b)  //邻接表存树与图
    {
        
        e[idx] = b, ne[idx] = h[a], h[a] = idx++;
    }
    void dfs(int cur)
    {
        
        vis[cur] = true;
        for(int i = h[cur]; i != -1; i = ne[i]){
          //遍历树
            int u = e[i];
            if(!vis[u]){
        
                dfs(u);
            }
        }
    }
    int main()
    {
        
        int a, b;
        cin >> n;
        //初始化
        memset(h, -1, sizeof h);
        memset(vis, false, sizeof vis);
        for(int i = 0; i < n; i++){
        
            cin >> a >> b;
            //建树，双向图
            add(a, b);
            add(b, a);
        }
        dfs(1);
        return 0;
    }

这样我们就遍历了每个点。

**2.树的dfs序**

一般来讲，我们在对树进行深度优先遍历时，对于每个节点，在刚进入递归以后以及即将回溯前各记录一次该点的编号,最后产生的长度为2N的节点序列被称为树的dfs序

void dfs(int x)
    {
        a[++m] = x;
        v[x] = 1;
        for(int i = h[x]; i != -1; i = ne[i]){
    		int y = e[i];
    		if(v[y])continue;
    		dfs(y);
    	}
    	a[++m] = x;
    }

**3.树的深度**

我们已知根节点的深度为0.若节点x的深度为d\[x\]，则它的子节点的深度为d\[y\] = d\[x\] + 1

void dfs(int x)
    {
    	v[x] = 1;
    	for(int i = h[x]; i != -1; i = ne[i]){
    		int y = e[i];
    		if(v[y])continue;
    		d[y] = d[x] + 1;
    		dfs(y);
    	}
    }

**4.连通图的划分**

假设从x点开始一次遍历，就会访问x能够到达的所有的点和边，因此，通过多次深度优先遍历，可以划分出一张无向图中的各个连通图。同理，对一个森林进行深度优先遍历，可以划分森林中每棵树

cnt表示无向图包含的连通块的个数, v数组标记了每一个点属于哪个连通块

void dfs(int x)
    {
        
    	v[x] = cnt;
        for(int i = h[x]; i != -1; i = ne[i]){
        
            int y = e[i];
            if(v[y])continue;
            dfs(y);
        }
    }
    for(int i = 1; i <= n; i++){
        
        if(!v[i]){
        
    		cnt++;
            dfs(i);
        }
    }

#### 三.树与图的广度优先遍历 ####

树与图的广度优先遍历需要使用一个队列来实现。起初，队列中仅包含一个起点。在广度优先遍历过程中，我们不断从队头取出一个节点x，对于x面对的多条分支，将所有x能够达到的下一个节点插入队尾，重复执行上述过程直到队列为空

**1.广度优先遍历模板**

void dfs()
    {
        
        memset(d, 0, sizeof d);
        queue<int> q;
        q.push(1);
        d[1] = 1;  //d数组表示节点的深度
        while(q.size()){
            //只要队列不为空
    		int x = q.front();  //取出队头
            q.pop();
            for(int i = h[x]; i != -1; i = ne[i]){
          //遍历x能够到达的所有下一个节点
    			int y = e[i];
                if(d[y])continue;  
                d[y] = d[x] + 1;    //深度+1
                q.push(y);
            }
        }
    }

在上面的代码中，d数组表示从起点 1 走到点 x 需要经过的最少点数. 广度优先遍历是一种按照层次顺序进行访问的方法, 它具有如下俩个重要的性质：  
**1.在访问完所有的第 i 层节点后，才会开始访问第 i + 1 层节点**

**2.广度优先遍历队列中的元素关于层次满足俩段性和单调性**, 即队列中至多包含俩个层次的节点, 其中一部分属于第 i 层, 一部分属于 i + 1 层,并且所有的第 i 层节点都排在第 i + 1 层节点之前

**2.拓扑排序**

给定你一个无向图，若一个由图中所有点构成的序列A满足：对于图中的每条边 (x, y)，x 在A中都出现在y之前,则称A是该有向图的一个拓扑排序

**入度：** 在有向图中，以节点 x 为终点的有向边的条数被称为 x 的入度

**出度：** 在有向图中，以节点 x 为起点的有向边的条数被称为 x 的出度

拓扑排序非常简单,我们只需要不断选择图中入度为0的节点 x , 然后把 x 连向的点的入度减1,我们可以结合广度优先遍历的框架来实现:

1.建立空的拓扑排序A。

2.预处理出所有点的入度deg\[i\]，起初把所有入度为0的点入队

3.取出队头节点x，把x加入拓扑序列A的末尾

4.对于x出发的每条边(x, y)把 deg\[y\] 减 1 。若被减为0, 则把y入队

5.重复3~4过程，直到队列为空，我们便求出了拓扑序列A

void add(int x, int y)  //建边
    {
        
        e[cnt] = y, ne[cnt] = h[x], h[x] = cnt++;
    }
    void topsort()
    {
        
        queue<int> q;
        for(int i = 1; i <= n; i++)
            if(deg[i] == 0)q.push(i);  //将入度为0的点加入到队列中
        while(q.size()){
        
            int x = q.front();
            q.pop();
            a[++t] = x;  //将x加入到拓扑序中
            for(int i = h[x]; i != -1; i = ne[i]){
        
                int y = e[i];
                deg[y]--;  //入度--
                if(deg[y] == 0)q.push(y);//如果入度为0，添加到队列中去
            }
        }
    }
    int main()
    {
        
        cin >> n >> m;
        for(int i = 1; i <= m; i++){
        
    		int x, y;
            cin >> x >> y;
            add(x, y);
        }
        topsort();
        for(int i = 1; i <= n; i++)//输出拓扑序
            printf("%d ", a[i]);
       	cout << endl;
    }

#### 四.迭代加深 ####

深度优先搜索每次选定一个分支，不断深入，直至到达递归边界才回溯。这种策略带有一定的缺陷。如果搜索树每个节点的分枝数非常多, 而答案在某个较浅的节点上。如果深搜在一开始选错了分支，就很可能在不包含答案的深层子树上浪费太多的时间

此时，我们可以从小到大限制搜索的深度如果在当前深度限制下找不到答案，就把深度限制增加，重新进行一次搜索，这就是**迭代加深**的思想。

**例题：加成序列(poj2248)**

满足如下条件的序列X（序列中元素被标号为1、2、3…m）被称为“加成序列”：

1、X\[1\]=1

2、X\[m\]=n

3、X\[1\]<X\[2\]<…<X\[m-1\]<X\[m\]

4、对于每个 k（2 ≤ k ≤ m）都存在两个整数 i 和 j （1 ≤ i,j ≤ k−1，i 和 j 可相等），使得 X\[k\]=X\[i\]+X\[j\]。

你的任务是：给定一个整数n，找出符合上述条件的长度m最小的“加成序列”。

如果有多个满足要求的答案，只需要找出任意一个可行解。

搜索框架：依次搜索序列中的每个位置k， 枚举 i 和 j 作为分支，把 X\[i\] 和 X\[j\] 的和填到 X\[k\] 上，然后递归填写下一个位置。

加入以下剪枝：

1.优化搜索顺序：为了让序列中的数尽快逼近n，在枚举 i 和 j 时从大到小枚举

2.排除等效冗余

对于不同的 i 和 j ，X\[i\] 和 X\[j\] 可能是相等的，我们可以在枚举是用一个 bool 类型的数组对 X\[i\] 和 X\[j\] 进行判重,避免重复搜索同一个和

3.我们可以采用迭代加深的方法进行搜索, 从1开始限制搜索深度，若搜索失败就增加深度限制重新搜索,直到找到一组解时即可输出答案

#include<iostream>
    #include<cstring>
    using namespace std;
    
    const int N = 110;
    int a[N];
    bool vis[N];
    int n, k;
    bool dfs(int u, int k)
    {
        
        //如果达到搜索限制，判断a[u - 1]是否等于n
        if(u == k)return a[u - 1] == n;
        //遍历前边的元素
        for(int i = u - 1; i >= 0; i--){
        
            for(int j = i; j >= 0; j--){
        
                int s = a[i] + a[j];
                //如果和已经出现过，或者不满足要求，剪枝掉
                if(vis[s] || s > n || s <= a[u - 1])continue;
                a[u] = s;
                if(dfs(u + 1, k))return true;
                
            }
        }
        return false;
    }
    int main()
    {
        
        a[0] = 1;
        while(cin >> n && n){
        
            int k = 1;
            while(!dfs(1, k)){
         //不断增加搜索限制k直到得到正确的答案
                memset(vis, false, sizeof vis);
                k++;
            }
            for(int i = 0; i < k; i++)cout << a[i] << ' ';
            cout << endl;
        }
        return 0;
    }

[format_png]: /images/20230531/f8cd70d74b174080b82925c27353793d.png
[format_png 1]: /images/20230531/90a356d3971b44cea392ec4c8ba3574e.png