MyException - 我的异常网
当前位置:我的异常网» 数据库 » 八数码有关问题:bfs及dbfs版本详解

八数码有关问题:bfs及dbfs版本详解

www.MyException.Cn  网友分享于:2013-08-22  浏览:0次
八数码问题:bfs及dbfs版本详解

hdu1043多组数据

poj1077单组数据

1、对于空间的处理

按常规方法,标志位序列vis的大小需要876543210位,空间非常大,所以我们考虑将int转化为char 类型储存(32位机int占4字节 char 占1字节)。

又考虑,如果转化为九进制,876543210(9)-->381367044(10),进一步优化空间。

可是像111111111,333333333这样的房间,根本没有被用到,却仍然占用空间,我们考虑对空间进行进一步优化。

情况个数共为9!个-->362880将标志位序列优化至此。

将每一种情况%mod以达到哈希目的,通过邻接表实现。

2、判断解的存在

设f(x)(x!=0)代表x之前小于x的数的个数,g(x)代表f(x)之和,g(x)的奇偶性决定了问题是否有解

若两状态奇偶性不同,则无法相互转化。

a、单向广搜版本

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
#include<queue>
#define maxn 362882
#define ll long long
using namespace std;
int dx[4] = {-1,1,0,0};
int dy[4] = {0,0,-1,1};
char s[10] = {'u','d','l','r'};
int tcnt,hcnt;
const int mod = 23333;
int head[mod+5];
  
struct Table
{
    int pos,dir,pre;
    char a[10];
}tb[maxn];
 
struct Hash
{
    char a[10];
    int next;
}htb[maxn];
 
queue<int>q;
 
int build_table(int dir,int pos,int last)
{
    ++tcnt;
    tb[tcnt].pos =  pos;
    tb[tcnt].dir = dir;
    strcpy(tb[tcnt].a,tb[last].a);
    tb[tcnt].pre = last;
    return tcnt;
}
 
inline bool check(char *a)//判断是否达到目标状态
{
    for(int i = 0; i < 8; i ++)
        if(a[i] != '0' + i + 1) return false;
    return true;
}
 
inline bool valid(int x,int y)//判断出界
{
    return 0 <= x && x <= 2 && 0 <= y && y <= 2;
}
 
inline bool ok(int a,int b)//防止回到父亲位置
{
    if(a > b) swap(a,b);
    if(a == 0 && b == 1) return false;
    if(a == 2 && b == 3) return false;
    return true;
}
 
void output(int id)//递归输出答案
{
    if(!id) return;
    output(tb[id].pre);
    putchar(s[tb[id].dir]);
}
 
int change(char *a)//储存哈希值
{
    int ret(0);
    for(int i = 0; i < 8; i ++)
        ret =  (ret<<1) + (ret <<3) + a[i]-'0';
    return ret%mod;
}
 
bool available(int id)//判断解的存在性
{
    char *a = tb[id].a;
    int tot(0);
    for(int i = 1; i < 9; i ++){
        if(a[i] == '0')continue;
        for(int j = 0 ; j < i ; j ++)
            if(a[j] < a[i]&& a[j]!='0') tot ++;
    }
    return (tot%2)^1;
}
 
void hash_insert(char *a)//添加状态
{
    int hash = change(a);hcnt ++;
    strcpy(htb[hcnt].a,a);
    htb[hcnt].next = head[hash];
    head[hash] = hcnt;
}
 
bool issame(char *a,char *b)判断是否出现过,用于防止转圈之类的重复路径
{
    for(int i = 0 ; i < 9; i ++)
        if(a[i]!=b[i]) return false;
    return true;
}
 
bool query(char *a)//通过邻接表实现查询
{
    int hash = change(a);
    for(int i = head[hash]; i ; i = htb[i].next)
        if(issame(a,htb[i].a)) return true;
    return false;
}
 
 
bool bfs()
{
    int pos,x,y,las,k,xx,yy,tar,idd;
    hash_insert(tb[0].a);
    q.push(0);
    while(!q.empty())
    {
        int id = q.front();q.pop();
        Table *p = &tb[id];//指针写法
        if(check(p->a))//判断是否达到目标
        {
            output(id);
            return true;
        }
        pos = p -> pos;x = pos/3,y = pos%3;
        las = p -> dir;
        for(k = 0; k < 4; k ++)
        {
            xx = x + dx[k];
            yy = y + dy[k];
            tar = xx*3 + yy;
            if(!valid(xx,yy)|| !ok(las,k)) continue;//ok函数是防止走回父亲
             
            swap(p->a[pos],p->a[tar]);//改变0的位置
             
            if(query(p->a)){
                swap(p->a[pos],p->a[tar]);
                continue;
            }//该情况出现过
             
            idd = build_table(k,tar,id);
            hash_insert(p->a);//将新状态存入hash表中
            q.push(idd);
            swap(p->a[pos],p->a[tar]);
        }
    }
    return false;
}
 
int main()
{
    char str[3];tb[0].dir = 4;
    for(int i = 0; i < 9; i ++){
        scanf("%s",str);
        if(str[0] == 'x'){
            tb[0].pos = i;
            tb[0].a[i] = '0';
            continue;
        }
        tb[0].a[i] = str[0];
    }
    if( !available(0) || !bfs()) printf("unsolvable");
}

有很多地方可以压缩减小代码量,在下面的dbfs中操作

b、dbfs版本

dbfs需要修改的地方是query,当找到相同状态时我们返回当前位置序号,如果该序号在另一个队列中那么目标状态被找到,output答案

现在解释output部分

从初始状态走向目标状态时,当我们找到交点,需要递归回去从起点输出路径;从目标状态走向起始状态时,当交点出现,直接按顺序输出路径即可。

同样的,交点的走向在两种不同情况时是相反的。

(和bfs一样的部分我就不解释了)

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
#include<queue>
#define maxn 362882
#define ll long long
using namespace std;
int dx[4] = {-1,1,0,0};
int dy[4] = {0,0,-1,1};
char s1[10] = {'u','d','l','r'};
char s2[10] = {'d','u','r','l'};
int hcnt;
const int mod = 23333;
int head[mod+5];
int vis[2][maxn],inque[2][maxn];

struct Hash//将hash和table写在一起(其实原本就可以写在一起可是我不想改bfs的代码了...)
{
    char a[10];
    int pos,dir,pre;
    int next;
}htb[maxn];

queue<int>q[2];

inline bool valid(int x,int y)
{
    return 0 <= x && x <= 2 && 0 <= y && y <= 2;
}

inline bool ok(int a,int b)
{
    if(a > b) swap(a,b);
    if(a == 0 && b == 1) return false;
    if(a == 2 && b == 3) return false;
    return true;
}

void output1(int id)//q[0]递归反向输出答案
{
    if(id <= 1) return;
    output1(htb[id].pre);
    putchar(s1[htb[id].dir]);
}
void output2(int id)//q[1]正向输出
{
    if(id <= 2) return;
    putchar(s2[htb[id].dir]);
    output2(htb[id].pre);
}

int change(char *a)
{
    int ret(0);
    for(int i = 0; i < 8; i ++)
        ret =  (ret<<1) + (ret <<3) + a[i]-'0';
    return ret%mod;
}

bool available(int id)
{
    char *a = htb[id].a;
    int tot(0);
    for(int i = 1; i < 9; i ++){
        if(a[i] == '0')continue;
        for(int j = 0 ; j < i ; j ++)
            if(a[j] < a[i]&& a[j]!='0') tot ++;
    }
    return (tot%2)^1;
}

int hash_insert(int dir,int pos,int id)//因为一个hash值对应一个hcnt,所以将bfs中的table和hash 合起来写
{
    int hash = change(htb[id].a);hcnt ++;
    strcpy(htb[hcnt].a,htb[id].a);
    htb[hcnt].dir = dir;
    htb[hcnt].pos = pos;
    htb[hcnt].pre = id;
    htb[hcnt].next = head[hash];
    head[hash] = hcnt;
    return hcnt;
}

bool issame(char *a,char *b)
{
    for(int i = 0 ; i < 9; i ++)
        if(a[i]!=b[i]) return false;
    return true;
}

int query(char *a)//bfs中check与query的作用在dbfs中一致,所以用query代替check
{
    int hash = change(a);
    for(int i = head[hash]; i ; i = htb[i].next)
        if(issame(a,htb[i].a)) return i;//返回序号数
    return 0;
}

bool bfs()
{
    int pos,x,y,las,k,xx,yy,tar,idd;hcnt = 2;
    q[0].push(1);
    q[1].push(2);
    inque[0][1]=1;
    inque[1][2]=1;
    while(!q[0].empty()&&!q[1].empty())
    {
        int num=q[0].size()>q[1].size() ;
        int id = q[num].front();q[num].pop();
        Hash *p = &htb[id];
        pos = p -> pos;x = pos/3,y = pos%3;
        las = p -> dir;
        
        for(k = 0; k < 4; k ++)
        {
            xx = x + dx[k];
            yy = y + dy[k];
            tar = xx*3 + yy;
            if(!valid(xx,yy)|| !ok(las,k)) continue;
            
            swap(p->a[pos],p->a[tar]);
            int ba;
            if(ba=query(p->a))
            {
                if(vis[num^1][ba]||inque[num^1][ba])//判断状态是否在另一队中出现
                {
                    int flg=0;
                    if(num) 
                    {
                        swap(id,ba);
                        flg=1;//判断交点走向
                    }
                    output1(id);
                    if(!flg)putchar(s1[k]);
                    else putchar(s2[k]);
                    output2(ba);
                    return true;
                }
                swap(p->a[pos],p->a[tar]);
                continue;
            }
            idd = hash_insert(k,tar,id);
            inque[num][idd]=1;
            q[num].push(idd);
            swap(p->a[pos],p->a[tar]);
        }
        vis[num][id]=1;
        inque[num][id]=0;
    }
    int num=q[0].empty();
    while(!q[num].empty())
    {
        int id = q[num].front();q[num].pop();
        Hash *p = &htb[id];
        pos = p -> pos;x = pos/3,y = pos%3;
        las = p -> dir;
        for(k = 0; k < 4; k ++)
        {
            xx = x + dx[k];
            yy = y + dy[k];
            tar = xx*3 + yy;
            if(!valid(xx,yy)|| !ok(las,k)) continue;
            swap(p->a[pos],p->a[tar]);
            int ba;
            if(ba=query(p->a))
            {
                if(vis[num^1][ba]||inque[num^1][ba])
                {
                    int flg=0;
                    if(num) swap(id,ba),flg=1;
                    output1(id);
                    if(!flg)putchar(s1[k]);
                    else putchar(s2[k]);
                    output2(ba);
                    return true;
                }
                swap(p->a[pos],p->a[tar]);
                continue;
            }
            idd = hash_insert(k,tar,id);
            q[num].push(idd);
            inque[num][idd]=1;
            swap(p->a[pos],p->a[tar]);
        }
        vis[num][id]=1;
        inque[num][id]=0;
    }
    return false;
}
void init()
{
    for(int i = 1 ; i <= hcnt ; ++i)
    {
        vis[0][i]=vis[1][i]=0;
        inque[0][i]=inque[1][i]=0;
    }
    for(int i = 1 ; i <= mod+1 ; ++i)
        head[i]=0;
    while(!q[0].empty()) q[0].pop();
    while(!q[1].empty()) q[1].pop();
}
int main()
{
    char str[3];
    while(scanf("%s",str)!=EOF)
    {
        init();

    htb[1].dir = 4;
    htb[2].dir = 4;

     htb[1].a[0]=str[0]; 

    if(str[0] == 'x'){

            htb[1].pos = 0;
            htb[1].a[0] = '0';
            }
        for(int i = 1; i < 9; i ++){
        scanf("%s",str);
        if(str[0] == 'x'){
            htb[1].pos = i;
            htb[1].a[i] = '0';
            continue;
        }
        htb[1].a[i] = str[0];
        }
        int hash = change(htb[1].a);
        head[hash] = 1;
        for(int i = 0 ; i < 8 ; ++i)
            htb[2].a[i]=i+1+'0';
        htb[2].a[8]='0';
        hash=change(htb[2].a);
        head[hash]=2;
        htb[2].pos=8;if( !available(1) || !bfs()) printf("unsolvable");
        printf("\n");
    }
}

 

接下来比较dbfs与bfs的时间及空间

bfs 时间157ms 空间7836K

dbfs 时间 0ms 空间1352K

虽然程序的时间及空间会受评测机性能的影响,但是dbfs的优越性还是显而易见的。

此篇是针对上一篇dbfs入门的加深,接下来几天会更新八数码问题的idA*版本,以解决15数码问题。

(16!超过long long 范围 ,所以针对15数码,只能使用idA*算法,仍然用dbfs的话会牵扯高精度,反而增加代码的难度了)

文章评论

60个开发者不容错过的免费资源库
60个开发者不容错过的免费资源库
 程序员的样子
程序员的样子
看13位CEO、创始人和高管如何提高工作效率
看13位CEO、创始人和高管如何提高工作效率
编程语言是女人
编程语言是女人
代码女神横空出世
代码女神横空出世
当下全球最炙手可热的八位少年创业者
当下全球最炙手可热的八位少年创业者
一个程序员的时间管理
一个程序员的时间管理
中美印日四国程序员比较
中美印日四国程序员比较
Java程序员必看电影
Java程序员必看电影
不懂技术不要对懂技术的人说这很容易实现
不懂技术不要对懂技术的人说这很容易实现
程序员的鄙视链
程序员的鄙视链
旅行,写作,编程
旅行,写作,编程
Java 与 .NET 的平台发展之争
Java 与 .NET 的平台发展之争
程序猿的崛起——Growth Hacker
程序猿的崛起——Growth Hacker
程序员最害怕的5件事 你中招了吗?
程序员最害怕的5件事 你中招了吗?
初级 vs 高级开发者 哪个性价比更高?
初级 vs 高级开发者 哪个性价比更高?
写给自己也写给你 自己到底该何去何从
写给自己也写给你 自己到底该何去何从
总结2014中国互联网十大段子
总结2014中国互联网十大段子
为什么程序员都是夜猫子
为什么程序员都是夜猫子
2013年中国软件开发者薪资调查报告
2013年中国软件开发者薪资调查报告
10个调试和排错的小建议
10个调试和排错的小建议
亲爱的项目经理,我恨你
亲爱的项目经理,我恨你
科技史上最臭名昭著的13大罪犯
科技史上最臭名昭著的13大罪犯
为啥Android手机总会越用越慢?
为啥Android手机总会越用越慢?
程序员都该阅读的书
程序员都该阅读的书
要嫁就嫁程序猿—钱多话少死的早
要嫁就嫁程序猿—钱多话少死的早
Web开发人员为什么越来越懒了?
Web开发人员为什么越来越懒了?
程序员周末都喜欢做什么?
程序员周末都喜欢做什么?
程序员和编码员之间的区别
程序员和编码员之间的区别
程序员必看的十大电影
程序员必看的十大电影
那些争议最大的编程观点
那些争议最大的编程观点
程序员应该关注的一些事儿
程序员应该关注的一些事儿
程序员的一天:一寸光阴一寸金
程序员的一天:一寸光阴一寸金
做程序猿的老婆应该注意的一些事情
做程序猿的老婆应该注意的一些事情
那些性感的让人尖叫的程序员
那些性感的让人尖叫的程序员
我的丈夫是个程序员
我的丈夫是个程序员
我是如何打败拖延症的
我是如何打败拖延症的
10个帮程序员减压放松的网站
10个帮程序员减压放松的网站
Web开发者需具备的8个好习惯
Web开发者需具备的8个好习惯
程序员眼里IE浏览器是什么样的
程序员眼里IE浏览器是什么样的
5款最佳正则表达式编辑调试器
5款最佳正则表达式编辑调试器
“肮脏的”IT工作排行榜
“肮脏的”IT工作排行榜
我跳槽是因为他们的显示器更大
我跳槽是因为他们的显示器更大
十大编程算法助程序员走上高手之路
十大编程算法助程序员走上高手之路
老美怎么看待阿里赴美上市
老美怎么看待阿里赴美上市
鲜为人知的编程真相
鲜为人知的编程真相
2013年美国开发者薪资调查报告
2013年美国开发者薪资调查报告
什么才是优秀的用户界面设计
什么才是优秀的用户界面设计
聊聊HTTPS和SSL/TLS协议
聊聊HTTPS和SSL/TLS协议
软件开发程序错误异常ExceptionCopyright © 2009-2015 MyException 版权所有