【摘要】：局部剪枝搜索算法[16]记录k个状态而不是一个。乍一看，k 个状态的局部剪枝搜索只不过是并行地而不是串行地运行 k 个随机重新开始搜索。而在局部剪枝搜索中，有用的信息在这k个并行的搜索线程之间传递。在其最简单的形式中，局部剪枝搜索会受到这k个状态缺乏多样性的影响——它们将很快聚集到状态空间中的一小块区域内，使得搜索比一个代价高昂的爬山法版本略多一些。
只在内存中保存一个节点看来是对内存限制问题的一个极端反应。局部剪枝搜索（local beam search）算法[16]记录k个状态而不是一个。它由k个随机生成的状态开始。每一步都生成全部k个状态的所有后继状态。如果其中有一个是目标状态，算法就停止。否则，它从整个后继列表中选择k个最佳的后继，然后重复这个过程。
乍一看，k 个状态的局部剪枝搜索只不过是并行地而不是串行地运行 k 个随机重新开始搜索。实际上，这两个算法是相当不同的。在随机重新开始搜索中，每个搜索过程的运行与其它搜索过程是独立的。而在局部剪枝搜索中，有用的信息在这k个并行的搜索线程之间传递。例如，如果一个状态生成了几个好的后继，而另外的k − 1个状态生成的后继都不好，那么效果就是第一状态对其它状态说：“来这儿吧，这儿的草更绿！”算法很快放弃没有成果的搜索而把资源都用在取得了最大进展的搜索上。
在其最简单的形式中，局部剪枝搜索会受到这k个状态缺乏多样性的影响——它们将很快聚集到状态空间中的一小块区域内，使得搜索比一个代价高昂的爬山法版本略多一些。这个算法的一个变化称为随机剪枝搜索，与随机爬山法相类似，帮助缓解这个问题。随机剪枝搜索不是从候选后继集合中选择最好的k个后继状态，而是按一定概率随机地选择k个后继状态，其中选择给定后继状态的概率是状态值的递增函数。随机剪枝选择和自然选择的过程有些相似性，“状态”（生物体）根据它的“值”（适应性）产生它的“后继”（后代）作为下一代。
免责声明：以上内容源自网络，版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。
