双向宽度优先搜索
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$ 是走到当前状态的步数
orz,迭代加深搜索在哪里找啊
求更新,佬
求更新,佬
$\Huge\color{LightCyan}{洛谷吗?}$
对
牛啊兄弟
牛