The Fourth Dimension Space

枯叶北风寒,忽然年以残,念往昔,语默心酸。二十光阴无一物,韶光贱,寐难安; 不畏形影单,道途阻且慢,哪曲折,如渡飞湍。斩浪劈波酬壮志,同把酒,共言欢! -如梦令

暑假专题训练一 搜索::POJ 1077 八数码 ——初识A*算法

特来YM+学习A*算法,A*果然快啊,在pku上曾经写过一个BFS,300MS,去航电直优化的空间接TLE.用A*算法北大16MS,航电750MS,效率很高啊。当然我的A*写得还不是特别好,航电上有16MS AC那道题的,看来这个A*还有优化的空间。
A*采用启发式搜索的思维方式很值得借鉴!F=G+H
#include<iostream>
#include
<cmath>
#include
<algorithm>
#include
<cstdio>
using namespace std;

int const maxn=365000;//总状态数不超过362880
char s[12],t[12];

//FOR DIRECTION
int num[9]={2,3,2,3,4,3,2,3,2};//指示每个位置可以移动的方向数
int dirn[9][4]=
{
    
{1,2},
    
{1,2,3},
    
{2,3},
    
{0,1,2},
    
{0,1,2,3},
    
{0,2,3},
    
{0,1},
    
{0,1,3},
    
{0,3}
}
;
//end
int xy[9][2]={{0,0},{1,0},{2,0},{0,-1},{1,-1},{2,-1},{0,-2},{1,-2},{2,-2}};//存每个位置的坐标
int fa[maxn],cz[maxn];//cz是回溯时记录方向
int factor[8]={1,2,6,24,120,720,5040,40320};
int dist[10][10];//存第i个位置到第j个位置要走的步数
int v[maxn];//标记是否在OPEN表中
int goalcode;
int initzeropos;

struct node
{
    
int pos,g,h,code;//code is short for hashcode
    char s[12];
    
bool operator<(node o)
    
{
        
return (g+h) < (o.g+o.h);
    }

}
;


#define ele node//可以修改数据类型
struct MinHeap
{
    ele 
*h;//heap数组
    int Csize;//CurrentSize现在的容量
    int Msize;//最大容量
    void Down(int s,int e)//第s号位置的元素进行下渗,数组中最大的下标到e
    {
        
int i=s,j=2*i+1;
        ele t
=h[i];
        
while(j<=e)
        
{
            
if(j<e&&h[j+1]<h[j])
                j
++;
            
if(t<h[j])
                
break;
            
else 
            
{
                h[i]
=h[j];i=j;j=2*j+1;
            }

        }

        h[i]
=t;
    }

    
void Up(int s)//start,上渗函数
    {

        
int j=s,i=(j-1)/2;
        ele t
=h[j];
        
while(j)
        
{
            
if(h[i]<t) break;
            
else
            
{   
                h[j]
=h[i];j=i;i=(i-1)>>1;
            }

        }

        h[j]
=t;
    }

    MinHeap(
int n){Msize=n;h=new ele[Msize];Csize=0;}//构造函数
    bool Insert(const ele &x)
    
{
        
if(Csize==Msize)
            
return false;
        h[Csize]
=x;
        Up(Csize);
        Csize
++;
        
return true;
    }

    ele RemoveMin()
    
{
        
//v[h[0].code]=false;//记录
        ele x=h[0];
        h[
0]=h[Csize-1];
        Csize
--;
        Down(
0,Csize-1);
        
return x;
    }

    ele GetMin()
{return h[0];}
}
;
MinHeap H(maxn);

int GetDist(int s,int t)//计算两个位置之间的最小步数
{
    
int dx=abs(xy[s][0]-xy[t][0]);
    
int dy=abs(xy[s][1]-xy[t][1]);
    
return dx+dy;
}

int cal(char s[])  //计算全排列的哈希值(hashcode)
{
    
int i,j,cnt,res=0;
    
for(i=1;i<9;i++)
    
{
        cnt
=0;
        
for(j=0;j<i;j++)
            
if(s[j]>s[i])cnt++;
        cnt
*=factor[i-1];
        res
+=cnt;
    }

    
return res;
}



int estimate(char str[])
{
    
int res=0,i,des;
    
for(i=0;i<9;i++)
    
{
        
if(str[i]!='0')
        
{
            des
=str[i]-'0'-1;
            res
+=dist[i][des];
        }

    }

    
return res;
}


bool check(char s[])//检测目标状态是否可达
{
    
int i,j,cnt,res=0;
    
for(i=1;i<9;i++)
    
{
        cnt
=0;
        
for(j=0;j<i;j++)
            
if(s[j]>s[i])cnt++;
        res
+=cnt;
    }

    
for(i=0;i<9;i++)
    
{
        
if(s[i]=='0')
        
{
            res
+=dist[i][8];
            
break;
        }

    }

    
if((res%2)==0)
        
return true;
    
else return false;
}



int change(char s[],int op,int pos) //互换位置,返回换后的空格位置
{
    
int end;
    
if(op==0)end=pos-3;
    
else if(op==1)end=pos+1;
    
else if(op==2)end=pos+3;
    
else if(op==3)end=pos-1;
    
char t=s[pos];
    s[pos]
=s[end];
    s[end]
=t;
    
return end;//返回调整后空格的位置
}


void Astar(char s[])
{
    H.Csize
=0;//清空操作
    node t;
    t.pos
=initzeropos;
    t.g
=0;
    t.h
=estimate(s);
    t.code
=cal(s);
    strcpy(t.s,s);
    v[t.code]
=true;
    cz[t.code]
=0;
    fa[t.code]
=-1;
    H.Insert(t);
    
//以上为初始化
    while(H.Csize>0)
    
{
        node tt
=H.RemoveMin();
        
if(tt.code==goalcode)     
        
{
            
int ans[1000];
            
int k=0,fp;
            fp
=tt.code;
            
while(fp!=t.code)
            
{
                ans[k
++]=cz[fp];
                fp
=fa[fp];
            }

            
for(int i=k-1;i>=0;i--)
            
{
                
if(ans[i]==0)printf("u");
                
else if(ans[i]==1)printf("r");
                
else if(ans[i]==2)printf("d");
                
else if(ans[i]==3)printf("l");
            }

            printf(
"\n");
            
return;
        }

        
int len=num[tt.pos];
        
for(int i=0;i<len;i++)
        
{
            node x
=tt;
            x.pos
=change(x.s,dirn[tt.pos][i],x.pos);
            x.code
=cal(x.s);
            x.g
++;
            x.h
=estimate(x.s);        
            
if(!v[x.code])
            
{
                v[x.code]
=true;
                fa[x.code]
=tt.code;
                cz[x.code]
=dirn[tt.pos][i];
                H.Insert(x);
            }


        }

    }


}





int main()
{
    
int i,j;
    strcpy(t,
"123456780");
    goalcode
=cal(t);


    
for(i=0;i<9;i++)
        
for(j=0;j<9;j++)dist[i][j]=GetDist(i,j);

    
char str[50];
    
while(gets(str))
    
{
        
int len=strlen(str),pos=0;
        memset(v,
0,sizeof(v));
        
for(i=0;i<len;i++)
        
{
            
if(str[i]=='x')//空格部分用0代替
            {
                initzeropos
=pos;
                s[pos
++]='0';
            }

            
else if(str[i]>='1'&&str[i]<='8')s[pos++]=str[i];
        }

        s[
9]='\0';
        
if(!check(s))printf("unsolvable\n");
        
else Astar(s);
    }

    
return 0;
}



代码参考了:http://www.cppblog.com/longzxr/archive/2010/07/05/92978.html#119349

posted on 2010-07-10 15:14 abilitytao 阅读(2183) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理