APTX Blog

A Moe Blog Set By APTX

#C/C++#DFS深度优先搜索/剪枝/迭代加深搜索/A*搜索

搜索问题

搜索是玄学,最稳定的应用是写暴力 or 骗分。

一个搜索问题的基本模型有以下几个要素:

  • 状态:表示当前搜索到的局面。一般用x,y,z表示。一开始我们处于初始状态。
  • 代价:表示对当前状态好坏的一个衡量。一般用f(x),g(x)表示,指代状态代价。
  • 扩展(转移):表示从当前状态出发,我们再进行一步搜索的过程。在扩展过程结束以后,我们可能会转移到若干个新的状态。一步转移也会带来代价,称为转移代价。

搜索问题可以分为两类:可行性搜索与最优性搜索。

  • 在可行性搜索问题当中,目标是搜索到某些给定状态,问是否能够从初始状态经过若干步扩展到达给定状态。
  • 在最优性搜索问题中,我们不仅要回答是否能够从初始状态扩展到给定状态,还要能够回答从初始状态到达给定状态的最优方法。这里最优方法定义为转移代价与状态代价之和最优(最大或最小)。

剪枝

剪枝是搜索算法当中一种非常强大的加速技巧。大家都知道搜索算法的时间效率是非常低的(指数级),所以需要各种各样的优化来加快速度,一般的加速方法就是剪枝。事实上,我们使用搜索算法的时候不太关心它的确切时间复杂度,如果你发现你的算法太慢了该怎么办呢?

就用剪枝。

可行性剪枝

如果这个状态是不合法的,就直接舍弃这个状态,否则就会出现不可预测的错误。例如数组越界,数据类型溢出,运行时错误。

最优性剪枝

最强大的剪枝手段,适用于求最优解的问题。

以求最小值的问题为例,假设现在已经搜索到了某个状态x,x可以扩展出的状态有y1,y2,y3,而且现在已知的最小值是m。那么我们对从状态y1,y2,y3出发能够找到的解的下界做一个估计,如果发现这个下界都不小于m,那么说明从这个状态出发一定不能搜索到最优解,所以我们根本不需要搜索这个状态和它的所有后继状态

如何对这个下界做估计?

使用已有代价。有点像可行性剪枝……

使用已有代价+状态估价。有点像A*……

这个方法的学名叫做分支限界,别问我为什么大家都叫它最优性剪枝。

迭代加深搜索

在一般的搜索问题当中,搜索路径的长度是有限的。例如在最多因子数这个题目里面,我们一旦发现当前搜索到的质数乘积超过了R就可以不再继续搜索了。在更之前的N皇后问题当中,我们一旦不能继续放皇后了就可以退出了。

但是有一些问题,在这些问题当中搜索路径的长度可以是无限的(接下来大家会看到例子)。于是如果我们使用dfs算法就可能会陷入无限循环当中。这个时候一般有两种选择:

用bfs……用迭代加深搜索。

所谓迭代加深搜索,就是限制dfs算法当中的搜索深度。搜索深度的意思是从初始状态出发经过的转移数量。我们一般将搜索深度定义为一个变量maxd,然后从1开始枚举maxd,上界可以是一个很大的数字(你觉得会超时的数字……)。

一旦maxd确定以后,dfs的搜索路径长度最多只能是maxd,所以dfs不会陷入无限循环当中。

A*搜索

A*搜索算法的学名叫做启发式搜索,又称为有信息搜索(Informed Search),它是利用问题拥有的启发信息来引导搜索,达到减少搜索范围、降低问题复杂度的目的,这种利用启发信息的搜索过程称为启发式搜索。

说人话就是在dfs或者bfs的时候,我们确定的搜索顺序是比较随意的(从大到小或者从小到大)。如果我们对每个当前的搜索状态进行一个估价,表示从这个状态出发能够搜到最优解的可能性,那么我们每次从估价最大的状态开始进行扩展,就可能以更快的速度搜到最优解。

一般使用g(S)表示状态S已经花费的代价,h(S)表示对状态S的估价,在代价最小的搜索问题当中,我们选择g(S)+h(S)最小的一个状态S来进行扩展。

使用来维护。

Meet in the Middle

搜索算法当中一个技巧,又称为双向搜索。

将搜索的状态空间分成两半,先搜索前一半,将结果记录下来。然后搜索后一半,利用之前记录的结果,就可以完成整个的搜索。

显著降低时间复杂度:如果搜索前一半和后一半的时间分别是A和B,那么朴素的搜索需要的时间是A*B,而双向搜索耗时是A+B,代价是需要更大的空间来记录前一半搜索的信息。

典型的以空间换时间。

以上By:北京大学图灵班 胡家琛

PPT以后放在我的Onedrive上

点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注