双向搜索之DFS篇

update: 12.9.2020 写成介绍部分，未写题解。 ------------ DFS不用说了吧，就是普通的深搜。 这里介绍一种深搜的优化搜索，叫作**双向搜索**。 思路： **从起点和终点出发，开始搜索**。容易发现，只要从两边各搜索一半的状态，就会得到答案。 怎么判断退出呢？ 当两个搜索路径有交会，也就是**搜到重复的点**，就可以退出搜索了。 因为有重复的点，就可以说明把所有状态都搜过了。 这样时间会快很多，主要是因为**搜索树分支减少了很多**。 介绍完毕。 练习题及题解：