BruceJay's Blog

IDA*算法总结

| Comments

扯淡

Bruce的搜索也是弱得难以想象。
什么遗传,模拟退火,Dancing_Link都看不懂,于是struggle to learn IDA*。
Suffering....

基本思路(Main Thoughts):

IDA*顾名思义,就是迭代深搜和启发式搜索的结合。
就是通过迭代加深和估价函数来剪枝。

实现步骤(Implementation Steps):

Step1

枚举深度上限maxd。

Step2

搜索,只考虑深度不超过maxd的节点。

Step3

估价函数剪枝。g(x)表示当前层数,h(x)表示估计还要扩展的层数(h(x)>=实际还要扩展的层数)。

模板(Code):

bool IDAstar(int gx){
    int hx=h(); //估价函数
 if(gx+hx>maxd) return false; //估价函数剪枝
 if(hx==0) return true;
    for(int i=1;i<=n;i++){ //枚举后继状态
     move(i); //转移
     if(IDAstar(gx+1)) return true;
        remove(i); //回溯
 }
    return false;
}
for(maxd=0;;maxd++) if(IDAstar(0)) break;

主要用途&优缺点(Main Applications & Advantages & Disadvantages):

主要用途

一般处理没有明显的层数上界的搜索。

优点

快,代码难度不大。

缺点

估价函数的选取不当很大程度上会影响搜索效率。

推荐题目(Recommendatory Problems) :

Bzoj1085 骑士精神

能在15步内出解,枚举答案上界不会很大,很支持IDA*。
一次至多使一个在不合法位置上的骑士到达合法位置,依此建立估价函数。

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
 
const int N = 5;
const int dx[8]={-2,-2,-1,-1,1,1,2,2};
const int dy[8]={-1,1,-2,2,-2,2,-1,1};
const int g[5][5]={{1,1,1,1,1},
{0,1,1,1,1},
{0,0,2,1,1},
{0,0,0,0,1},
{0,0,0,0,0}};
int a[N][N]; char s[N][N];
int T,ans; bool flag;
 
int Get()
{
    int res=0;
    for(int i=0;i<5;i++)
    for(int j=0;j<5;j++)
        if(a[i][j]!=g[i][j] && a[i][j]!=2) res++;
    return res;
}
 
void Dfs(int step,int x,int y)
{
    int f=Get();
    if(!f) flag=true;
    if(step+f>ans || flag) return;
    for(int i=0;i<8;i++){
        int tx=x+dx[i]; int ty=y+dy[i];
        if(tx<0 || tx>4 || ty<0 || ty>4) continue;
        swap(a[x][y],a[tx][ty]);
        Dfs(step+1,tx,ty);
        swap(a[x][y],a[tx][ty]);
    }
}
 
int main()
{
    int x,y;
    scanf("%d",&T);
    while(T--){
        flag=false;
        for(int i=0;i<5;i++) scanf("%s",s[i]);
        for(int i=0;i<5;i++)
        for(int j=0;j<5;j++){
            if(s[i][j]=='*'){
                a[i][j]=2;
                x=i; y=j;
            }
            else a[i][j]=s[i][j]-'0';
        }
        for(ans=0;ans<=15;ans++){
            Dfs(0,x,y);
            if(flag) {printf("%d\n",ans); break;}
        }
        if(!flag) puts("-1");
    }
    return 0;
}

Codevs2495 水叮当的脚步

搜索策略很重要。要分别标记与左上角在同一颜色块上的点,以及在该颜色块边界上的点(不属于该颜色块),每次染色就将边界上的一些点加入该颜色块。
除左上角颜色块外,还剩下一些颜色,每次染色至多消除一种,依此建立估价函数。

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

const int N = 10;
const int C = 6;
const int dx[4]={-1,1,0,0};
const int dy[4]={0,0,-1,1};
int a[N][N]; int b[N][N];
bool used[C]; bool flag;
int n,ans;

inline int read()
{
    int t=1,x=0; char ch=getchar();
    while(ch<'0' || ch>'9'){
        if(ch=='-') t=-1;
        ch=getchar();
    }
    while(ch>='0' && ch<='9'){
        x=x*10+ch-'0';
        ch=getchar();
    }
    return t*x;
}

int Get()
{
    int res=0;
    memset(used,0,sizeof(used));
    for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
        if(b[i][j]!=1 && !used[a[i][j]]){
            used[a[i][j]]=true;
            res++;
        }
    return res;
}

void Dfs(int x,int y,int c)
{
    b[x][y]=1;
    for(int i=0;i<4;i++){
        int tx=x+dx[i];
        int ty=y+dy[i];
        if(!tx || tx>n || !ty || ty>n) continue;
        if(b[tx][ty]==1) continue; b[tx][ty]=2;
        if(a[tx][ty]==c) Dfs(tx,ty,c);
    }
}

bool Fill(int c)
{
    bool res=false;
    for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
        if(b[i][j]==2 && a[i][j]==c){
            res=true;
            Dfs(i,j,c);
        }
    return res;
}

void Search(int step)
{
    int f=Get();
    if(!f) flag=true;
    if(step+f>ans || flag) return;
    int c[N][N];
    for(int i=0;i<=5;i++){
        memcpy(c,b,sizeof(c));
        if(Fill(i)) Search(step+1);
        memcpy(b,c,sizeof(b));
    }
}

int main()
{
    while(1){
        n=read(); if(!n) break;
        for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            a[i][j]=read();
        memset(b,0,sizeof(b));
        Dfs(1,1,a[1][1]); flag=false;
        for(ans=0;;ans++){
            Search(0);
            if(flag) {printf("%d\n",ans); break;}
        }
    }
    return 0;
}

Codevs1288 埃及分数

详见紫书P207。

Uva11212 编辑书稿

详见紫书P208。

Comments

comments powered by Disqus