双端BFS之重塑（未完成）
2026-01-11 17:15:22
发布于：上海
あっという間に 電車が前を吹きすさぶ 勝手に目に留まる 少し夜の匂いもして 踊り踊り踊る ネズミも踊る
——————————————————————————————————————
感谢Xylophone同学，TA开启了我对双端BFS的新探索。
——————————————————————————————————————
由于某些原因，打算再写一次双端BFS。
并且在写的过程中发现自己对双端BFS不够了解。
所以我找了一些教程。
分别在洛谷，OIWIKI，博客园。
所以这其实类似于一篇学习笔记吧。
同时在整理完之后，我会插入两题双端BFS的题目。
应该两道都是绿题。黑白棋 字串变换
那是我的作业。我会写出我的思考过程。
和最终的解决方案。
有想去的可以看看。觉得有问题的可以指出。
如果是对于本文章的讲解有原则上的问题，我会立刻（指我看到之后）进行修改。
对于文章有其他的建议，我会留到寒假进行一并修改。
因为我的身体不太好（续航时间短）+要期末考了。
感谢理解和尊重。
—————————————————————————————————————
在本篇笔记中，我会说明以下几个问题的答案：（所有答案在本片末尾，中途会提及）
Q1：为什么双向广搜的时间复杂度和空间复杂度可以得到优化？
Q2：如何使用双端BFS对图进行遍历？
Q3：如何使用双端BFS搜索状态？
Q4：双端BFS的应用？
Q5：如何在双端BFS是存储状态？
—————————————————————————————————————
双向广搜，就是初始节点和目标节点同时拓展的一种搜索。
相比广度优先搜索，其时间复杂度和空间复杂度都会得到优化。
这是它的定义。
它的普遍模板解答，可以看这张图片（截取自博客园Hoppz)或者看我前期自己写的这个
这里已经解答了Q1和Q2，双端BFS的精髓就是优先对元素少的那个队列进行BFS。
因而，其会得到相对于普通BFS的优化。（如果不理解可以看[这个]
(https://www.acgo.cn/discuss/study/67561)，更详细）
然后我们来探究Q3。（我没找到相关的题解和说明帖子啥的）
提出假设：假设搜索状态和对图进行遍历其实是差不多的。
也就是，初始状态和目标状态同时拓展。
等等。那岂不是和图遍历是一样的？
猜测它们可能是一样的外壳，不过目的是不一样的。
欸，好像可以把“对图进行遍历”归为“搜索状态”的一类。
好像可以。
看T1：字串变换
题目大意：
已知有两个字串A，B及一组字串变换的规则（至多6个）
形如： A1 -> B1
规则含义:在A中的字串A1可以变换为B1。
询问是否能在<=10步之中将A变成B。是，则输出最少的变换步数。
不是则输出No answer.
思路似乎是比较明朗的，将A作为起始状态，将B作为目标状态。
然后进行双端BFS。
这里空空如也
有帮助，赞一个