搜索进阶

· · 算法·理论

迭代加深

迭代加深，顾名思义，是一层一层向下搜，类似于BFS

BFS有什么缺点，那就是占空间，但在某些时候比DFS快

毕竟，如果DFS找错分支，而那个分支没有答案并且很深，就会耗费大量的时间

于是，我们想着，可以自小到大枚举深度进行DFS，这样既能保证，这些节点会一层一层搜到，加快寻找答案的速度，又不占空间

双向搜索

双向搜索是一种常见策略，一般用于优化枚举子集问题，主要适用于有主要初始状态与最终状态的时候

使用双向搜索可以避免层数过深时分支数量大规模增长的情况

方法如下，可以先搜索前半段，在搜索后半段，再对后半段产生的答案去匹配前半段产生最终答案

A*

它适用于一些最优解问题或$k$优解问题 它可以用优先队列将保证从终点第$x$次得到的一定是第$x$优解 我们设一个函数$f(x)$是预估的价值总和，让优先队列里的状态以$f(x)$排序 设已算的价值为$h(x)$，那我们需要预估剩下的价值 $g(x) f(x)=h(x)+g(x) 我们需要使 $f(x) \le ans

到终点时，f(x)=ans，所以答案是能正确的

剩下的和广搜是一样的

IDA*

A*$的算法关键是在设计估价函数，将$BFS$与估价函数结合形成了$A*$，那么如果我们将$DFS+迭代加深$和估价函数相结合就可以得到$IDA*