Abstract: Heuristic hill-climbing search algorithm can do effectively pruning. In practice, it can be used to searching a large hypothesis space to get an optimal or approximate optimal solution. Beam search algorithm retains its advantage in efficiency while reducing the risk of converging to locally optimal hypotheses. Beam search algorithm is widespread used AI field. To k-size beam search, due to only k paths is maintained the key to optimize the accuracy of beam search is how to select the k paths. In most of search algorithms, the k candidates with the most high performance measure value are selected at each searching step. In this paper, the author presented some methods of candidate selection of beam search approaches, and the thought of avoiding “full of blood brother nodes” is presented. The experiments were done on the UCI repository of machine learning databases.

摘要： 启发式爬山搜索算法能高效地实现搜索剪枝，求解实际问题时，能在庞大的假设空间中，找到最优或近似最优解，束搜索算法保持了爬山搜索算法的高效剪枝特性，同时能有效减小爬山搜索收敛到局部最优解的风险，人工智能领域广泛采用束搜索策略。对于宽度为k的束搜索，由于只维持有限的k条搜索路径，提高束搜索算法的搜索精度，重在这k条路径的选择上，但如何选取这k条路径，作者未见描述相关方法的资料，目前多数算法是在每一搜索步选取具有最大启发式性能量度值的k个候选作为进一步搜索的入口。本文简要讨论了束搜索算法，提出了几种合理的候选选取方法以及避免单亲填满的思想，并在UCI测试数据库上进行了对比实验，给出了实验结果。