beam搜索

·最近搜了几篇BEAM SEARCH 束搜索的文章，这篇最直白易懂，并有示例的详细步骤图解，比维基百科的更为合适，因此拿在这里，供参考。

原文链接：Beam Search Algorithm (Draft by Andrew Jungwirth)

束搜索算法

本文目标：

1.演示了如何在存储有限的情况下进行类似的宽度优先的图搜索算法，即束搜索，使用启发式函数和限定的束宽度beam width .

2.强调在搜索空间很大的情况下对图搜索进行存储限制的重要性

3.展示了书搜索的优缺点

所需背景知识：

要了解束搜索，先要熟悉图的概念，如边和结点；知道搜索树如何表示图的搜索过程。除此之外，必须要了解宽度优先搜索算法，因为束搜索是对该算法的改进。

束搜索算法：

尽管宽度优先搜索能保证在 unweighted graph无向图中找到起始结点和终止节点之间的最短路径，但由于该算法对存储的消耗是指数级的，因此对于搜索空间大的问题，BFS几乎无用武之地，在算法周到最优解之前，存储就已经耗尽了。为对BFS进行改进，就有了束搜索算法。束搜索旨在消耗有限存储的情况下进行宽度优先遍历，找到最优解。

为此，束搜索要借助一个启发式代价函数heuristic cost function，h，来估计当前节点到目标节点的代价的大小。并用束宽度beam width，B，来限制在每层遍历时存储的该层节点的个数。因此，BFS存储的是下一层的所有节点，而束搜索仅根据h，存储B个最优的下层节点。利用启发式代价函数h是一个寻优的过程，而B又限制仅存储有限个重要的节点，避免了在达到最优解之前存储耗尽的情况。

在BFS搜索借助一个Openlist，在BS中则借助BEAM来存储将继续展开的节点。此外，还有一个hash table来存储已经访问过的节点，与BFS中的closed list作用类似。初始化时，把起始节点加入BEAM 和 hash table。 然后，在算法的每个主循环中，将在BEAM中的节点的所有后继节点加入SET中，并在SET中选取最优的B个节点加入BEAM和hash table中。注意，已经在hash table中的节点是不会再加入BEAM中的，因为到达改点的更近的路径已经找到了。直至目标节点加入到SET，或者hash table满了（表明存储耗尽），或者BEAM为空（表明搜索无解），则算法终止。

束搜索的伪码如下。该伪码是对于无向图而言，因此变量g表示的是搜索的深度，即到达该节点的代价大小。

束搜索的伪码：

/* initialization */
g = 0;
hash_table = { start };
BEAM = { start };/* main loop */
while(BEAM ≠ ∅){                             // loop until the BEAM contains no nodesSET = ∅;                                   // the empty set/* generate the SET nodes */for(each state in BEAM){for(each successor of state){if(successor == goal) return g + 1;SET = SET ∪ { successor };             // add successor to SET}}BEAM = ∅;                                  // the empty setg = g + 1;/* fill the BEAM for the next loop */while((SET ≠ ∅) AND (B > |BEAM|)){         // set is not empty and the number of nodes in BEAM is less than Bstate = successor in SET with smallest h value;SET = SET \ { state };                   // remove state from SETif(state ∉ hash_table){                  // state is not in the hash_tableif(hash_table is full) return ∞;hash_table = hash_table ∪ { state };   // add state to hash_tableBEAM = BEAM ∪ { state };               // add state to BEAM}}
}// goal was not found, and BEAM is empty - Beam Search failed to find the goal
return ∞;

束搜索的搜过过程示例

下面的算法步骤解析中，对每个main loop中的数据有两行表示：第一行为该次循环中加入SET的节点，这些节点按照启发式函数值排序，如果h值大小相同，则按照字母瞬息排序。由于该存储结果是数学集合，因此对于有多个前节点的节点，只出现在SET中一次；第二行数据给出从SET中留下存储到BEAM中的节点，即main loop中的第二部分。两行中都给出了hash table的值，即当前的状态。注意，在该例子中，hash table大小是7，哈希函数是简单的线性焊锡，即键值的ASCII值模7。每个节点以 节点名（前继节点）的方式表示。

图1

Trace 1, B = 1

搜索树如下图所示：

图2

此时，BEAM已经为空，搜索无解。G的邻节点D已经在close table 中了，因此搜索无法再继续下去，导致BEAM为空。该例说明了束搜索的一个致命弱点：如果启发式函数不正确，可能使算法找不到最优路径，即使该最优路径确实是存在的。如果增大B值呢？一方面，使得算法找打最优路径的概率增大，另一方面，它也增大了存储空间。因此，B的选择极大的影响了束搜索的性能。图2即为失败的搜索路径示例。

下面我们改变B的值，再看看结果如何，待搜索的图还是图1，下下面是搜索过程：

Trace 2, B = 2

图3

这次搜索过程中，路径IJACB找到了解。然而，尽管找到了一条通路，但是该解并不是最优的。这里，不精确的启发式函数又影响了搜索的性能。图3即为搜索过程的搜索树。注意，在第三层节点中，只有一个节点A进入了搜索树，这证明了，该搜索算法并不是将每一层的最优节点都被放入BEAM中。

下面再将B设为3，看看结果如何：

Trace 3, B = 3

图4

当B=3时，束搜索找到了最优解。然而，同时hashtable 的空间也被填满。

Trace 4, B = 4

图5

当B=4时，该算法很快就存储不够了。这展示了束搜索的一个重要缺陷：当B很大时，它也会想BFS一样耗尽存储

来源：http://blog.csdn.net/girlhpp/article/details/19400731