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

在上一篇文章中(《洛谷刷题记——P1379 八数码难题(朴素广搜实现)》),我们介绍了康托展开判重,以及如何使用朴素的BFS去解决八数码问题,但朴素的广搜效率较差,也就是勉强过了。今天,我们将使用一种优化版的广搜来解决八数码问题。

题目描述

见“P1379 八数码难题”。

知识链接

双向广搜

双向广搜,顾名思义,是从两个方向开始搜索,适用于知道搜索起点和搜索目标的情况下,能够显著减少搜索次数。具体方法为:从起点和终点分别开始搜索,当搜索路径出现重合时就代表搜索结束,因为如果从终点能够反向搜索到某个点,那么从这个点也能够正向搜索到终点,并且都是最短路径。双向广搜我们可以用这个模型来理解:从起点和终点分别抛一颗石子,激起层层涟漪扩散,当涟漪出现交点时就代表起点能通过这个点到达终点。使用双向广搜能够显著降低复杂度,至于如何证明······这我也不太会啊 |(*′口`)

那么如何实现双向广搜呢?有两种方法:一种是使用两个队列,另一种是使用一个队列,但通过标记区分是通过起点入队还是通过终点入队。第一种方法实现起来比第二种方法复杂一些,但可以通过优化搜索出较为平衡的搜索树(注:和平衡二叉搜索树没有一点关系),常数上来讲比第二种方法更优。

解题思路

与朴素BFS类似,都是通过搜索后康托展开判重。只不过这次康托展开函数承担了一个不一样的任务:算出康托展开后还要判断是从起点入队还是从终点入队,并算出路径和。

至于如何判断是否搜索到,我们可以对判重数组做这样一个改变:当从起点搜到就将这个点+1,从终点搜到就将这个点+2,如果这个点等于3,就代表出现重合,直接返回即可。

本实现采用知识链接中第二种方法实现双向广搜,因为本题并不需要过于复杂的实现方法。测试结果:朴素BFS花费3.42s,双向广搜花费369ms(0.37s),快了整整3秒多,这可是难以想象的优化速度!!!

代码展示

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

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

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

using namespace std;

// 当前八数码状态,相比朴素BFS的pair多了一个是从起点入队还是从终点入队的判断
struct State {
  array<int, 10> nums; // 当前数码
  int step; // 步数
  bool is_from_head; // true是从起点入队,false是从终点入队
  State() {
    is_from_head = false;
    step = 0;
    nums.fill(-1);
  }
  State(const array<int, 10>& a, int b, bool c) {
    nums = a;
    step = b;
    is_from_head = c;
  }
};

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<array<int, 5>, 362885> kIsVis; // kIsVis[i][0]是记录从起点访问、从终点访问还是都访问了,kIsVis[i][1]是记录走到这个点所用的步数
queue<State> kQueue;

int Dbfs(void); // 双向广搜
int Cantor(const State& /* str */); // 传进的参数变为了当前八数码状态,返回值变为算出的康托值
inline bool IsValid(int /* dx */, int /* dy */);

int main(void) {
  kGoal.fill(-1);

  // 初始化路径记录数组
  for (auto iter = kIsVis.begin(); iter != kIsVis.end(); ++iter)
    (*iter)[0] = (*iter)[1] = 0;

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

  if (kGoal == kStart)
    puts("0");
  else
    printf("%d\n", Dbfs());

  return 0;
}

int Dbfs(void) {
  State head(kStart, 0, true), new_node;
  Cantor(head); // 初始化起点
  kQueue.push(head); // 起点入队
  head = State(kGoal, 0, false);
  Cantor(head); // 初始化终点
  kQueue.push(head); // 终点入队

  while (!kQueue.empty()) {
    bool is_find_zero(false);
    int zero_pos(-1);

    head = kQueue.front();
    kQueue.pop();

    for (int i = 0; i < 9 && !is_find_zero; ++i) {
      if (0 == head.nums[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]),
          new_zero_y(zero_y + kPosMove[i][1]);
      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.nums[zero_pos], new_node.nums[new_zero_pos]);
        ++new_node.step;
        int cantor_num(Cantor(new_node)); // 获取当前点康托值

        if (3 == kIsVis[cantor_num][0]) // 出现重合
          return kIsVis[cantor_num][1]; // 直接返回路径
      }
    }
  }

  return -1;
}

int Cantor(const State& str) {
  int res(0);

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

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

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

  // 注:这里仅仅是对kIsVis数组进行处理,判断是否达到目标的代码在Dbfs函数中
  if (str.is_from_head) { // 是从起点来的
    if (kIsVis[res][0] != 1) { // 如果之前没从起点访问过
      kQueue.push(str); // 入队
      kIsVis[res][0] += 1; // +1
      kIsVis[res][1] += str.step; // 加上从起点搜索到这里的路径
    }
  } else { // 是从终点来的
    if (kIsVis[res][0] != 2) { // 如果之前没从终点访问过
      kQueue.push(str); // 入队
      kIsVis[res][0] += 2; // +2
      kIsVis[res][1] += str.step; // 加上从终点搜索到这里的路径
    }
  }

  return res;
}

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号