深度优先搜索

深度优先搜索属于图算法的一种，英文缩写为DFS即Depth First Search.其过程简要来说是对每一个可能的分支路径深入到不能再深入为止，而且每个节点只能访问一次.

深度优先遍历的策略是：
从一个顶点v出发，首先将v标记为已遍历的顶点，然后选择一个邻接于v的尚未遍历的顶点u，如果u不存在，本次搜素终止。如果u存在，那么从u又开始一次DFS。如此循环直到不存在这样的顶点。
比如图a中
1.从顶点0开始，将0标记为已遍历，然后选择未被遍历的邻接0的顶点1。
2.标记顶点1，然后选择3并标记，然后选择顶点3邻接的顶点2。
3.顶点2标记后没有与它邻接的未标记的点，所以返回3选择另一个邻接3并且未被标记的顶点4。
4.顶点4没有更多的符合条件的点，因此搜索终止，返回到3，3没有更多的点，搜索终止返回到1，最后返回到0，搜索终止。
遍历的路径可以参考如下图红色标记的路径：

• DFS代码框架

  void dfs(需要的变量 {,int tmp_ans} ){ //tmp_ans用于记录答案,因为用了void类型

  if (搜索结束){
      ans=...  //传出答案
      return;
  }
  标记此节点已经遍历
  for (确定方向){
      if (该节点未遍历){
          bfs(遍历该节点)
          标记该节点未遍历  //回溯 其实可以写在末尾(Link~1),如果写在这里,就可能出现问题(详见例题代码)
      }
  }
  //标记此节点未遍历(Link~1)  //回溯

  }

• 例题

【问题描述】

给定一个N*M方格的迷宫，迷宫里有T处障碍，障碍处不可通过。给定起点坐标和
终点坐标，问: 每个方格最多经过1次，有多少种从起点坐标到终点坐标的方案。在迷宫
中移动有上下左右四种方式，每次只能移动一个方格。数据保证起点上没有障碍。

【数据规模】

1≤N,M≤5

【输入】

第一行N、M和T，N为行，M为列，T为障碍总数。第二行起点坐标SX,SY，终点
坐标FX,FY。接下来T行，每行为障碍点的坐标。

【输出】

给定起点坐标和终点坐标，问每个方格最多经过1次，从起点坐标到终点坐标的方
案总数。

输入样例#1：

2 2 1
1 1 2 2
1 2

输出样例#1：

1

代码

#include <bits/stdc++.h>
using namespace std;

int n,m,t,sx,sy,ex,ey,tx,ty,ans,a[10][10],
    wx[4]={0,0,1,-1},
    wy[4]={1,-1,0,0};

void dfs(int x,int y){
    if (x==ex&&y==ey){
        ans++;
        return;
    }else{
        a[x][y]=1;
        for (int i=0;i<4;++i){
            int tx=x+wx[i];
            int ty=y+wy[i];   //注意:这里必须加 int 否则会更改全局变量,导致回溯时参数出错  Link~1
            if (tx>=1&&tx<=n&&ty>=1&&ty<=m&&a[tx][ty]==0){
                dfs(tx,ty);
                a[tx][ty]=0;  //Link~1 因为上一行语句中递归后,tx,ty值已经改变,所以回溯会出错
            }
        }
    }
}

int main(){
    cin>>n>>m>>t;
    cin>>sx>>sy>>ex>>ey;
    for (int i=1;i<=t;++i){
        cin>>tx>>ty;
        a[tx][ty]=1;
    }
    dfs(sx,sy);
    cout<<ans<<endl;
    return 0;
}

• 其他
  DFS用于暴力枚举时(例如求最优方案01背包),搜索过程像一棵二叉树,每个父节点对应2个孩子节点(表示取或不取),深度为物品的数量
• 优化
  DFS执行的次数为(2^n),当n较大时很容易TLE

可以根据题意,采取剪枝(Eg:记忆化,预判性剪枝)等方式
例题:归档/Day7/3.cpp

广度优先搜索

宽度优先搜索算法（又称广度优先搜索）是最简便的图的搜索算法之一，这一算法也是很多重要的图的算法的原型。Dijkstra单源最短路径算法和Prim最小生成树算法都采用了和宽度优先搜索类似的思想。其别名又叫BFS，属于一种盲目搜寻法，目的是系统地展开并检查图中的所有节点，以找寻结果。换句话说，它并不考虑结果的可能位置，彻底地搜索整张图，直到找到结果为止。

有一个有向图如图a

广度优先搜索的策略是：
从起始点开始遍历其邻接的节点，由此向外不断扩散。
1.假设我们以顶点0为原点进行搜索，首先确定邻接0的顶点集合S0 = {1，2}。
2.然后确定顶点1的集合S1 = {3}，顶点2没有邻接点，所以集合为空。
3.然后确定3的邻接点集合S3，因为2已经被遍历过，所以不考虑，所以由顶点3知道的邻接点集合S3 = {4}。
4.然后再确定顶点4的邻接点集合,顶点4没有更多的邻接点了，此时也没有还未遍历的邻接点集合，搜索终止。
遍历的路径可以参考如下图红色标记的路径：

代码的实现思路：

void BFS(){
    输入起始点；
    初始化所有顶点标记为未遍历；
    初始化一个队列queue并将起始点放入队列；
    while（queue不为空）{
        从队列中删除一个顶点s并标记为已遍历； 
        将s邻接的所有还没遍历的点加入队列；
    }
}

• 例题

题目描述

给定一个整数N ( 范围为04999 )，然后给定M个不重复的数字(范围为09)，你的任务是，判断这M个数字（每个数字可以使用0到多次）能不能构成一个数是N的倍数，如果存在，输出最小的倍数，否则输出0。

输入

第一行输入N
第二行输入M
接下来M行，每行输入一个数字（范围0~9）

输出

如果存在，输出最小倍数；否则输出0

样例输入

22
3
7
0
1

样例输出

110

提示

110是22的倍数

其它样例：

2
1
1

输出：

0

【数据规模和约定】

0 <= N <= 4999 1 <= M <= 10

代码

#include <bits/stdc++.h>
using namespace std;

int b[2000000][2],mark[5005];
stack <int> st;
void print(int s){
    st.push(b[s][1]);
    if (b[s][2]!=0) print(b[s][2]);  //将之前的各位倒的压入栈中
}

int main(){
    int n,m,a[15],tq,ty,ts,cnt=1,tmp;
    bool flag=false;
    cin>>n>>m;
    for (int i=1;i<=m;++i){
        cin>>a[i];
    }
    queue <int> q;
    queue <int> y;
    queue <int> s;
    sort(a+1,a+m+1);
    for (int i=1;i<=m;++i){
        if (a[i]==0) continue;  //自然数首位不为0
        q.push(a[i]);
        y.push(a[i]%n);
        s.push(cnt);
        mark[a[i]%n]=1;
        b[cnt][1]=a[i];
        b[cnt][2]=0;
        cnt++;
    }
    while (!q.empty()){
        tq=q.front();
        ty=y.front();
        ts=s.front();
        q.pop();
        y.pop();
        s.pop();
        if (ty==0){
            print(ts);
            while (!st.empty()){
                cout<<st.top();  //倒序输出
                st.pop();
            }
            cout<<endl;
            flag=true;
            break;
        }
        for (int i=1;i<=m;++i){
            tmp=(ty*10+a[i])%n;
            if (mark[tmp]==0){
                q.push(a[i]);
                y.push(tmp);
                s.push(cnt);
                mark[tmp]=1;
                b[cnt][1]=a[i];
                b[cnt][2]=ts;
                cnt++;
            }
        }
    }
    if (!flag) cout<<0<<endl;
    return 0;
}

搜索的剪枝

一：剪枝策略的寻找的方法

1）微观方法：从问题本身出发，发现剪枝条件

2）宏观方法：从整体出发，发现剪枝条件。

3）注意提高效率，这是关键，最重要的。

总之，剪枝策略，属于算法优化范畴；通常应用在 DFS 和 BFS 搜索算法中；剪枝策略就是寻找过滤条件，提前减少不必要的搜索路径。

二：剪枝算法 (算法优化)

1、简介

**在搜索算法中优化中，剪枝，就是通过某种判断，避免一些不必要的遍历过程**，形象的说，就是剪去了搜索树中的某些 “枝条”，故称剪枝。**应用剪枝优化的核心问题是设计剪枝判断方法，即确定哪些枝条应当舍弃，哪些枝条应当保留的方法。**

2、剪枝优化三原则: 正确、准确、高效原则

 搜索算法, 绝大部分需要用到剪枝. 然而, 不是所有的枝条都可以剪掉, 这就需要通过设计出合理的判断方法, 以决定某一分支的取舍. 在设计判断方法的时候, 需要遵循一定的原则.

剪枝的原则

1） 正确性

正如上文所述, 枝条不是爱剪就能剪的. 如果随便剪枝, 把带有最优解的那一分支也剪掉了的话, 剪枝也就失去了意义. 所以, 剪枝的前提是一定要保证不丢失正确的结果.

2）准确性

在保证了正确性的基础上, 我们应该根据具体问题具体分析, 采用合适的判断手段, 使不包含最优解的枝条尽可能多的被剪去, 以达到程序 “最优化” 的目的. 可以说, 剪枝的准确性, 是衡量一个优化算法好坏的标准.

3）高效性

设计优化程序的根本目的, 是要减少搜索的次数, 使程序运行的时间减少. 但为了使搜索次数尽可能的减少, 我们又必须花工夫设计出一个准确性较高的优化算法, 而当算法的准确性升高, 其判断的次数必定增多, 从而又导致耗时的增多, 这便引出了矛盾. 因此, 如何在优化与效率之间寻找一个平衡点, 使得程序的时间复杂度尽可能降低, 同样是非常重要的. 倘若一个剪枝的判断效果非常好, 但是它却需要耗费大量的时间来判断、比较, 结果整个程序运行起来也跟没有优化过的没什么区别, 这样就太得不偿失了.

3、分类

剪枝算法按照其判断思路可大致分成两类: 可行性剪枝及最优性剪枝.

3.1 可行性剪枝 —— 该方法判断继续搜索能否得出答案，如果不能直接回溯。

3.2 最优性剪枝

最优性剪枝，又称为上下界剪枝，是一种重要的搜索剪枝策略。它记录当前得到的最优值，如果当前结点已经无法产生比当前最优解更优的解时，可以提前回溯。

三：示例分析

题目来源于 poj 3900 The Robbery (类似于背包问题，但是不能够用背包求解)

1 分析：W，C 值很大，数组开不下（所以，不能用背包处理），但是发现 N 值很小，(1+15)*15/2=120，所以可以考虑 dfs + 剪枝。

首先利用贪心的思想我们对箱子进行排序，关键字为性价比（参考了 poj 里的 discuss）。也就是单位重量的价值最高的排第一，搜索的时候枚举顺序注意一定要从满到空，这样才能最快的找到一个可行解然后利用它进行接下来的剪枝。

剪枝 1. 之后所有的钻石价值 + 目前已经得到的价值 <=ans 则剪枝。

剪枝 2. 剩下的重量全部装目前最高性价比的钻石 + 目前已经得到的价值 <=ans 则剪枝（非常重要的剪枝）。

本作品采用知识共享署名-非商业性使用-相同方式共享 3.0 未本地化版本许可协议进行许可。
本文链接：https://hs-blog.axell.top/archives/22/