andyli

题解 洛谷 P1379 【八数码难题】
八数码问题其实就是图上的最短路问题,图的“节点”就是9个格子中的滑块编号(从上到下,从左到右把它们放到一个包含9个...
扫描右侧二维码阅读全文
04
2018/05

题解 洛谷 P1379 【八数码难题】

八数码问题其实就是图上的最短路问题,图的“节点”就是9个格子中的滑块编号(从上到下,从左到右把它们放到一个包含9个元素的数组中)。无权图上的最短路问题可以用BFS求解。


树的BFS不需要判重,因为根本不会重复;但对于图来说,如果不判重,时间和空间都将产生极大的浪费。 楼下的判重方式建议不要学习,因为用一个九维数组一共有9^9=387420489项,太多了,数组可能开不下。实际结点数并没有这么多,0~8的排列总共只有9!=362880个。这样的用法存在大量的浪费…——数组中有很多项都没有被用到,但却占据了空间。


第一种办法是把排列变成整数,这样只开一个一维数组就可以了。(效率还行)。但是适用范围不大:如果隐式图的总结点数非常大,编码也会很大,数组还是开不下。


第二种办法是使用哈希(hash)技术(简单地说,是把结点变成整数,但不必一一对应)。(比赛中最常用)


第三种方法是利用STL集合。(代码最好写),但是效率比较慢,建议在时间紧迫或对效率要求不太高的情况下使用,或者仅把它作为“跳板”——先写一个STL的程序,确保主算法正确,然后把set替换成自己写的哈希表。


这里利用第二种方法,因为比赛中比较常用,而且执行效率很高。代码如下:

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

using State = int[9]; // 定义“状态”类型
const int maxstate = 1000000;
State st[maxstate], goal = {1, 2, 3, 8, 0, 4, 7, 6, 5}; // 状态数组。所有状态都保存在这里
int dist[maxstate]; // 距离数组

const int dx[] = {-1, 1, 0, 0};
const int dy[] = {0, 0, -1, 1};

namespace myhash // STL有许多函数名是hash的函数,为了保险最好用名称空间(换个名字也可以),个人习惯
{
    const int hashsize = 1000003;
    int head[hashsize], next[maxstate];

    void init_lookup_table()
    {
        memset(head, 0, sizeof(head));
    }

    int hash(State& s)
    {
        int v = 0;
        // 把9个数字组合成9位数
        for (int i = 0; i < 9; i++)
            v = v * 10 + s[i];
        return v % hashsize;
        // 确保hash值是不超过hash表的大小的非负整数
    }

    int try_to_insert(int s)
    {
        int h = hash(st[s]);
        int u = head[h]; // 从表头开始查找链表
        while (u)
        {
            // 找到了,插入失败
            if (!memcmp(st[u], st[s], sizeof(st[s])))
                return 0;
            u = next[u]; // 顺着链表接着找
        }
        next[s] = head[h]; // 插入到链表中
        head[h] = s;
        return 1;
    }
}

// BFS,返回目标状态在st数组下标
int bfs()
{
    myhash::init_lookup_table(); // 初始化查找表
    int front = 1, rear = 2; // 不使用下标0,因为0被看做“不存在”
    while (front < rear)
    {
        State& s = st[front]; // 用引用简化代码
        if (!memcmp(goal, s, sizeof(s)))
            return front; // 找到目标状态,成功返回
        int z;
        for (z = 0; z < 9; z++)
            if (!s[z])
                break; // 找“0”的位置
        // 获取行列编号(0~2) 
        int x = z / 3;
        int y = z % 3;
        for (int d = 0; d < 4; d++)
        {
            int newx = x + dx[d];
            int newy = y + dy[d];
            int newz = newx * 3 + newy;
            if (newx >= 0 && newx < 3 && newy >= 0 && newy < 3)
            { // 如果移动合法
                State& t = st[rear]; // 扩展新结点
                memcpy(&t, &s, sizeof(s));
                t[newz] = s[z];
                t[z] = s[newz];
                // 更新新结点的距离值
                dist[rear] = dist[front] + 1;
                // 如果成功插入查找表,修改队尾指针
                if (myhash::try_to_insert(rear))
                    rear++;
            }
        }
        front++;
    }
    return 0; // 失败
}

int main()
{
    char tmp;
    for (int i = 0; i < 9; i++)
    {
        cin >> tmp; // 起始状态
        st[1][i] = tmp - '0';
    }
    int ans = bfs(); // 返回目标状态的下标
    if (ans > 0)
        cout << dist[ans] << endl;
    else
        cout << -1 << endl;
    return 0;
}

提示:某些特定的STL实现还有hash_set,它正是基于前面的哈希表,但它并不是标准C++的一部分,因此不是所有情况下都可用。

Last modification:June 25th, 2019 at 11:02 am
If you think my article is useful to you, please feel free to appreciate

Leave a Comment