专栏首页ACM算法日常搜索专题3 | 八数码 HDU - 1043

搜索专题3 | 八数码 HDU - 1043

本搜索专题会参考vjudge上的《kuangbin带你飞》系列题目,前面2篇是基础题,后面会慢慢复杂起来!加油!

前两篇展示了DFS和BFS的基本应用,可能大家觉得比较简单,回顾一下,DFS一般用于求所有解的情况,BFS用于求最短路类型的问题,DFS缺点是容易迷失自己,优点是不用维护队列,省空间。BFS缺点是需要队列在处理寻路这样的问题时比较耗费空间,优点是循序渐进的容易找最优解。

本篇接着看BFS的启发式搜索A*算法。

虽然BFS搜索路径已经不错了,但是每次都是按部就班的从队列里先进先出的取元素,这样有点太古板了。于是在某些情况下可以采用优先队列来替代普通队列,优先队列这个BFS搜索本来打算写一篇文章的,现在直接放在A*里面理解吧。

优先队列是指在搜索解时,选取一条最优路径,比如当前代价最小的路径。然而这样有一个缺点,那就是当前代价小并不代表最终这条路径是最小的。

理想情况下是知道当前消耗和接下来需要消耗的,然而未知路径的消耗只有先知才知道

如下图:

于是有人便想到了,虽然不能够确定未知路径的代价H,但是我们可以大概估算一下代价H啊,小学老师就说过,估算是一项非常重要的能力,A*算法里面估算就是核心了(虽然看上去会感觉不靠谱)。

嗯,大概思路就有了,A*算法 = 优先队列 + 未知估值

那么未知估值具体要怎么做呢?

这又是一个类似于DP算法要怎么写呢的问题

只有针对特定的题目,我们才知道要怎么写,适合意会不好言传,还是看题领悟吧。

题目很简单,其实重点是看懂代码。代码其实也很清晰,重点是花点耐心看完~

The 15-puzzle has been around for over 100 years; even if you don't know it by that name, you've seen it. It is constructed with 15 sliding tiles, each with a number from 1 to 15 on it, and all packed into a 4 by 4 frame with one tile missing. Let's call the missing tile 'x'; the object of the puzzle is to arrange the tiles so that they are ordered as:

15谜题已经有100多年历史了。即使不知其名,肯定也见过。它由15个滑动块组成,每个滑动块由数字1到15标记,并且被放在4x4大小的框框里面,缺失一个块。缺失的称之为x。谜题的目标就是将这些块有序的整理起来。如下图:

1 2 3 4

5 6 7 8

9 10 11 12

13 14 15 x

where the only legal operation is to exchange 'x' with one of the tiles with which it shares an edge. As an example, the following sequence of moves solves a slightly scrambled puzzle:

唯一合法的操作是交换x与相邻的块。

1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4

5 6 7 8 5 6 7 8 5 6 7 8 5 6 7 8

9 x 10 12 9 10 x 12 9 10 11 12 9 10 11 12

13 14 11 15 13 14 11 15 13 14 x 15 13 14 15 x

r-> d-> r->

The letters in the previous row indicate which neighbor of the 'x' tile is swapped with the 'x' tile at each step; legal values are 'r','l','u' and 'd', for right, left, up, and down, respectively.

每一步操作称之为rlud,分别是右移/左移/上移/下移。

Not all puzzles can be solved; in 1870, a man named Sam Loyd was famous for distributing an unsolvable version of the puzzle, and frustrating many people. In fact, all you have to do to make a regular puzzle into an unsolvable one is to swap two tiles (not counting the missing 'x' tile, of course).

并不是所有的谜题都能被解决,

In this problem, you will write a program for solving the less well-known 8-puzzle, composed of tiles on a three by three arrangement.

在这个问题上,你需要写一个8谜题,解决3x3上的问题。

Input

You will receive, several descriptions of configuration of the 8 puzzle. One description is just a list of the tiles in their initial positions, with the rows listed from top to bottom, and the tiles listed from left to right within a row, where the tiles are represented by numbers 1 to 8, plus 'x'. For example, this puzzle

输入会成为一行。

1 2 3

x 4 6

7 5 8

is described by this list:

1 2 3 x 4 6 7 5 8

Output

You will print to standard output either the word ``unsolvable'', if the puzzle has no solution, or a string consisting entirely of the letters 'r', 'l', 'u' and 'd' that describes a series of moves that produce a solution. The string should include no spaces and start at the beginning of the line. Do not print a blank line between cases.

如果没有解,输出unsolvable,否则输出路径。

Sample Input

2 3 4 1 5 x 7 6 8

Sample Output

ullddrurdllurdruldr

解题思路:

八数码问题,就是小时候玩的那个小玩具。

重点可以看看A*的大概流程:

1:初始化,将起始位置放入队列

priority_queue<state_t> q; q.push(a);

2:4个方向前进,计算每个方向的估值,这里的估值是计算曼哈顿距离,也就是x/y轴的差值绝对值之和。当前步数作为当前消耗的代价G。放入队列。

3:取队列元素,重复2过程。

解题代码:

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>


using namespace std;
const int maxn = 4e5 + 10;


int ha[9] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320};
/*这个ha[9]数组是用来计算hash值的,这个数组中的值分别是0!,1!,2!,3!,4!,5!,6!,7!,8!*/
int dir[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
char d[10] = "udlr";
int vis[maxn];  //判重


struct state_t {
    int f[3][3];  //当前这个转态每个位置上的值
    int x, y;
    int g, h;
    int hash_num;


    // 估值为h+g
    bool operator<(const state_t a) const {
        return h + g > a.h + a.g;  //优先队列保证出队的是估值函数值较小的。
    }
};


struct path {
    int pre;
    char ch;
} p[maxn];  //用于记录路径


// 评估函数,获得评估值
// 计算1~8的数字回到原点需要的步数作为评估值,必定小于实际操作数
int get_h(state_t a) {
    int i, j, ans = 0;
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            if (a.f[i][j]) {
                // 曼哈顿距离
                ans += abs(i - (a.f[i][j] - 1) / 3) + abs(j - (a.f[i][j] - 1) % 3);  
            }
        }
    }
    return ans;
}


//康托展开
int get_hash(state_t e) {
    int a[9], i, j, k = 0, ans = 0;
    for (i = 0; i < 3; i++)  //将数据排成一排,便于计算
    {
        for (j = 0; j < 3; j++)
            a[k++] = e.f[i][j];
    }
    for (i = 0; i < 9; i++)  //计算hash值
    {
        k = 0;
        for (j = 0; j < i; j++)
            if (a[j] > a[i])
                k++;
        ans += ha[i] * k;
    }
    return ans;
}


void print(int x) {
    if (p[x].pre == -1)
        return;
    print(p[x].pre);
    printf("%c", p[x].ch);
}


void AStar(state_t a) {
    memset(vis, 0, sizeof(vis));
    int end_ans, xx, yy, k;
    state_t vw, vn;


    // 最终状态的值
    for (int i = 0; i < 9; i++) {
        vw.f[i / 3][i % 3] = (i + 1) % 9;  //目标转态时各个位置的值
    }


    end_ans = get_hash(vw);  //目标转态时的hash值
    a.hash_num = get_hash(a);


    a.g = 0;         //初始状态到状态a的代价函数
    a.h = get_h(a);  //从状态a到目标状态的最佳路径的估计代价


    vis[a.hash_num] = 1;
    p[a.hash_num].pre = -1;


    if (a.hash_num == end_ans) {
        printf("\n");
        return;
    }


    priority_queue<state_t> q;
    q.push(a);


    while (!q.empty()) {
        a = q.top(), q.pop();


        for (int i = 0; i < 4; i++) {
            xx = a.x + dir[i][0];
            yy = a.y + dir[i][1];
            if (xx < 0 || yy < 0 || xx >= 3 || yy >= 3)
                continue;


            vw = a;
            swap(vw.f[a.x][a.y], vw.f[xx][yy]);  //交换双方的值


            k = get_hash(vw);
            if (vis[k])
                continue;

            vis[k] = 1;
            vw.hash_num = k;
            // 当前x的位置
            vw.x = xx;
            vw.y = yy;
            // 更新g,增加1
            vw.g++;
            // 评估距离
            vw.h = get_h(vw);


            p[k].pre = a.hash_num;
            p[k].ch = d[i];

            //如果当前状态的hash值等于目标状态的hash值,表示已经到达目标状态
            if (k == end_ans)  
            {
                print(k);
                printf("\n");
                return;
            }


            q.push(vw);
        }
    }
}


int main() {
    char a[30];


    while (gets(a)) {
        int i, j, k, n;
        // 输入初始状态
        state_t e;
        n = strlen(a);


        for (i = 0, j = 0; i < n; i++) {
            if (a[i] == ' ')
                continue;
            if (a[i] == 'x') {
                // x设置为0
                e.f[j / 3][j % 3] = 0;
                e.x = j / 3;
                e.y = j % 3;
            } else
                e.f[j / 3][j % 3] = a[i] - '0';
            j++;
        }


        // 这边涉及到一个逆序数问题,如果开始状态的逆序数为奇数,那么这个状态只能到达逆序数为奇数的转态,同理偶数逆序数的状态也只能到达逆序数为偶数的状态
        // 逆序数:前面的数大于后面的数
        for (i = 0, k = 0; i < 9; i++) {
            if (e.f[i / 3][i % 3] == 0)
                continue;
            for (j = 0; j < i; j++) {
                if (e.f[j / 3][j % 3] == 0)
                    continue;
                if (e.f[j / 3][j % 3] > e.f[i / 3][i % 3])
                    k++;
            }
        }
        // 求逆序数
        if (k & 1)
            printf("unsolvable\n");
        else
            AStar(e);
    }
    return 0;
}

有时候用一个庞大的队列来处理状态超级多搜索问题,内存会有点紧张,于是,为了更好的处理这种问题,又由A*的启发式特性,IDA*算法才横空出世。

本文分享自微信公众号 - ACM算法日常(acm-clan),作者:dansen

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-08-20

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 翻转瓷砖Fliptile(开关反转)- POJ 3279

    Farmer John knows that an intellectually satisfied cow is a happy cow who will g...

    ACM算法日常
  • CodeForces 982F:The Meeting Place Cannot Be Changed(有向图)

    Petr is a detective in Braginsk. Somebody stole a huge amount of money from a ba...

    ACM算法日常
  • POJ-3641:Pseudoprime numbers(快速幂)

    Fermat's theorem states that for any prime number p and for any integer a > 1, a...

    ACM算法日常
  • 翻转瓷砖Fliptile(开关反转)- POJ 3279

    Farmer John knows that an intellectually satisfied cow is a happy cow who will g...

    ACM算法日常
  • 实习杂记(22):仿照VideoView+MediaPlayerController做视频

    主要是抽取出来,有些方法是hide,有些类是  internal层的,无法使用,所以需要自己去想办法弄,

    wust小吴
  • LintCode 交错正负数题目分析代码

    样例 给出数组[-1, -2, -3, 4, 5, 6],重新排序之后,变成[-1, 5, -2, 4, -3, 6]或者其他任何满足要求的答案

    desperate633
  • POJ-3641:Pseudoprime numbers(快速幂)

    Fermat's theorem states that for any prime number p and for any integer a > 1, a...

    ACM算法日常
  • Android打造不一样的新手引导页面(一)

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/gdutxiaoxu/article/details/...

    用户2965908
  • 仿qq最新侧滑菜单

    为了后续对这个项目进行优化,比如透明度动画、背景图的位移动画,以及性能上的优化。 我把这个项目上传到github上面,请大家随时关注。 github地址 htt...

    xiangzhihong
  • Greedy & Violent

    1 2 3//坐标缩小后就可以更方便的选择 double pos = (double)i / n * (n + m);//原来雕像的位置 ans += f...

    radaren

扫码关注云+社区

领取腾讯云代金券