最优化算法实例讲解

DFS（深度优先搜索）是一种常见的算法，我们平时遇到的大部分题目都可以用 DFS 解决，但是一般情况下，这都是骗分算法，很少会有爆搜为正解的题目。因为 DFS 的时间复杂度特别高。

一、定义

DFS（深度优先搜索）定义上的深度优先搜索的思路与树的先序遍历非常相似，是针对图的搜索而提出的一种算法，下面是算法导论上的解释：

在深度优先搜索中，对于最新发现的顶点，如果它还有以此为顶点而未探测到的边，就沿此边继续探测下去，当顶点v的所有边都已被探寻过后，搜索将回溯到发现顶点v有起始点的那些边。这一过程一直进行到已发现从源顶点可达的所有顶点为止。如果还存在未被发现的顶点，则选择其中一个作为源顶点，并重复上述过程。整个过程反复进行，直到所有的顶点都被发现时为止。

在实际的操作中，我们一般对深度优先搜索问题进行分类：

（1）定义的DFS：对图的连通性进行测试，典型的问题：迷宫连通性测试、图的条件搜索等

（2）广义的DFS–DFS思路的应用：DFS搜索顺序+规则问题、穷举结果寻求最优解/符合条件解等等，由于其穷举答案的本质，又被称为爆搜

深度优先搜索(下文统称DFS)的精髓在于递归求解问题的思路以及回溯的处理。而针对搜索的过程，又有更为重要的剪枝、优化，必要的剪枝优化(通过对穷举答案方式进行改进)对DFS的顺利执行有着不可或缺的作用。本文章将针对DFS的原理、常见的题型、剪枝优化的思路进行分析。当然，爆搜的题型千千万，不可能一概而论，本文会通过具体的题目对几类问题的求解思路进行总结分析，构建基本的思维模型。

二、原理分类与分析

（1）DFS连通性模型

在测试图的连通性时，DFS与实际人们的思想一致，相对于起点选择一条路走到底，发现不行就返回选择的节点换一条路试，直到试出一条能到达终点的路。当然，一直试不出来就表示该起点与某点(终点)不连通。其他DFS连通性模型的思想与之类似。

1. 无需回溯：统计某点能到达的点的个数问题

在这类问题中，我们一般从某点出发进行搜索，对于已经被搜索过的点可以直接抛弃(标记不可访问)，对于当前被搜索的点递归搜索周围邻接的点并进行计数，直到无法搜索到合法的点返回。最终计数变量将记录所有能到达的点。

2.需要回溯：迷宫类问题，测试两点间连通性

在这类问题中，由于当前选择的路径未必能够到达目标点，因此需要设置回溯，当搜索到非法路径返回时需要“恢复现场”，即：对于该路径下各点的访问状态重置。

根据数据结构，又可以将两个模型分别继续细分，DFS可以基于邻接矩阵、邻接表、边集数组实现，思路相同，只是路径的遍历方式、点的访问有所改变。

⭐总结一下DFS的模板框架(简单描述)

function dfs(当前状态){
	if(当前状态 == 目的状态){
        ···
    }
    for(···寻找新状态){
        if(状态合法){
            vis[访问该点]；
            dfs(新状态);
            ?是否需要恢复现场->vis[恢复访问]
        } 
    }
    if(找不到新状态){
        ···
    }
}

（2）DFS思路应用-穷举求解问题

在无路可走时，我们往往会选择搜索算法，因为我们期望利用计算机的高性能来有目的的穷举一个问题的部分甚至所有可能情况，从而在这些情况中寻找符合题目要求的答案。这也是“爆搜”之名的由来。

我们约定，对于问题的介入状态，叫初始状态，要求的状态叫目标状态。

这里的搜索就是对实时产生的状态进行分析检测，直到得到一个目标状态或符合要求的最佳状态为止。对于实时产生新的状态的过程叫扩展（由一个状态，应用规则，产生新状态的过程）

搜索的要点：

1. 选定初始状态，在某些问题中可能是从多个合法状态分别入手搜索；

2. 遍历自初始状态或当前状态所产生的合法状态，产生新的状态并进入递归；

3. 检查新状态是否为目标状态，是则返回，否则继续遍历，重复2-3步骤。

对状态的处理：DFS时，用一个数组存放产生的所有状态。

1. 把初始状态放入数组中，设为当前状态；

2. 扩展当前的状态，从合法状态中旬寻找一个新的状态放入数组中，同时把新产生的状态设为当前状态；

3. 判断当前状态是否和前面的状态重复，如果重复则回到上一个状态，产生它的另一状态；

4. 判断当前状态是否为目标状态，如果是目标目标状态，则找到一个解答，根据实际问题需求，选择继续寻找答案或是直接返回。

5. 如果数组为空，说明对于该问题无解。

function dfs(当前状态, 一系列其他的状态量){
	if(当前状态 == 目的状态){
        ···
    }
    for(···寻找新状态){
        if(状态合法){
            vis[访问该点]；
            dfs(新状态);
            ?是否需要恢复现场->vis[恢复访问]
        } 
    }
    if(找不到新状态){
        是否需要创建新规则？{
            创建并对当前状态进行访问vis;
            继续搜索;
            恢复现场/恢复访问vis;
        }
    }
}

⭐与图的搜索类似，算法的框架基本不变，不同的是对于新状态的寻找、控制递归终止的条件更为复杂。在实际的题目中，会有一些题目需要对合法的新状态进行干预：可能在首轮搜索无法应用规则或所有条件均不满足且需要人为创建新的规则以继续搜索答案。这里也会设计到一系列剪枝与优化的问题。

举例说明：ACWing分成互质组

题目描述：给定 n 个正整数，将它们分组，使得每组中任意两个数互质。至少要分成多少个组？

输入格式：第一行是一个正整数 n。

                第二行是 n 个不大于10000的正整数。

输出格式：一个正整数，即最少需要的组数。

数据范围：1≤n≤10

输入样例：

6
14 20 33 117 143 175

输出样例：

3

题目分析与算法设计：

给定n个数字分成互质组，那么考虑最坏的情况，要分成n组(n个数均不互质)。因为题目的数据量并不大，可以采用DFS解决，具体思路如下：

预备工作：准备一个数组存输入数据，准备一个容器，用于存不同的组，准备一个检索函数，可以检索指定分组内是否存在与目的数字重合的

**开始DFS：**首先是递归终止条件，判断是否搜到末尾，搜到末尾则更新组数计数的值，返回；

**继续：**每次在已有分组中从头开始搜索，用检索函数判断当前数字是否可以加入分组，若可以，加入后递归向下一个数字搜索

**新建分组：**考虑组数为0的情况、找不到可以加入组的情况，应该设置创建新分组的情况，加入新分组后，同样递归向后搜索。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 11;
int n, p[N], cnt, ans = N;
vector<int> num[N];	//这里使用STL中的Vector，其长度可变，更方便模拟分组的状态

int gcd(int x, int y){
    return y ? gcd(y, x % y) : x;	//辗转相除求最大公约数
}

//判断两数是否互质
bool check(int x, int t){
    for (int i = 0; i < num[t].size(); i++){
        if (gcd(x, num[t][i]) > 1) return false;
    }
    return true;


void dfs(int now)
{
    if (now == n){
        ans = min(ans,  cnt);	//每次搜完取最小组数
        return;
    }
    for (int i = 0; i <  cnt; i++){
        if (check(p[now], i)){
            num[now].push_back(p[now]);
            dfs(now + 1);
            num[i].pop_back();
        }
    }
    //需要考虑首次搜索无组可加、当前状态无组可加
    num[cnt++].push_back(p[u]);
    dfs(now + 1);
    num[--cnt].pop_back(); 
}

int main(){
    cin >> n;
    for (int i = 0; i < n; i++) cin >> p[i];
    dfs(0);
    cout << ans << endl;
    return 0;
}

三、剪枝优化、题型归纳总结

在通过搜索解决实际问题的过程中，我们是通过穷举每种情况来寻找合法解，然而在一些情况比较复杂的题目、数据量较强的题目中，由于算法的时间复杂度较高、数据规模过大，从而会导致运行超时甚至程序卡死，因此在对复杂问题的答案进行搜索时，我们应该灵活的针对每种题型设计对应的搜索规则并进行优化，通常通过设置剪枝、排除无效情况、对问题进行适当的转化等手法对搜索算法进行优化，使算法高效的执行并得出我们想要的结果。

对算法的剪枝与优化堪称是爆搜算法的精髓，如何合理的设置剪枝优化直接关系能否得到结果，这对我们的解题思维是一个很大的挑战，本板块将对常见的剪枝优化思路、对细节的处理进行归纳总结。

（一）剪枝与优化

（1）剪枝与优化的原则

1. 正确性：剪枝优化的过程是使算法逼近最优解的过程，而不是使算法远离最优解甚至跳过最优解的过程。剪枝的前提是保证对最优解不丢不漏。

2. 准确性：在保证正确性的前提下，我们采取必要的手段使算法跳过一定不含有目标状态/最优解的分支，从而保证算法高效地进行并更迅速的找出

3. 高效性：设计优化程序的根本目的,是要减少搜索的次数,使程序运行的时间减少. 但为了使搜索次数尽可能的减少,我们又必须花工夫设计出一个准确性较高的优化算法,而当算法的准确性升高,其判断的次数必定增多,从而又导致耗时的增多,这便引出了矛盾. 因此,如何在优化与效率之间寻找一个平衡点,使得程序的时间复杂度尽可能降低,同样是非常重要的。

（2）枝与优化的一般入手点

1. 优化搜索顺序：在一些题目中，可以通过对子问题分支进行分析，先解决相对简单的子问题从而使尚未解决的子问题得到简化，通过对搜索顺序的优化可以实现这一点。

2. 排除冗余信息：对限制条件进行分析，不要额外添加没有意义的搜索规则

3. 可行性剪枝：对于显然不包含目标状态的搜索方向及时停止搜索，转而向可能包含目标状态的分支进行搜索

4. 最优性剪枝：每次搜索完成后更新当前得到的最优状态/最优解，在每次搜索开始前判断当前解是否已经比上次得出的状态/解更劣？如果是则停止本次搜索，转向其他搜索分支

5. 记忆化搜索：记忆化搜索是一种搜索的形式，对搜索的结果用数组或其他数据结构记录下来。

（二）问题的转化、数据的预处理与压缩

在解决实际问题时，我们可以巧妙地对题目给出的数据进行适当的转化，从而构造出DFS的模型进行求解。

这与数学上的构造函数思想类似，在掌握题目数据的基础上对数据进行预处理从而构造可以按照某规则进行检索的新数据，通过对新数据进行搜索从而得出原数据符合要求的解。

举例说明：

单词接龙是一个与我们经常玩的成语接龙相类似的游戏。

现在我们已知一组单词，且给定一个开头的字母，要求出以这个字母开头的最长的“龙”，每个单词最多被使用两次。

在两个单词相连时，其重合部分合为一部分，例如 beast 和 astonish ，如果接成一条龙则变为 beastonish。

我们可以任意选择重合部分的长度，但其长度必须大于等于1，且严格小于两个串的长度，例如 at 和 atide 间不能相连。

输入格式：输入的第一行为一个单独的整数 n 表示单词数，以下 n 行每行有一个单词（只含有大写或小写字母，长度不超过20），输入的最后一行为一个单个字符，表示“龙”开头的字母。

你可以假定以此字母开头的“龙”一定存在。

输出格式：只需输出以此字母开头的最长的“龙”的长度。

输入样例：

5
at
touch
cheat
choose
tact
a

输出样例：

23

代码如下：

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

vector<int> ver[N],edge[N];//匹配的单词编号和匹配长度
string word[N];
int n, res;
int st[N];

void dfs(string u, int k)
{
    st[k] ++;
    res = max(res, (int)u.size());

    for(int i = 0;i < ver[k].size(); i++)
    {
        int point = ver[k][i],d = edge[k][i];
        if(st[point]<2)
            dfs(u + word[point].substr(d), point);
    }
    st[k]--;
}

int main(){
    cin >> n;
    for(int i=1;i<=n;i++) cin >> word[i];

    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        {
            string a = word[i] , b = word[j];
            int len = min(a.size(),b.size());
            for(int k=1;k<len;k++)
            {
                if(a.substr(a.size()-k)==b.substr(0,k))
                {
                    ver[i].push_back(j);
                    edge[i].push_back(k);
                    break;
                }
            }
        }

    string head;
    cin >> head;
    for(int i = 1; i <= n; i++)
        if(head[0] == word[i][0]) dfs(word[i], i);
    cout << res << endl;
    return 0;
}

对于数据的预处理和规模压缩，举一个非常巧妙地例子：数独

题目描述：数独是一种传统益智游戏，你需要把一个9 × 9的数独补充完整，使得图中每行、每列、每个3 × 3的九宫格内数字1~9均恰好出现一次。

请编写一个程序填写数独。

输入格式

输入包含多组测试用例。

每个测试用例占一行，包含81个字符，代表数独的81个格内数据（顺序总体由上到下，同行由左到右）。

每个字符都是一个数字（1-9）或一个”.”（表示尚未填充）。

您可以假设输入中的每个谜题都只有一个解决方案。

文件结尾处为包含单词“end”的单行，表示输入结束。

输出格式

每个测试用例，输出一行数据，代表填充完全后的数独。

输入样例：

4.....8.5.3..........7......2.....6.....8.4......1.......6.3.7.5..2.....1.4......
......52..8.4......3...9...5.1...6..2..7........3.....6...1..........7.4.......3.
end

输出样例：

417369825632158947958724316825437169791586432346912758289643571573291684164875293
416837529982465371735129468571298643293746185864351297647913852359682714128574936

题目分析：

本题目数据量较大，用爆搜解决超时是个问题，因此如何优化剪枝便成了重点，下面是需要进行的准备工作，这些预处理极其关键！

1. 开始时判断是否搜索成功，若成功则返回；

2. ！优化：找出备选方案数最少的空格，先填它，从而实现整体的优化；

3. 找出能填的数字怼上去试试，能行继续搜，搜到底return上来true，搜不到返回false，那么恢复现场，继续找数搜。

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

const int N = 9;
int map[1 << N], ones[1 << N];
int row[N], col[N], cell[3][3];
char sudoku[100];

inline int lowbit(int x){
    return x & (-x);
}

inline int get(int x, int y){
    return row[x] & col[y] & cell[x / 3][y / 3];
}

void makeg(){
    for(int i = 0; i < N; i++) map[1 << i] = i;
    for(int i = 0, k = 0; i < (1 << N); i++, k = 0){
        for(int j = i; j; j -= lowbit(j)) k++;
        ones[i] = k;
    }
}

void init(){
    for (int i = 0; i < N; i++) row[i] = col[i] = (1 << N) - 1;
    for(int i = 0; i < 3 ; i++)
        for(int j = 0; j < 3; j++) cell[i][j] = (1 << N) - 1;
}

bool dfs(int cnt){
    //搜索成功结束
    if(!cnt) return true;
    //找出备选数字数目最少的空格
    int minn = 10;
    int x, y;
    for(int i = 0; i < N; i++){
        for(int j = 0; j < N; j++){
            if(sudoku[i * 9 + j] == '.'){
                int tmp = ones[get(x, y)];
                if(tmp < minn) minn = tmp, x = i, y = j;
            }
        }
    }
    for(int i = get(x, y); i; i -= lowbit(i)){
        int tmp = map[lowbit(i)];
        row[x] -= 1 << tmp;
        col[y] -= 1 << tmp;
        cell[x / 3][y  /3] -= 1 << tmp;
        sudoku[x * 9 + y] = '1' + tmp;
        if(dfs(cnt - 1)) return true;
        row[x] += 1 << tmp;
        col[y] += 1 << tmp;
        cell[x / 3][y / 3] += 1 << tmp;
        sudoku[x * 9 + y] = '.';
    }
    return false;
}

int main(){
    makeg();
    while(cin >> sudoku,  sudoku[0] != 'e'){
        init();
        int cnt = 0;
        for(int i = 0, k = 0; i < N; i++){
            for(int j = 0; j < N; j++, k++){
                if(sudoku[k] != '.'){
                    int tmp = sudoku[k] - '1';
                    row[i] -= 1 << tmp;
                    col[j] -= 1 << tmp;
                    cell[i / 3][j / 3] -= 1 << tmp;
                }
                else cnt++;
            }
        }
        dfs(cnt);
        cout << sudoku << endl;
    }
    return 0;
}

从本题中可以看出，通过合理利用位运算使运算和数据的规模极大的得到了缩小，因此，合理利用巧解法可以优化搜索算法。但这类思路通常难以想到，需要大量的刷题经验积累。