【题解】八数码难题之 A* 算法

人生第一个 A * 算法～好激动……

八数码难题……又称八数码水题，首先要理解一些东西：

状态可以转化成整数，比如状态：

1 2 3
4 5 6
7 8 0

可以转化成：123456780 这个整数

看上去有 9×9 种不同状态，实际上只有 9! 种（即 9×8×7×6×5×4×3×2×1）种状态，哈希表大小开成一个大素数即可，每次用这个大素数去对当前的状态（整数）取余获得哈希表的键值

移动一个数码到 0 这个位置可以理解成 0 这个数码移动到四周的数码的位置 我先用广搜水过，速度大约是 20ms 左右：

#include <iostream>
#include <queue>
#include <cstdlib>
#define hash(x) (x%14233333)
using namespace std;
const int _end=123804765;
int _sta;
bool h_tab[14233333];
queue<int> que,tque;
int move(int key,char c)
{
    int p0=1,kb=key,_map[3][3],x0,y0;
    while(1){if(kb%10==0)break;p0++,kb/=10;}
    kb=key,x0=(9-p0)/3,y0=(9-p0)%3;
    for(int i=2;i>=0;i--)for(int j=2;j>=0;j--)_map[i][j]=kb%10,kb/=10;
    switch(c)
    {
        case 'l':if(y0==0)return key;swap(_map[x0][y0],_map[x0][y0-1]);break;
        case 'r':if(y0==2)return key;swap(_map[x0][y0],_map[x0][y0+1]);break;
        case 'u':if(x0==0)return key;swap(_map[x0][y0],_map[x0-1][y0]);break;
        case 'd':if(x0==2)return key;swap(_map[x0][y0],_map[x0+1][y0]);break;
        default:break;
    }
    kb=0;
    for(int i=0;i<3;i++)for(int j=0;j<3;j++)kb=kb*10+_map[i][j];
    return kb;
}
int main()
{
    cin>>_sta;
    if(_sta==_end)cout<<0,exit(0);
    que.push(_sta),tque.push(0),h_tab[hash(_sta)]=1;
    while(!que.empty())
    {
        int _new=move(que.front(),'u');
        if(_new==_end)cout<<tque.front()+1,exit(0);
        if(!h_tab[hash(_new)])h_tab[hash(_new)]=1,que.push(_new),tque.push(tque.front()+1);
        _new=move(que.front(),'d');
        if(_new==_end)cout<<tque.front()+1,exit(0);
        if(!h_tab[hash(_new)])h_tab[hash(_new)]=1,que.push(_new),tque.push(tque.front()+1);
        _new=move(que.front(),'l');
        if(_new==_end)cout<<tque.front()+1,exit(0);
        if(!h_tab[hash(_new)])h_tab[hash(_new)]=1,que.push(_new),tque.push(tque.front()+1);
        _new=move(que.front(),'r');
        if(_new==_end)cout<<tque.front()+1,exit(0);
        if(!h_tab[hash(_new)])h_tab[hash(_new)]=1,que.push(_new),tque.push(tque.front()+1);
        que.pop(),tque.pop();
    }
    return 0;
}

又用了双向广搜试了试，速度大概是 10ms 左右：

#include <iostream>
#include <queue>
#include <cstdlib>
#define hash(x) (x%14233333)
using namespace std;
const int _end=123804765;
int _sta;
unsigned short th_tab[2][14233333];
bool h_tab[2][14233333];
queue<int> que[2];
int move(int key,char c)
{
    int p0=1,kb=key,_map[3][3],x0,y0;
    while(1){if(kb%10==0)break;p0++,kb/=10;}
    kb=key,x0=(9-p0)/3,y0=(9-p0)%3;
    for(int i=2;i>=0;i--)for(int j=2;j>=0;j--)_map[i][j]=kb%10,kb/=10;
    switch(c)
    {
        case 'l':if(y0==0)return key;swap(_map[x0][y0],_map[x0][y0-1]);break;
        case 'r':if(y0==2)return key;swap(_map[x0][y0],_map[x0][y0+1]);break;
        case 'u':if(x0==0)return key;swap(_map[x0][y0],_map[x0-1][y0]);break;
        case 'd':if(x0==2)return key;swap(_map[x0][y0],_map[x0+1][y0]);break;
        default:break;
    }
    kb=0;
    for(int i=0;i<3;i++)for(int j=0;j<3;j++)kb=kb*10+_map[i][j];
    return kb;
}
int main()
{
    cin>>_sta;
    if(_sta==_end)cout<<0,exit(0);
    que[0].push(_sta),que[1].push(_end),h_tab[0][hash(_sta)]=h_tab[1][hash(_end)]=1,th_tab[0][hash(_sta)]=th_tab[1][hash(_end)]=0;
    while(!que[0].empty()||!que[1].empty())
    {
        int _new;
        if(!que[0].empty())
        {
            _new=move(que[0].front(),'u');
            if(!h_tab[0][hash(_new)])
            {
                h_tab[0][hash(_new)]=1,que[0].push(_new),th_tab[0][hash(_new)]=th_tab[0][hash(que[0].front())]+1;
                if(h_tab[1][hash(_new)])cout<<th_tab[0][hash(_new)]+th_tab[1][hash(_new)],exit(0);
            }
            _new=move(que[0].front(),'d');
            if(!h_tab[0][hash(_new)])
            {
                h_tab[0][hash(_new)]=1,que[0].push(_new),th_tab[0][hash(_new)]=th_tab[0][hash(que[0].front())]+1;
                if(h_tab[1][hash(_new)])cout<<th_tab[0][hash(_new)]+th_tab[1][hash(_new)],exit(0);
            }
            _new=move(que[0].front(),'l');
            if(!h_tab[0][hash(_new)])
            {
                h_tab[0][hash(_new)]=1,que[0].push(_new),th_tab[0][hash(_new)]=th_tab[0][hash(que[0].front())]+1;
                if(h_tab[1][hash(_new)])cout<<th_tab[0][hash(_new)]+th_tab[1][hash(_new)],exit(0);
            }
            _new=move(que[0].front(),'r');
            if(!h_tab[0][hash(_new)])
            {
                h_tab[0][hash(_new)]=1,que[0].push(_new),th_tab[0][hash(_new)]=th_tab[0][hash(que[0].front())]+1;
                if(h_tab[1][hash(_new)])cout<<th_tab[0][hash(_new)]+th_tab[1][hash(_new)],exit(0);
            }
            que[0].pop();
        }
        if(!que[1].empty())
        {
            _new=move(que[1].front(),'u');
            if(!h_tab[1][hash(_new)])
            {
                h_tab[1][hash(_new)]=1,que[1].push(_new),th_tab[1][hash(_new)]=th_tab[1][hash(que[1].front())]+1;
                if(h_tab[0][hash(_new)])cout<<th_tab[1][hash(_new)]+th_tab[0][hash(_new)],exit(0);
            }
            _new=move(que[1].front(),'d');
            if(!h_tab[1][hash(_new)])
            {
                h_tab[1][hash(_new)]=1,que[1].push(_new),th_tab[1][hash(_new)]=th_tab[1][hash(que[1].front())]+1;
                if(h_tab[0][hash(_new)])cout<<th_tab[1][hash(_new)]+th_tab[0][hash(_new)],exit(0);
            }
            _new=move(que[1].front(),'l');
            if(!h_tab[1][hash(_new)])
            {
                h_tab[1][hash(_new)]=1,que[1].push(_new),th_tab[1][hash(_new)]=th_tab[1][hash(que[1].front())]+1;
                if(h_tab[0][hash(_new)])cout<<th_tab[1][hash(_new)]+th_tab[0][hash(_new)],exit(0);
            }
            _new=move(que[1].front(),'r');
            if(!h_tab[1][hash(_new)])
            {
                h_tab[1][hash(_new)]=1,que[1].push(_new),th_tab[1][hash(_new)]=th_tab[1][hash(que[1].front())]+1;
                if(h_tab[0][hash(_new)])cout<<th_tab[1][hash(_new)]+th_tab[0][hash(_new)],exit(0);
            }
            que[1].pop();
        }
    }
    return 0;
}

然后我一条路走到黑，研究起了 A 算法…… A 算法我现在研究也不透彻……

也是一种广搜，它通过一个估值函数，估算当前扩展出的新状态到目标状态的代价，再选中代价最小的新状态扩展，直到扩展到目标状态……

非常快，速度大概是 0~1ms 先转发一个写 A*算法很不错的博客：

http://www.cnblogs.com/yanlingyin/archive/2012/01/15/2322640.html 再贴个代码：

#include <iostream>
#include <deque>
#include <algorithm>
#include <cstdlib>
#define _abs(x) (x>=0?x:-x)//绝对值函数
#define h_size 14233333//哈希表大小
#define hash(x) (x%h_size)
using namespace std;
typedef pair<int,int> pii;
const int _end=123804765,_enp[2][9]={{1,0,0,0,1,2,2,2,1},{1,0,1,2,2,2,1,0,0}};//end 为目标状态,enp[0][i] 表示目标状态中数字 i 所在的行,enp[1][i] 表示数字 i 所在的列
int _sta;//开始状态
bool _clo[h_size];//a*算法的 close 表
deque<pii> _ol;//a*算法的 open 表（使用双端队列）
int h(int key)//估值函数，使用曼哈顿距离估值
{
    int _map[3][3],_kp[2][9],sum=0;
    for(int i=2;i>=0;i--)for(int j=2;j>=0;j--)_kp[0][key%10]=i,_kp[1][key%10]=j,key/=10;
    for(int i=0;i<9;i++)sum+=abs(_kp[0][i]-_enp[0][i])+abs(_kp[1][i]-_enp[1][i]);
    return sum;
}
int move(int key,char _ctr)//移动数字 0 函数,u 表示向上，d 表示向下,l 表示向左,r 表示向右
{
    int _kb=key,_map[3][3],i0,j0;
    for(int i=2;i>=0;i--)for(int j=2;j>=0;j--){_map[i][j]=_kb%10,_kb/=10;if(_map[i][j]==0)i0=i,j0=j;}
    switch(_ctr)//如果无法扩展（即到达边界）就返回移动前的值
    {
        case 'u':if(i0==0)return key;swap(_map[i0][j0],_map[i0-1][j0]);break;
        case 'd':if(i0==2)return key;swap(_map[i0][j0],_map[i0+1][j0]);break;
        case 'l':if(j0==0)return key;swap(_map[i0][j0],_map[i0][j0-1]);break;
        case 'r':if(j0==2)return key;swap(_map[i0][j0],_map[i0][j0+1]);break;
    }
    for(int i=0;i<3;i++)for(int j=0;j<3;j++)_kb=_kb*10+_map[i][j];
    return _kb;
}
bool cmp(pii a,pii b){return a.second<b.second;}//二分查找比较函数
void work(pii _nex)//处理新状态
{
    if(_nex.first==_end)cout<<_nex.second-h(_nex.first),exit(0);//发现正解，直接输出并结束程序
    if(!_clo[hash(_nex.first)])_ol.insert(lower_bound(_ol.begin(),_ol.end(),_nex,cmp),_nex);//二分查找插入新状态
}
int main()
{
    cin>>_sta;
    if(_sta==_end)cout<<0,exit(0);
    _ol.push_back(make_pair(_sta,h(_sta)));//把开始状态加入到 open 表中
    while(!_ol.empty())//处理 open 表
    {
        pii _now=_ol.front();
        _ol.pop_front(),_clo[hash(_now.first)]=1;//把当前 open 表中的最优状态取出并加入到 close 表中
        int _nex=move(_now.first,'u');//扩展新状态
        work(make_pair(_nex,_now.second-h(_now.first)+h(_nex)+1)),_nex=move(_now.first,'d');
        work(make_pair(_nex,_now.second-h(_now.first)+h(_nex)+1)),_nex=move(_now.first,'l');
        work(make_pair(_nex,_now.second-h(_now.first)+h(_nex)+1)),_nex=move(_now.first,'r');
        work(make_pair(_nex,_now.second-h(_now.first)+h(_nex)+1));
    }
    return 0;
}