人生第一个 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;
}
分类: 文章

XZYQvQ

炒鸡辣鸡的制杖蒟蒻一枚QvQ

5 条评论

mayday · 2022年9月12日 9:25 上午

remina 大佬,您的双向广搜好像有点问题,丢洛谷上只有 94 会 wa 两个点

mayday · 2022年9月12日 8:32 上午

能否提供一下此题题干和输入格式

enceladus · 2018年10月16日 3:10 下午

QAQ,不会 A * ,只会 IDA *

B_Z_B_Y · 2018年10月15日 8:11 下午

您的 A* 的代码 少了 一个特判 if(_sta==_end)cout<<0,exit(0); QvQ 还是加一下吧

    XZYQvQ · 2018年10月16日 8:20 上午

    已添加,谢谢提醒

回复 XZYQvQ 取消回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注