DFS

· · 个人记录

知识点1：迭代加深DFS

应用情景

如图，当搜索树的深度过大但答案在搜索树的浅层时，根据DFS的搜索顺序，会先枚举左子树的所有内容（图中框出部分），接下来才能够找到答案。

解决办法

所以，如果我们已经知道答案出现出浅层，我们可以借用BFS的搜索顺序（一层一层搜），但用BFS的方法实现：

  1. 我们在每一次DFS的时候，限制搜索的层数。
  2. 当按照当前限制的层数搜索未搜索到答案，就把搜索限制加1.
  3. 当搜索到答案，当前的搜索限制就是答案。

代码：

#include<bits/stdc++.h>
using namespace std;
/*!@#$%^&*!@#$%^&*~~优美的分界线~~*&^%$#@!*&^%$#@!*/
int n,limit;//DFS搜索限制
int l[10000];//路径记录
/*!@#$%^&*!@#$%^&*~~优美的分界线~~*&^%$#@!*&^%$#@!*/
bool dfs(int dep){
    if(dep>limit) return 0;//超出DFS限制范围 return
    if(找到答案) return 1;
    for(枚举可达状态){
        %%%
        if(dfs(dep+1)) return 1;//如果找到答案，继续return 1
        %%%
    }
    return 0;//未找到答案，return 0
}
/*!@#$%^&*!@#$%^&*~~优美的分界线~~*&^%$#@!*&^%$#@!*/
int main(){
    while(cin>>n && n){
        limit=1,l[1]=1;
        while(!dfs(开始参数)) limit++;
        printf("%d ",limit-1);
        for(int i=1;i<limit;i++) printf("%d ",l[i]);//输出答案路径
        cout<<'\n';
    }
    return 0;
}

知识点2：双向搜索

应用情景

当我们已经知道起点和终点的情况下，我们可以使用双向搜索来使时间复杂度减半:
从起点和终点分别搜索一半，在中间相遇。
如图：
这样时间复杂度减少一半。

例题：

例19.1-2 送礼物
方法：

  1. 首先，看见题目我们很容易想到01背包，但一看题目数据范围：G[i]\leq 2^{31}-1,根本存不下。
  2. 但是如果我们直接使用DFS的话，时间复杂度O(2^N)
  3. 送一我们想到双向搜索，DFS1搜一般总价格，然后DFS2一一与DFS1的结果比较。

代码:

#include<bits/stdc++.h>
using namespace std;
/*!@#$%^&*!@#$%^&*~~优美的分界线~~*&^%$#@!*&^%$#@!*/
int W,n,ans;
int tot,l[50],f[1<<24];
/*!@#$%^&*!@#$%^&*~~优美的分界线~~*&^%$#@!*&^%$#@!*/
void dfs1(int cnt,int sum){
    if(cnt==n/2+1){
        f[++tot]=sum;
        return ;
    }
    dfs1(cnt+1,sum);
    if(l[cnt]<=W-sum) dfs1(cnt+1,sum+l[cnt]);
}
void dfs2(int cnt,int sum){
    if(cnt==n+1){
        ans=max(ans,sum+f[upper_bound(f+1,f+tot+1,W-sum)-f-1]);
        return ;
    }
    dfs2(cnt+1,sum);
    if(l[cnt]<=W-sum) dfs2(cnt+1,sum+l[cnt]);
}
/*!@#$%^&*!@#$%^&*~~优美的分界线~~*&^%$#@!*&^%$#@!*/
signed main(){
    cin>>W>>n;
    for(int i=1;i<=n;i++) cin>>l[i];
    sort(l+1,l+n+1);
    dfs1(1,0);sort(f+1,f+tot+1);
    dfs2(n/2+1,0);cout<<ans;
    return 0;
}