Andrew Zhang Aug 6, 2017
beam search是一个普通搜索算法的优化技巧。 拿A*为例来说，在
n
维平面中，一个点有3n−1个邻接点，随着n的增加，需要保存的状态点的个数指数级增加。 如果内存不支持把所有的状态点都给保存了，而还想采用A*算法那怎么办？一个选择就是可以采用beam search的思路，比如说根据适应度函数只保存一半的状态点，或者更少。当然，缺点就是beam search的准确性有一定损失。 由于再次搜索已经搜索过的点是没有意义的，在应用beam search的时候为了保证搜索过的点不会被再次搜索，利用一个hash表来保存搜索过的点。
http://jhave.org/algorithms/graphs/beamsearch/beamsearch.shtml https://en.wikipedia.org/wiki/Beam_search
