洛谷刷题记——P1379 八数码难题(朴素广搜实现)

八数码问题是所有BFS问题中最经典的问题之一,而且非常考验做题人对广搜的综合理解,建议先去查阅学习广搜相关资料,再看看《洛谷刷题记——P1443 马的遍历》这篇文章,最后再来挑战这道难题。

题目描述

见“P1379 八数码难题”。

知识链接

康托展开

定义:康托展开是一个全排列到一个自然数的双射,常用于构建哈希表时的空间压缩。康托展开的实质是计算当前排列在所有由小到大全排列中的顺序,因此是可逆的。

看到这段话,你肯定一脸雾水(因为这段话直接引自百科,而众所周知写百科的人都不喜欢说人话),所以我们用人话来描述一下康托展开。

观察以下数对:(0, 012345678), (1, 012345687), (2, 012345768),······,(362879, 876543210),通过找规律我们可以看出这些数对中前一个数,是后一个数在{0, 1, 2, 3, 4, 5, 6, 7, 8}的全排列中的序数(不知道全排列的可以自行Google)。什么意思呢?我们将这九个数做全排列,可以看到012345678是第一个全排列,所以它对应的数就是0;而012345687是第二个全排列,所以它对应的数就是1······一直到876543210,可以看出它是所有全排列中最后一个,所以对应的编号为362879(共有362880个排列)。而这个“编号”,就是这个数的康托展开。

一句话:一个数的康托展开就是这个数在全排列中的排行。

至于全排列如何去算呢?我们有如下公式:

$$ X = \alpha_{n}(n – 1)! + \alpha_{n – 1}(n – 2)! + \cdots + \alpha_{1} \cdot 0! $$

其中,\( \alpha_{i} \) 为整数,并且 \( 0 \leq \alpha_{i} < i, 1 \leq i \leq n \)。

至于实现方面,就按照上面的公式来即可。只不过注意一点:在程序中动态算阶乘时间损耗过高,可以提前算好,然后保存进数组。下面以之前的9位数来做康拓展开的例子:

// 以9位数为例的康托展开

array<int, 10> kFactories = {1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880}; // 这个数组存的是公式里的那些阶乘结果

int Cantor(const array<int, 10>& str) { // str是传进去的数,输出这个数的康托展开
  int res(0); // 康托展开结果

  for (int i = 0; i < 9; ++i) {
    int cnt(0);

    for (int j = i + 1; j < 9; ++j) // 这层循环可以用线段树优化,但本题中n最大只有9,所以没有必要
      if (str[i] > str[j])
        ++cnt;

    res += cnt * kFactories[8 - i];
  }

  return res;
}

这样一算,发现是 \( O(n^2) \) 的复杂度,在这里大约只要循环81次左右,是很不错的方法。当然,第二层循环用线段树优化后能达到 \( O(n\log n) \) 的复杂度。不过,正如代码中所说的,在这个例子中没有必要。如果读者对此有兴趣的话,可以参见《排列数,康托展开及其线段树优化》这篇文章。

另:康拓展开有一个非常重要的特性,就是每一个展开只对应一个全排列,由此可以看出康托展开其实就是一种哈希函数。这是一个非常重要的特性,这也是我们为什么能用康托展开判重的原因。“康托逆展开”也是基于这样一个原理,有兴趣的读者可以自己查阅资料了解一下。

解题思路

本题是一个考察综合BFS能力的题,与其他题类似,这道题只需要分别将空位四个方向的数码拖拽到空位上来,再分别将这四种情况入队即可。注意:一定要判断四个方向的位置是否合法。

当然,如果你这么做了的话,是 \( O(n!n!) \) 的复杂度,显然会是超时的。怎么办呢?记忆化搜索!至于如果想要直接判重的话,最大的情况转化为一维数就是876543210,直接开一个876543210的数组肯定是会MLE的······等等,这个数怎么这么熟悉?对的,就是我们刚才的康托展开!刚才我们算过,九位数的康托展开最大只到362880,而这样一个数组显然是不会越界的。搜索的 \( O(n!) \) 的复杂度,加上康托展开 \( O(n^2) \) 的复杂度,总共加起来是 \( O(n!n^2) \),对付本题绰绰有余了。

于是总体思路就定了:首先将当前状态用康托展开设为已访问过,然后将可能的四种状态加入队列继续搜索,直到找到目标。

我的实现是用的数组来存的八数码状态,当然用字符串也可以存。还有,如果想要更好的复杂度可以使用STL的map判重,或使用上面所说的线段树实现康托展开判重。

代码展示

拒绝抄袭,共创和谐社会[机智]

#include <cstdio> // std::getchar, std::puts, std::printf

#include <array> // std::array
#include <queue> // std::queue
#include <utility> // std::pair
#include <algorithm> // std::swap

using namespace std;

array<int, 10> kStart = {1, 2, 3, 8, 0, 4, 7, 6, 5, -1}; // 初始状态,由题目给出
array<int, 10> kGoal; // 目标状态,由输入确定
array<array<int, 2>, 4> kPosMove = {0, 1, -1, 0, 0, -1, 1, 0}; // 上下左右四个方向的数码移动
array<int, 10> kFactories = {1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880}; // 康托展开用到的常数
array<bool, 362885> kIsVisited; // 判重
queue<pair<array<int, 10>, int> > kBfsQueue; // 队列

int Bfs(void); // 广搜
bool Cantor(const array<int, 10>& /* str */); // 康托展开,直接返回是否重复
inline bool IsValid(int /* dx */, int /* dy */); // 判断坐标是否越界

int main(void) {
  // 初始化
  kGoal.fill(-1);
  kIsVisited.fill(false);

  for (int i = 0; i < 9; ++i)
    kGoal[i] = getchar() - '0';

  if (kGoal == kStart) // 如果两种情况相等
    puts("0"); // 可以直接输出
  else
    printf("%d\n", Bfs()); // 输出广搜结果

  return 0;
}

int Bfs(void) {
  pair<array<int, 10>, int> head(make_pair(kStart, 0)), new_node; // 当前状态和新状态
  Cantor(head.first); // 将起始状态设为当前状态,用康托展开设为已访问
  kBfsQueue.push(head); // 起点入队

  while (!kBfsQueue.empty()) {
    bool is_find_zero(false); // 是否找到当前状态中的空位
    int zero_pos(-1); // 空位的位置

    head = kBfsQueue.front(); // 将队首取出,设为当前状态
    kBfsQueue.pop();

    for (int i = 0; i < 9 && !is_find_zero; ++i) { // 寻找当前状态的空位
      if (0 == head.first[i]) { // 找到了
        zero_pos = i;
        is_find_zero = true;
      }
    }

    int zero_x(zero_pos % 3), zero_y(zero_pos / 3); // 将一维位置化为二维

    for (int i = 0; i < 4; ++i) { // 列举上面的往下、左边的往右、下边的网上、右边的往左四种情况
      int new_zero_x(zero_x + kPosMove[i][0]), // 新空位的x值
          new_zero_y(zero_y + kPosMove[i][1]); // 新空位的y值
      int new_zero_pos(new_zero_x + new_zero_y * 3); // 将二维位置化为一维

      if (IsValid(new_zero_x, new_zero_y)) { // 坐标没有越界
        new_node = head;
        swap(new_node.first[zero_pos], new_node.first[new_zero_pos]); // 移动数码
        ++(new_node.second); // 步数加一

        if (new_node.first == kGoal) // 如果该状态等于目标状态
          return new_node.second; // 直接返回即可

        if (Cantor(new_node.first)) // 如果该状态没有搜索过
          kBfsQueue.push(new_node); // 加入队列
      }
    }
  }

  return -1;
}

// 康托展开,在“知识链接”中有讲解
bool Cantor(const array<int, 10>& str) {
  int res(0);

  for (int i = 0; i < 9; ++i) {
    int cnt(0);

    for (int j = i + 1; j < 9; ++j)
      if (str[i] > str[j])
        ++cnt;

    res += cnt * kFactories[8 - i];
  }

  if (!kIsVisited[res]) { // 这部分,直接判重返回
    kIsVisited[res] = true;
    return true;
  } else {
    return false;
  }
}

inline bool IsValid(int dx, int dy) {
  if (-1 < dx && dx < 3 && -1 < dy && dy < 3)
    return true;
  else
    return false;
}

写在最后

这道八数码问题是一道非常综合的广搜题目,做出了这道题后可以说是登堂入室了。但是这里只写出了朴素的BFS写法,还有很多的优化空间,如双向广搜、BFS A*、IDDFS和IDA*等,后面会一一讲解。

发表评论

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据

返回顶部
京ICP备15050995号