搜索问题
搜索是玄学，最稳定的应用是写暴力 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上
文章评论