双向宽度优先搜索

P1379 八数码难题

在 $3×3$ 的棋盘上，摆有八个棋子，每个棋子上标有 $1$ 至 $8$ 的某一数字。棋盘中留有一个空格，空格用 $0$ 来表示。空格周围的棋子可以移到空格中。要求解的问题是：给出一种初始布局（初始状态）和目标布局（为了使题目简单,设目标状态为 123804765），找到一种最少步骤的移动方法，实现从初始布局到目标布局的转变。

尴尬的单向 $\rm{BFS}$

双向宽度优先搜索 DBFS

• DBFS 算法从两个方向以宽度优先的顺序同时扩展，一个是从起始节点开始扩展，另一个是从目标节点扩展，直到一个扩展队列中出现另一个队列中已经扩展的节点，也就相当于两个扩展方向出现了交点，那么可以认为我们找到了一条路径
• 假设 $1$ 个节点能扩展出 $n$ 个节点，单向搜索要 $m$ 层才能找到答案，那么扩展出来的节点数目就是 $\frac{1-n^m}{1-n}$
• 双向宽搜，同样是一共扩展 $m$ 层，假定两边各扩展出 $\frac{m}{2}$ 层，则总节点数目就是 $2 \* \frac{1-\frac{n^m}{2}}{1-n}$

DBFS 代码框架

初始化两个队列 $q[0]$ 和 $q[1]$，起点和终点分别加入两个队列中。

初始化两个 map，$m[0]$ 和 $m[1]$，$key$ 是字符串表示的状态，$step$ 是走到当前状态的步数