Beam-Search学习笔记

Beam-Search

类似于A* 搜索和优先队列搜索，通过各种方式得到一个评估函数h(s)，用于评估状态s的得分，得分越高/越低，约有可能搜到结果，这个可能性和时间与空间的限制密切相关，所以不能保证有解的时候能搜到解，也不能保证搜到的解是最优解。
与A* 和优先队列不同的是，Beam-Search并非每次都取当前最优(h(s)最大/最小)，而是将当前层的状态集合S的所有后继状态S' = {s0,s1,s2, ... ,sk}（当然S'是按h(s)排好序的），分成若干个Slice，每个Slice里最多B个后继状态，一个Slice称为一个Beam。也就是每次拓展状态最多也就拓展出B个状态，这样拓展了scnt个状态后hash表里也就scnt*B个状态，空间复杂度比起普通BFS来说从指数降到了线性，当然这是以牺牲准确度为代价的。
当然也有Depth-First-Beam-Search，每次拓展B个后继状态不变，搜索形式类似于DFS，这可以算是在时间宽松的情况下的一种改进，同样的空间复杂度，搜索到更多的状态，回溯的时候注意清理hash表，所以不能避免重复状态。

Limited Discrepancy Search

这是这篇论文里比较有意思的一个思路——可以选择非最优的后继状态拓展，但是有惩罚(令discrepancies-1)。也就是说每次往下拓展(这里还没有考虑Beam-Search)的时候，如果拓展的是最优的后继状态，那么discrepancies不变，否则-1。约束了最多只能尝试一开始限制的discrepancies那么多次非最优状态的拓展，这样就不至于说回溯的时候还在焦头烂额的拓展比较靠近叶节点的状态，而是可以更快地回溯到根节点——正所谓“一步错，步步错”，这种策略体现了从根源上减少错误的思想。
换个角度去看这种思路，和迭代加深有种微妙的相似。

BULB

也就是Beam-Serach中使用Limited Discrepancy Search，回溯的时候注意hash表的维护和Slice的选择即可。

按层拓展，回溯，还通过评估函数加速求解，个人感觉是A*在充分利用空间的情况下对时间空间的有效折衷。