论文标题
梁搜索：更快且单调
Beam Search: Faster and Monotonic
论文作者
论文摘要
光束搜索是一种流行的启发式搜索问题的令人满意的方法，它可以通过增加梁宽度参数来交易增加的计算时间，以换取较低的解决方案成本。我们为梁搜索的研究做出了两种贡献。首先，我们展示了如何使光束搜索单调。也就是说，我们提供了一种新的变体，可确保随着梁宽度的增加，可以保证非进攻解决方案成本。这使得设置光束参数变得更加容易。其次，我们展示了如何使用距离估计值允许光束搜索在成本不均匀的域中更快地找到更好的解决方案。这些结果共同提高了光束搜索的实际有效性。
Beam search is a popular satisficing approach to heuristic search problems that allows one to trade increased computation time for lower solution cost by increasing the beam width parameter. We make two contributions to the study of beam search. First, we show how to make beam search monotonic; that is, we provide a new variant that guarantees non-increasing solution cost as the beam width is increased. This makes setting the beam parameter much easier. Second, we show how using distance-to-go estimates can allow beam search to find better solutions more quickly in domains with non-uniform costs. Together, these results improve the practical effectiveness of beam search.
