深度优先搜索（dfs）算法之四——性能优化

在竞赛中，我们有时会碰到一些题目，它们既不能通过建立数学模型解决，又没有现成算法可以套用，或者非遍历所有状况才可以得出正确结果。这时，我们就必须采用搜索算法来解决问题。

搜索算法按搜索的方式分有两类，一类是深度优先搜索，一类是广度优先搜索。

深度搜索编程简单，程序简洁易懂，空间需求也比较低，但是这种方法的时间复杂度往往是指数级的，倘若不加优化，其时间效率简直无法忍受；

所以，对程序进行优化，就成为搜索算法编程中最关键的一环。

4.1 细节优化

在深度优先搜索（dfs）算法之三——寻路中的N皇后问题中，每一层递归都需要进行判断上放、左斜线、右斜线是否有落子，常规思维是通过三个循环来判断，但是我们可以应用数学规律（同一直线上的点的行列和或差相等）简化，或者用二进制（位压）的特性来提高检测性能。

N皇后 应用数学规律优化
#include<bits/stdc++.h>
using namespace std;
int n,ans;
int x[100],y[100],k1[100],k2[100];
void out(){
    if(ans<3){
        for(int i=1;i<=n;i++)
            cout<<x[i]<<' ';
        cout<<'\n';
    }
} 
void dfs(int i){
    if(i>n){
        out();
        ans++;
        return;
    }
    for(int j=1;j<=n;j++){
        if(y[j]==0&&k1[i-j+n]==0&&k2[i+j]==0){
            y[j]=k1[i-j+n]=k2[i+j]=1;
            x[i]=j;
            dfs(i+1);
            y[j]=k1[i-j+n]=k2[i+j]=0;
        }
    }
}
int main(){
    cin>>n;
    dfs(1);
    cout<<ans;

    return 0;
}

N皇后 二进制位压缩
#include<bits/stdc++.h>
using namespace std;

#define maxn 1000

using namespace std;
int n,m,ans,a[maxn];
void dfs(int k,int l,int b,int r)
{
    if(k>n)
    {
       if(++ans<=3)
        {
            for(int i=1;i<n;i++)
                printf("%d ",a[i]);
            printf("%d\n",a[n]);
        }
        return;
    }
    int s=~(l | b | r);
    for(int i=1;i<=n;i++)
    {
        int bit = 1<<(i-1);
        if(s & bit)
        {
            a[k]=i;
            dfs(k+1,(l | bit)<<1,b|bit ,(r | bit)>>1);
        }

    }
}
int main()
{
    scanf("%d",&n);
    dfs(1,0,0,0);
    printf("%d\n",ans);
    return 0;
}

4.2 记忆化搜索

例题一、李白打酒加强版

话说大诗人李白，一生好饮。幸好他从不开车。

一天，他提着酒壶，从家里出来，酒壶中有酒 $2$ 斗。他边走边唱：

无事街上走，提壶去打酒。
逢店加一倍，遇花喝一斗。

这一路上，他一共遇到店 $N$ 次，遇到花 $M$ 次。已知最后一次遇到的是花，他正好把酒喝光了。

请你计算李白这一路遇到店和花的顺序，有多少种不同的可能?

注意：壶里没酒（ $0$ 斗）时遇店是合法的，加倍后还是没酒；但是没酒时遇花是不合法的。

输入数据格式

第一行包含两个整数 $N$ 和 $M$ 。

输出数据格式

输出一个整数表示答案。由于答案可能很大，输出模 $1000000007$ （即 $10^9+7$ ）的结果。

输入输出样例

输入 #1	输出 #1
5 10	14

说明与提示

【样例说明】

如果我们用 0 代表遇到花，1 代表遇到店， $14$ 种顺序如下:

010101101000000
010110010010000
011000110010000
100010110010000
011001000110000
100011000110000
100100010110000
010110100000100
011001001000100
100011001000100
100100011000100
011010000010100
100100100010100
101000001010100

【评测用例规模与约定】

对于 $40 \%$ 的评测用例： $1 \leq N, M \leq 10$ 。

对于 $100 \%$ 的评测用例： $1 \leq N, M \leq 100$ 。

在线练习（30分钟左右）李白打酒加强版

解题思路：

简化为每一步会遇到酒店或花:

遇到店：酒的数量乘以2，店的数量减1。
遇到花：酒的数量减1，花的数量减1。
最后一步如果酒为0则为一种方案。

李白打酒
#include<bits/stdc++.h>
#define MOD 1000000007
using namespace std;

int n, m;

int dfs(int st, int shop, int flower) {
    if(st < 0 || shop < 0 || flower < 0) {
        return 0;
    }
    if(st > flower) {
        return 0;
    }
    if(st == 1 && shop == 0 && flower == 1) {
        return 1;
    }

    return (dfs(st * 2, shop - 1, flower) + dfs(st - 1, shop, flower - 1)) % MOD;
}

int main() {
    cin >> n >> m;
    cout << dfs(2, n, m);
    return 0;
}

备注

画图分析可以得知，每一步如果酒一样、剩余花数一样、剩余酒店一样的时候，后面不论什么情况，方案数都是一样，于是我们可以将同样的酒、花、店的哪一个调用的结果存起来，后面直接调用，就不用再往下递归了，避免了重复递归搜索，就可以提高性能。

李白打酒
#include<bits/stdc++.h>
#define MOD 1000000007
using namespace std;

int n, m;
int dp[105][105][105];

int dfs(int st, int shop, int flower) {
    if(st < 0 || shop < 0 || flower < 0) {
        return 0;
    }
    if(st > flower) {
        return 0;
    }
    if(st == 1 && shop == 0 && flower == 1) {
        return 1;
    }
    if (dp[st][shop][flower] != -1) {
        return dp[st][shop][flower]; //记忆化搜索: 搜索过的就直接跳过
    }

    dp[st][shop][flower] = (dfs(st * 2, shop - 1, flower) + dfs(st - 1, shop, flower - 1)) % MOD;
    return dp[st][shop][flower];
}

int main() {
    memset(dp, -1, sizeof(dp));
    cin >> n >> m;
    cout << dfs(2, n, m);
    return 0;
}

4.3 剪枝

在深度优先搜索（DFS）中，剪枝是一种常用的优化技术，用于减少不必要的搜索空间，从而提高搜索效率。剪枝的核心思想是在搜索过程中，尽早地识别和排除那些不可能产生解的路径或状态，从而避免在这些无效路径上浪费时间和资源。

可行性剪枝

可行性剪枝最常见, 就是每一步递归前通过一些方法判断这个方向可不可以走。比如在上面的N皇后问题中，采用一些方法判断这一步可不可以放在这一列，而不是等到这条路径递归到最后一行再判断本条路径是否符合要求，这就是可行性剪枝。正所谓“兵无常势，水无常形”，剪枝没有固定方法，需要因时而异，具体问题具体分析，但是研究好的剪枝策略在很多时候是唯一的解决方案。

扩展练习：

*学习笔记

暂没有学习笔记，快来抢first blood ！

4.1 细节优化​

4.2 记忆化搜索​

例题一、李白打酒加强版​

输入数据格式​

输出数据格式​

输入输出样例​

说明与提示​

解题思路：​

4.3 剪枝​

可行性剪枝​

扩展练习：​

*学习笔记​