在上一篇文章中（《洛谷刷题记——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*实现等，也请大家多多关照啦！