2019-09-05

分支限界 bfs 搜索的一般性论述

缘起

是时候总结一下搜索算法这个东西了. 基于写过的【1】、【2】、【3】、【4】这四篇文章以及【5】这篇讲解A*算法的好文.

分析

深搜没什么好说的. 本文主要将宽度类型的搜索. 而且只局限于求某个目标函数最小的场景. 注意，本文的函数有四种

真实代价函数
启发式函数
代价函数=真实代价函数+启发式函数
目标函数（即题目真正要我们求的最优标准是什么）

宽度类型的搜索主要是

启发式搜索（代价函数=真实代价函数+启发式函数构成。例如A*）
bfs（其实就是真实代价函数搜索步长, 而启发式函数为0，所以代价函数=搜索步长的启发式搜索）
分支限界（个人感觉，其实分支限界就是 剪枝+启发式搜索或者 剪枝+bfs, 分别对应优先队列式分支限界和队列式分支限界，但是队列式分支限界个人认为是错误的,原因在第二个问题的时候会讲到）

注意，上面三种算法的论述都没有涉及到代价目标函数，即并没有说代价函数和目标函数一致(所以可能两者高度一致，也可能略有偏差，甚至背道而驰~).

原先使用的时候都是混着用，感觉也是不明就里. 反正能A题也就不管了. 但是算法之间的细微差别以及实现没有提高到理论认识的角度. 本文要讲清楚下面几个问题，这几个问题能让我们明白宽度类型的搜索的本质，也是经过我谨慎思考得出的有用结果.

bfs一定求出的是目标函数最小吗?
启发式搜索一定求出的是目标函数最小吗?
分支限界如何剪枝的?
分支限界算法什么时候结束?
宽度类型的搜索曾经进过队的节点如果被重新发现的话需要再次进队吗（在【4】中叫做关闭列表,即在关闭节点列表中的节点要不要复活?）?

关于第一个问题

答: 未必

因为bfs的代价函数恒为搜索步长. 但是目标函数未必和搜索步长（即代价函数）是一致的. 所以bfs能保证搜出搜索步长最短的节点（这一点是可以保证的）但是这又有什么用呢? 和目标函数的价值观如果不符的话（或者你不能数学上证明相符），则bfs求出的解不能保证在目标函数下最优. 举个好简单的例子. A,B,C三个节点. A到C的距离是100，A->B是1，B->C是2，则求A到C的最短距离. 按照bfs, 搜索一步就能发现C. 然后得出最短距离是100的错误结论. 所以如果要用bfs求最短路径必须要求所有边长都是1. 这一点在【3】中也提及了.

关于第二个问题

答: 未必

其实和第一个问题的原因是一样的——也是目标函数和代价函数价值观未必相同. 但是和bfs不同的是，我们可以选择启发式搜索的代价函数和目标函数的价值观一致. 怎么选呢? 首先，真实代价函数和目标函数一致. 即真实代价函数就是按照目标函数来计算的. 以【4】中A*搜索为例子. 目标函数是路径的长度（注意, 水平或者垂直走一格的长度和斜着走一格的长度是不一样的）. 那么真实代价函数也就是目前为止走过的路径的长度. 这其实并不难理解. 关键是启发式函数该怎么选取才能使得启发式搜索第一个搜到的节点就一定是目标函数意义下的最优解. 答案是应该让启发式搜索函数<=从当前节点到达目的地节点（例如【4】中到达终点）的真实代价. 举个例子, 【4】中应该取出的启发式函数是当前处在的格点到终点的按照能走斜线走斜线（因为比横+竖的代价小），否则就横平竖直走这样的策略的真实代价. 还是不明白? 来来来, 看【4】中的图.

A处的启发式函数就是黄色路径的代价. B处的启发式函数就是蓝色路径的代价.

如果从这样的小根堆（代价函数越小优先级越高）中出堆元素到达了终点（例如上图中的终点）. 那么我们可以断言此时的节点（节点在【4】中就是一条路径）就是使得目标函数最小的节点. 因为出堆的这个节点（已经到达目的地）的代价函数就是目标函数. 而堆中其他节点都已经作弊了（用的启发式函数而不是真实代价函数）还没有出堆的节点优先级高. 所以出堆的到达终点的该堆顶元素就是最优解. 试想一下，如果还有更短路径存在的话，则它做起弊来岂不是更厉害? 使得代价函数的值更小? 那它早就出堆了. 而且一定更早作为已经到达终点的元素出堆，哪还轮得到当前堆顶元素呢?

于是我们就知道了

要想启发式搜索出堆的堆顶元素一定是最优解的话. 必须要保证对于任何节点的启发式函数的值<=它真实走完剩余路
的目标函数的值. 特别的, 启发式函数为0（注意，仅仅是启发函数为0，真实代价函数要和目标函数一致才行. 所以
这并不等同于bfs, 这一点, 网上很多人人云亦云都错了）. 而且启发式函数越逼近真实走完剩余路的代价函数, 则
启发式算法的效率就越高. 这一点也是极为符合直观的. 启发式函数为0的话,效率最低. 因为只看当下,而没有
高瞻远瞩.

所以我们就知道了【4】中用曼哈顿距离作为启发式函数其实并不能保证（虽然实践中很可能求出最优解）上面的结论. 所以曼哈顿距离作为A*算法的启发式函数并不能保证一定求出最优解（这也是为什么【5】中使用欧式距离的平方这么离谱的启发式函数得到了非最短路径的原因. ）. 而按照上图中的方式取启发式函数就能保证出堆的元素如果到达终点，则该节点一定是最优解.

ps: 我认为【5】不如我这篇文章讲的本质. 本文其实把启发式搜索和分支限界说透了.

而队列式的分支限界如果就是剪枝+bfs的话（注意这个前提~ 我说的是我理解的队列式分支限界, 如果有杠精说TA理解的队列式分支限界法是”启发式函数值为0,代价函数为目标函数的分支限界法（这种分支限界依旧要用优先队列而不是队列）”，那就没啥说的了,只是我看网上很多人云亦云说队列式分支限界法就是先进先出，用队列而不是优先队列），也不难理解为什么它是错的了. 因为bfs的代价函数和目标函数未必一致嘛~ 这个前面说过了. 所以大部分网上分支限界法用的都是优先队列式分支限界. 而不是队列式分支限界.

关于第三个问题

剪枝嘛~ 对深度和宽度而言都是一样的——就是不再继续在已经不可能是最优解的状态树上的某些子树上搜索了. 放到这里，就是说让肯定不可能是最优解的节点进队了. 那么怎么判断一个节点已经失去资格了呢（kill 掉它，不再开拓它了）?

其实分支限界四个字我不晓得大家是怎么理解的？

分支自然不消说. 就是状态树上的分支嘛~

限界呢?

我理解的界有2个界.

第一个界就是上面说的启发式函数定的（走完剩余路的真实代价函数的）下界. 它用来在优先队列中每次出堆更有希望的节点（启发式函数为0则就是只根据眼前状况来找，注意，再次声明，这种启发式并不等价于bfs，bfs只是这种启发式函数为0的启发式搜索的一个特例而已，bfs是代价函数等于搜索步长的启发式搜索），从而提高算法的效率. 即这个下界用于更快的接近答案.

第二个界就是上界. 它应该额外维护. 但是具体问题的上界构造是不一样的（启发式函数亦是如此）. 这个界的作用是用于剪枝. 减少问题的规模. 当然，一个分支限界问题你不定上界进行剪枝亦是没有问题的（相当于取了一个inf作为上界函数）.

关于第四个问题

网上最常见的说法是——活动节点列表（其实就是堆）为空的时候. 其实这种说法肯定是正确的——但是经过上面的论述我们知道其实没必要等到活动节点列表为空才结束——只要你的真实代价函数=目标函数而且启发式函数<=走完剩余路的真实代价函数的话，则就可以一旦到达终点就退出循环结束分支限界算法. 但是当终点意义不明的情况下，就可以当堆中的节点为空的时候才结束算法. 这一点在【1】中用到了. 那，对于没有”出堆元素如果到达终点就必定是最优”这一点需求的话，我们的启发式函数是否可以任取了呢? 是可以的. 但是这样的话，我们就必须要等到整个堆中节点为空了才行. 那岂不是太慢了? 非也(【1】、【2】就是这样)~ 因为我们某个出堆元素到达了终点的话，我们就可以更新最优解，然后用这个最优解来做上界进行剪枝——砍掉不可能成为最优解的节点，不让它进堆. 当然，我们还是希望不要取太离谱（但是可能并不满足<=真实走完剩余路产生的代价函数）的启发式函数，原因在第三个问题也说了——我们希望能快速接近最优解，然后搞到一个比较好的上界（也就是近似解），从而更加快速的剪枝. 注意，这和【5】中选择欧氏距离的平方这个离谱的启发式函数得到非最短路径不矛盾，因为【5】中的代码在堆顶元素到达终点的时候就结束了算法从而只能得到一个上界（近似解）.如果能等到堆变空才结束算法的话，就一定能得到最优解.

话说回来——如果满足启发式函数<=真实走完剩余路产生的代价函数的话, 则可以不需要剪枝——因为你没办法产生用于剪枝的上界——因为上界一般是堆顶到达终点了出堆产生的. 但是你这种情况下，一旦堆顶到达终点出堆的话，算法就已经结束了. 还剪个屁枝啊~

关于第五个问题

谈到节点复活问题，其实在【3】中部分讲到过了——即【3】中讲解了为什么在bfs中，节点不需要复活. 但是那是在代价函数恒为搜索步长的情况下才不需要复活. 对于现在启发式搜索或者分支限界情况下就可能不同了.

其实节点是否有误复活的必要等价于再次发现此节点时，此节点的真实代价函数有无可能减少（不需要考虑此节点的启发式函数, 因为节点的启发式函数一般是位置的函数, 一般不变化）. 只有它能减少，它才可能继续松弛其他节点(这一点和spfa中的队列优化思想完全一样), 不然它是没必要复活再次进队的. bfs中因为搜索步长是时间的严格单增函数, 所以死去（即出队）的节点不需要再次进队, 所以bfs算法才要有一个哈希数组来记录已经死掉的节点（即曾经进过队的节点, 即bfs算法表面上哈希的是顶点、格点啥的，其实本质上哈希的是队列节点——以便让已经出队的队列节点不能重新进队）. 对于A*算法，不难证明死去的节点亦是没必要复活的.

参考

【1】https://yfsyfs.github.io/2019/08/19/hdu-3810-Magina-%E6%95%8C%E6%B3%95%E5%B8%88-%E4%BC%98%E5%85%88%E9%98%9F%E5%88%97%E5%BC%8F%E5%88%86%E6%94%AF%E9%99%90%E7%95%8C%E6%B3%95%E6%B1%82%E8%A7%A301%E8%83%8C%E5%8C%85/

【2】https://yfsyfs.github.io/2019/09/05/hdu-5067-Harry-And-Dig-Machine-tsp%E9%97%AE%E9%A2%98/

【3】https://yfsyfs.github.io/2019/05/27/%E4%BD%BF%E7%94%A8bfs%E6%B1%82%E8%A7%A3%E6%9C%89%E5%90%91%E7%BD%91%E6%9C%80%E7%9F%AD%E8%B7%AF%E5%BE%84/

【4】https://yfsyfs.github.io/2019/05/26/A-star-%E5%AF%BB%E8%B7%AF%E7%AE%97%E6%B3%95/

【5】https://blog.csdn.net/zgwangbo/article/details/52078338