关于
联系
Oi大佬们
keyboard_arrow_down
本站已运行
载入天数...载入时分秒...
Woshiluo's Notebook
Woshiluo
2018年2月2日
Caioj 1046: 8数码问题

广搜入门题,经典八数码

题库中已经说的很清楚了,这题是用广搜(又称宽搜),那么,何为宽搜,它与深搜区别何在?

1.深搜与广搜


这两种搜索的全名分别是:

深搜——深度优先搜索
广搜——广度优先搜索

其英文缩写分别是 dfs 与 bfs ,虽然只差一个字母,不过却有所不同

深搜的特点是短而难想
广搜的特点是长且难写

我们就根据八数码这道题,说一下深搜与广搜的区别,先看看下面这张图:

                  0
           /   |    |   \
        上 下 左  右(最优解)
    /  |    |    \
上 下 左 右(次右解)

如果你是用深搜他会这么寻找: 0->上->上->返回上一层->下->返回上一层->左->返回上一层->右(次优解)->返回上一层->下-》……最优解
然而广搜是这个样子的 0->上->下->左->右(最优解)->进入下一层-》上-》下-》左-》右-》次优解

以上应该就可以很明白的看出,深搜是将一步搜索到底再回头,广搜是在每一层搜索,所以广搜第一个搜到的一定是最优解。 不过为什么会右这样的差距,这就要看广搜的原理了

2.何为广搜


广度优先搜索

这不就是没解释

也就是说我们先把同一个步数的所有情况扩展完,然后进行判断,这也就是为什么第一个答案就是最优解

我们说这种情况,每一种情况搜完就不在需要了,而最近被搜到的应该放入最后,也就是说,先进先出——队列

那也就是说,这个东西需要我们开队列=.=,并且这种状况下,重复的可能性很高,关于如何这道题的剪枝方法,你可以看看这个

Caioj 1220:康托展开和康托展开的逆运算

3.题目&思路&部分代码


题目链接: http://caioj.cn/problem.php?id=1046

首先我们知道,这个题我们就是要模拟上下左右,也就是说我们读入初始与截止情况,将初始情况放入队列首,先来看看队列怎么写吧

struct FUCK{
    int a[4][4],x,y,deep;
}dl[400000],ed;

请忽略结构体名 dl[] 也就是队列

  • int a[][] 临时储存数码图
  • x,y 0 的坐标
  • deep 深度,也就是步数

ed 结尾情况

嗯对就是这样

然后就是判断重复,也就是上文所说的康托展开,我们吧每一中情况打成哈希表(坑爹玩意),然后就可以判断重复了,接下来就可以进行搜索

    while(l<=r){
        for(int i=0;i<4;i++){
            FUCK fir=dl[l];
            fir.x=dl[l].x+dx[i];
            fir.y=dl[l].y+dy[i];

            if(fir.x>=1&&fir.x<=3&&fir.y>=1&&fir.y<=3){
                int temp=fir.a[fir.x][fir.y];
                fir.a[fir.x][fir.y]=fir.a[dl[l].x][dl[l].y];
                fir.a[dl[l].x][dl[l].y]=temp;
                int temp_kt=zys(fir);
                fir.deep=dl[l].deep+1;

                if(!xd[temp_kt]){
                    xd[temp_kt]=true;
                    r++;
                    dl[r]=fir;
                    if(temp_kt==z){
                        printf("%d\n",fir.deep);
                        return 0;
                    }
                }

            }
        }
        l++;
    }

其中 l 是队列首指针, r 是队列尾指针, for 循环对应的就是 dx[] , dy[] 这两个增量然后我们就交换变量, 随意说这道题并不是特别的难 当然如果你不加判断重复就会 RE 了2333


textsms