投稿
  1. 高性能架构探索首页
  2. C/C++

搜索问题总结

admin • • C/C++ • 阅读 148
目录

剪枝技巧

  • P1731生日蛋糕

    一道专门考察剪枝的搜索题，在这里我把一些常用的剪枝手段进行一些总结：

    1. 有时候先对所有的东西进行排序，然后再从大的开始搜索，剪枝效果更明显，原因是比较大的在选择之后变数较小，即在比较靠近根的位置进行剪枝

    2. 在搜索有序的时候，可以记录上一次选了什么东西，这样有时候可以确定下一次枚举的起始位置，也有时候可以减少出现相邻两次操作效果抵消的问题

    3. 利用极限进行剪枝，比如把xx都按最大算，或者把xx都按最小算，如果这样都不行，就cut掉（可行性和最优性都有）

    4. 循环+dfs时，每轮循环完了之后，可以判断一下是不是已经把答案搜出来了，如果搜出来了，就return

    5. 桶有时候可以优化我们的搜索

    6. A*算法使用时，为了减少priority_queue的调整，可以用大于等于/小于等于号。

    7. 一些数学公式预测未来的行为（比如求和公式等）

    本题代码如下：

    #include <cstdio>
#include <algorithm>
#include <cmath>
#define ll long long
#define INF 999999999
using namespace std;
ll n,m,s=INF;
void dfs(ll step,ll r,ll h,ll sum,ll cost);
int main(){
    ll r,h;
    scanf("%lld %lld",&n,&m);
    for(r=sqrt((n/(m)))+1;r>=m;r--){ //先搜大的再搜小的 
        for(h=n/((m)*(m))+1;h>=m;h--){
            dfs(1,r,h,2*r*h+r*r,r*r*h);
        }
    }
    if(s==INF){
        printf("0\n");
        return 0;
    } 
    printf("%lld\n",s);
    return 0;
}
void dfs(ll step,ll r,ll h,ll sum,ll cost){
    ll x=m-step;
    if(sum+(x*(x+1)*(2*x+1))/3>s){ //最优性剪枝，后面的按照1^2+2^2+……的最小情况算 
        return;
    }
    if(cost+x*(r-1)*(r-1)*(h-1)<n){ //最大也拼不成 
        return;
    }
    if(cost+(x*x*(x+1)*(x+1))/4>n){ //可行性剪枝，这样不够拼成蛋糕 ，负优化？？ 
        return;
    }
    if(step==m){
        if(cost==n){
            s=min(s,sum);
            return;
        } else {
            return;
        }
    } else {
        if(cost>=n){ //体积超了 
            return;
        } else {
            if(r<=0 || h<=0){ //前面用多了 
                return ;
            } else {
                for(ll i=r-1;i>=m-step;i--){ //枚举确保能够拼下去
                    for(ll j=h-1;j>=m-step;j--){
                        dfs(step+1,i,j,sum+2*i*j,cost+i*i*j);
                    }
                }
            }
        }
    }
}

启发式搜索

  • P2324 骑士精神

    这道题地图太大了，状压都压不住，所以我们得考虑用dfs之类的搜索方法去做。但是裸的dfs又不行，所以考虑一下启发式迭代加深搜索，启发函数挺好写的，就是不在目标位置上的点的个数/2。然后就直接用启发函数剪枝就好了。另外，为了更有效的剪枝，我们需要在深搜的时候，避免上一次和这一次的移动抵消了，所以dfs的时候我们最好传一下上一次进行了什么操作这样一个参数。事实上，这个剪枝很重要，没有它的话即使是IDA*也没法通过此题（只有20pts）。

    AC代码如下：

    #include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <cstring>
#define ll long long
using namespace std;
ll t,flag=0;
char graph[7][7];
char goal[7][7];
int dx[8]={-1,-1,2,2,-2,-2,1,1}; //对称式存储方法比较好判断抵消的情况
int dy[8]={-2,2,-1,1,-1,1,-2,2};
ll evaluate();
void dfs(ll step,ll maxstep,ll x,ll y,ll last);
int main(){
    scanf("%lld",&t);
    for(int i=0;i<5;i++){
        for(int j=0;j<i;j++){
            goal[i][j]='0';
        }
        for(int j=i;j<5;j++){
            goal[i][j]='1';
        }
    }
    goal[2][2]='*';
    goal[3][3]='0';
    goal[4][4]='0';
    for(int i=0;i<t;i++){
        for(int j=0;j<5;j++){
            scanf("%s",graph[j]);
        }
        flag=0;
        ll x,y;
        for(ll j=0;j<5;j++){
            for(ll k=0;k<5;k++){
                if(graph[j][k]=='*'){
                    x=j;
                    y=k;
                }
            }
        }
        for(ll j=1;j<=15;j++){
            if(flag) break;
            dfs(0,j,x,y,8);
        }
        if(flag==0){
            printf("-1\n");
        }
    }
    return 0;
}
void dfs(ll step,ll maxstep,ll x,ll y,ll last){
    ll ok=1;
    if(flag) return;
    ll value=evaluate();
    if(step+value>maxstep) return;
    if(step==maxstep) {
        for(int i=0;i<5;i++){
            for(int j=0;j<5;j++){
                if(graph[i][j]!=goal[i][j]){
                    ok=0;
                    break;
                }
            }
            if(ok==0)
                break;
        }
        if(ok){ //已经找到了 
            flag=1;
            printf("%lld\n",maxstep);
            return;
        }
        return;
    } else {
        for(int i=0;i<8;i++){
            ll xx=x+dx[i],yy=y+dy[i];
            if(xx>=0 && xx<5 && yy>=0 && yy<5 && last+i!=7){ //一定不要和上一次抵消了！
                swap(graph[xx][yy],graph[x][y]);
                dfs(step+1,maxstep,xx,yy,i);
                swap(graph[xx][yy],graph[x][y]);
            }
            if(flag) return;
        }
    }
}
ll evaluate(){
    ll value=0;
    for(int i=0;i<5;i++){
        for(int j=0;j<5;j++){
            if(graph[i][j]!=goal[i][j]){
                value++;
            }
        }
    }
    return value/2;
}

  • P5507 机关

    题目大意见原题。

    这个题是我做过的第一道启发式搜索的题目。在做这个题目之前，我们不难想到可以用双向广搜去做这个题，并且大概率能通过。但是，我这个题不会写双向广搜啊，所以就得另寻他路了。之前以为启发式很玄，但其实拿这个例子来讲，或者用八数码的例子讲，那些抽象的概念就变得容易理解多了。这道题用IDA\(*\)是过不了的，毕竟它的时间消耗还是挺大的，为了通过这道题，我们需要用A\(*\) 算法。对于这道题，就是用bfs，只不过在bfs的过程中，所有入队的状态都要先算一下它的启发函数和已经走过的距离，并且队列要用优先队列，这样能保证那些更有希望走到终点的状态先被搜到。注意不能只按照启发函数大小确定优先级，还有原先已经走过的步数！值得注意的是，这里利用了剪枝技巧中的6号技巧，这样能减少堆的调整（您可能会发现我的代码如果不用这个技巧就会TLE，用的话会跑得飞快）。整个题从裸的bfs，到双向bfs，再到IDA\(*\)和A\(*\)，我写了一整天才通过，好艰难！

    A\(*\)代码如下：

    #include <bits/stdc++.h>
#define ll long long
using namespace std;
typedef struct{
    int state;
    int c[5];
}Node;
typedef struct{
    int allstate;
    int value;
    int step;
    int path[20];
}AllState;
Node node[13];
int sign[1<<24];
priority_queue<AllState> q;
AllState bfs();
int evaluate();
int getHashValue();
void setState(AllState s);
int main(){
    for(int i=1;i<=12;i++){
        scanf("%d%d%d%d%d",&node[i].state,&node[i].c[1],&node[i].c[2],&node[i].c[3],&node[i].c[4]);
        node[i].state--;
    }
    AllState ans=bfs();
    printf("%d\n",ans.step);
    for(int i=1;i<=ans.step;i++)
        printf("%d ",ans.path[i]);
    return 0;
}
AllState bfs(){
    AllState start;
    start.allstate=getHashValue();
    start.step=0;
    start.path[0]=0;
    start.value=evaluate();
    q.push(start);
    sign[start.allstate]=1;
    while(!q.empty()){
        AllState now=q.top();
        q.pop();
        setState(now);
        if(now.value==0){
            return now;
        }
        for(int i=1;i<=12;i++){
            int i_state=node[i].state;
            int follow=node[i].c[i_state+1];
            int follow_state=node[follow].state;
            if(i_state==0 && follow_state==0) continue;
            node[i].state=(node[i].state+1)%4;
            node[follow].state=(node[follow].state+1)%4;
            AllState newstate;
            newstate.allstate=getHashValue();
            newstate.value=evaluate();
            newstate.step=now.step+1;
            for(int j=1;j<=now.step;j++)
                newstate.path[j]=now.path[j];
            newstate.path[newstate.step]=i;
            if(!sign[newstate.allstate]) {
                sign[newstate.allstate]=1;
                q.push(newstate);
            } 
            node[i].state=i_state;
            node[follow].state=follow_state;
        }
    }
    printf("fuck\n");
    return q.top();
}
int evaluate(){
    int value=0;
    for(int i=1;i<=12;i++){
        if(node[i].state!=0){
            value+=4-node[i].state;
        }
    }
    return value/2;
}
void setState(AllState s){
    int value=s.allstate;
    for(int i=12;i>=1;i--){
        node[i].state=value%4;
        value/=4;
    }
}
int getHashValue(){
    int value=0;
    for(int i=1;i<=12;i++)
        value=4*value+node[i].state;
    return value;
}
bool operator <(AllState a,AllState b){
    if(a.value+a.step>=b.value+b.step) //利用了6号剪枝技巧
        return true;
    return false;
}

meet in the middle

  • P4799 世界冰球锦标赛

    题目大意：有一些物品，物品有价值和重量两个属性，在不超过人能承受的最大重量的情况下，求有多少种取物品的方案。

    如果题目数据小，那就是一个01背包求不同方案数的裸题。但是这个题目承受重量是1e18，太大了，不过物品却较少，<=40，所以我们可能要考虑换一种方案。显然每个物品有选与不选两个可能，如果暴力搜索，那么有\(2^{40}\) 种方案，太多了，根本算不完。我们可能想到了双向搜索，但是之前只写过双向广搜解决地图走路问题，这个题似乎要双向深搜？咋做呢？根据学习meet in the middle算法，我知道了这个题的解决方案：正着搜一半，反着搜另一半，我们可以把前一半的结果记下来，排个序，然后每进行完一次后一半的搜索，就在前一半中二分查找一下，看看有多少个情况能够使得重量不超，这样整合答案的时间每次是对数级的，状态数也少了。这个题目是典型的meet in the middle的思想，不难有这个思路，但是二分合并答案可能是没有想到的。另外，前一半搜索的结果被记录下来了，这是典型的以空间换时间的做法。先对结果进行sort，然后再进行其他操作，也可能能够使得后续操作免除一些麻烦（比如非负，可以去掉绝对值），或者更快（比如二分）。

    这道题特别注意的一点实现细节：我们存下来了前半部分和后半部分的状态，所以状态数组要足够大，得超过1e6吧。

    代码如下：

    #include <cstdio>
#include <algorithm>
#include <cstdlib>
#define ll unsigned long long
using namespace std;
const int N=1e7+9;
ll left[N],right[N],n,m,a[50],cnt,cntleft,cntright,ans;
void dfs(ll step,ll maxstep,ll sum,ll s[]);
ll b_search(ll l,ll r,ll s[],ll key);
int main(){
    scanf("%llu %llu",&n,&m);
    for(ll i=1;i<=n;i++){
        scanf("%llu",&a[i]);
    }
    dfs(1,n/2,0,left);
    cntleft=cnt;
    cnt=0;
    dfs(n/2+1,n,0,right);
    cntright=cnt;
    sort(left+1,left+cntleft+1);
//  for(int i=1;i<=cntleft;i++){
//      printf("%lld ",left[i]);
//  }
//  printf("\n");
    for(ll i=1;i<=cntright;i++){
        ll pos=b_search(1,cntleft,left,m-right[i]);
        ans=ans+pos-1;
    }
    printf("%llu\n",ans);
    return 0;
} 
ll b_search(ll l,ll r,ll s[],ll key){
    ll mid;
    while(l<=r){
        mid=(l+r)/2;
        if(s[mid]<=key){
            l=mid+1;
        } else {
            r=mid-1; //?
        }
    }
    return l;
}
void dfs(ll step,ll maxstep,ll sum,ll s[]){
    if(sum>m){
        return;
    }
    if(step>maxstep){
        if(sum<=m){
            s[++cnt]=sum;
            return;
        } else {
            return;
        }
    }
    dfs(step+1,maxstep,sum+a[step],s);
    dfs(step+1,maxstep,sum,s);
}

原文链接: https://www.cnblogs.com/BUAA-Wander/p/13311277.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍;

也有高质量的技术群，里面有嵌入式、搜广推等BAT大佬

    搜索问题总结

原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/367357

非原创文章文中已经注明原地址，如有侵权，联系删除

关注公众号【高性能架构探索】，第一时间获取最新文章

转载文章受原作者版权保护。转载请注明原作者出处！

赞 (0)
adminadmin
0 0
上一篇 2023年3月2日 下午5:44
下一篇 2023年3月2日 下午5:44

相关推荐