束搜索算法Andrew-Jungwirth-初稿BEAM-Search
束搜索算法（Andrew Jungwirth 初稿）BEAM Search
·最近搜了几篇BEAM SEARCH 束搜索的文章，这篇最直白易懂，并有示例的详细步骤图解，比维基百科的更为合适，因此拿在这里，供参考。
原文链接：
束搜索算法
本文目标：
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 nodes
SET = ∅; // 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 set
g = 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 B
state = successor in SET with smallest h value;
SET = SET \ { state }; // remove state from SET
if(state ∉ hash_table){ // state is not in the hash_table
if(hash_table is full) return ∞;
hash_table = hash_table ∪ { state }; // add state to hash_table
BEAM = 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
| loop number | Set( first row per numbered loop ) BEAM( second row per numbered loop ) | hash*table |
| BEAM = { I(null) } | hash_table = { *, I(null), _, _, _, _, _ } | |
| 1 | SET = { G(I), J(I), E(I), H(I) } | hash_table = { _, I(null), _, _, _, _, _ } |
| 1 | BEAM = { G(I) } | hash_table = { _, I(null), _, _, _, _, G(I) } |
| 2 | SET = { D(G), J(G), I(G) } | hash*table = { *, I(null), _, _, _, _, G(I) } |
| 2 | BEAM = { D(G) } | hash*table = { *, I(null), _, D(G), _, _, G(I) } |
| 3 | SET = { G(D) } | hash_table = { _, I(null), _, D(G), _, _, G(I) } |
| 3 | BEAM = { } | hash_table = { _, I(null), _, D(G), _, _, G(I) } |
搜索树如下图所示：
图 2
此时，BEAM 已经为空，搜索无解。G 的邻节点 D 已经在 close table 中了，因此搜索无法再继续下去，导致 BEAM 为空。该例说明了束搜索的一个致命弱点：如果启发式函数不正确，可能使算法找不到最优路径，即使该最优路径确实是存在的。如果增大 B 值呢？一方面，使得算法找打最优路径的概率增大，另一方面，它也增大了存储空间。因此，B 的选择极大的影响了束搜索的性能。图 2 即为失败的搜索路径示例。
下面我们改变 B 的值，再看看结果如何，待搜索的图还是图 1，下下面是搜索过程：
Trace 2, B = 2
| loop number | Set( first row per numbered loop ) BEAM( second row per numbered loop ) | hash table |
| BEAM = { I(null) } | hash_table = { _, I(null), _, _, _, _, _ } | |
| 1 | SET = { G(I), J(I), E(I), H(I) } | hash_table = { _, I(null), _, _, _, _, _ } |
| 1 | BEAM = { G(I), J(I) } | hash_table = { _, I(null), J(I), _, _, _, G(I) } |
| 2 | SET = { A(J), D(G), G(J), J(G), E(J), I(G) } | hash_table = { _, I(null), J(I), _, _, _, G(I) } |
| 2 | BEAM = { A(J), D(G) } | hash_table = { A(J), I(null), J(I), D(G), _, _, G(I) } |
| 3 | SET = { C(A), G(D), J(A) } | hash_table = { A(J), I(null), J(I), D(G), _, _, G(I) } |
| 3 | BEAM = { C(A) } | hash_table = { A(J), I(null), J(I), D(G), C(A), _, G(I) } |
| 4 | SET = { B(C) [goal found - algorithm returns], A(C) } | hash*table = { A(J), I(null), J(I), D(G), C(A), *, G(I) } |
图 3
这次搜索过程中，路径 IJACB 找到了解。然而，尽管找到了一条通路，但是该解并不是最优的。这里，不精确的启发式函数又影响了搜索的性能。图 3 即为搜索过程的搜索树。注意，在第三层节点中，只有一个节点 A 进入了搜索树，这证明了，该搜索算法并不是将每一层的最优节点都被放入 BEAM 中。
下面再将 B 设为 3，看看结果如何：
Trace 3, B = 3
| loop number | Set( first row per numbered loop ) BEAM( second row per numbered loop ) | hash*table |
| BEAM = { I(null) } | hash_table = { *, I(null), _, _, _, _, _ } | |
| 1 | SET = { G(I), J(I), E(I), H(I) } | hash_table = { _, I(null), _, _, _, _, _ } |
| 1 | BEAM = { G(I), J(I), E(I) } | hash_table = { _, I(null), J(I), _, E(I), _, G(I) } |
| 2 | SET = { A(J), C(E), D(G), F(E), G(J), J(E), E(J), H(E), I(E) } | hash*table = { *, I(null), J(I), _, E(I), _, G(I) } |
| 2 | BEAM = { A(J), C(E), D(G) } | hash*table = { A(J), I(null), J(I), C(E), E(I), D(G), G(I) } |
| 3 | SET = { B(C) [goal found - algorithm returns], A(C), C(A), J(A) } | hash_table = { A(J), I(null), J(I), C(E), E(I), D(G), G(I) } |
搜索树如下图：
图 4
当 B=3 时，束搜索找到了最优解。然而，同时 hashtable 的空间也被填满。
Trace 4, B = 4
| loop number | SET (first row per numbered loop) BEAM (second row per numbered loop) | hash_table |
| BEAM = { I(null) } | hash_table = { *, I(null), _, _, _, _, _ } | |
| 1 | SET = { G(I), J(I), E(I), H(I) } | hash_table = { _, I(null), _, _, _, _, _ } |
| 1 | BEAM = { G(I), J(I), E(I), H(I) } | hash_table = { H(I), I(null), J(I), _, E(I), _, G(I) } |
| 2 | SET = { A(J), C(E), D(G), F(E), G(J), J(E), E(H), H(E), I(E) } | hash_table = { H(I), I(null), J(I), _, E(I), _, G(I) } |
| 2 | BEAM = { A(J), C(E), D(G) [not enough memory - algorithm returns] } | hash_table = { H(I), I(null), J(I), A(J), E(I), C(E), G(I) } |
搜索树如下：
图 5
当 B=4 时，该算法很快就存储不够了。这展示了束搜索的一个重要缺陷：当 B 很大时，它也会想 BFS 一样耗尽存储。
注：原文还有关于效率和正确性的一些分析，以及一个小练习，在此未翻。