双向广度搜索/折半搜索 发表于 2022-03-25 | 分类于 算法学习 | 顾名思义，便是从目标状态与起始状态两个方向进行搜索，其实就是“关于dfs剪枝优化”中提到的二分优化（个人觉得用双向广度搜索更贴切hhh），将搜索的深度/2，而搜索深度所导致的时间复杂度是指数级的，故可大大优化时间复杂度 用八数码问题举例，用bfs搜索预处理出到达各个状态的最少步数并存储起来（此处运用到hash，不再赘述），然后再从目标状态反过来进行bfs，判断当前状态是否与之前预处理出的状态一致（依然是用hash判断），若一致，则当前步数+预处理步数则为最少步数