Speedy Versus Greedy Search
Speedy Versus Greedy Search
复制标题
快速搜索与贪婪搜索
DOI：
--
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
Wheeler Ruml
中科院分区：
文献类型：
--
作者：
C. Wilt;Wheeler Ruml
在满足搜索的工作中，人们一直致力于如何解决启发式函数中与局部极小或平台相关的问题。一种已被证明相当有前景的技术是使用另一种启发式函数，该函数不估计待完成成本，而是估计有待完成的距离。经验结果总体上倾向于使用距离启发式而不是启发式成本，但目前除了直觉之外，几乎没有其他方法来解释这种差异。我们首先从经验上证明，距离启发式算法的成功似乎与其具有较小的局部最小值有关。然后，我们讨论了一个合理的启发式算法的理论模型，并证明了在该模型下，费用启发式算法的局部极小值的预期大小高于距离启发式算法，这为为什么距离启发式算法的性能往往好于成本启发式算法提供了可能的解释。
In work on satisficing search, there has been substantial attention devoted to how to solve problems associated with local minima or plateaus in the heuristic function. One technique that has been shown to be quite promising is using an alternative heuristic function that does not estimate cost-to-go, but rather estimates distance-to-go. Empirical results generally favor using the distance-to-go heuristic over the cost-to-go heuristic, but there is currently little beyond intuition to explain the difference. We begin by empirically showing that the success of the distance-to-go heuristic appears related to its having smaller local minima. We then discuss a reasonable theoretical model of heuristics and show that, under this model, the expected size of local minima is higher for a cost- to-go heuristic than a distance-to-go heuristic, offering a possible explanation as to why distance-to-go heuristics tend to outperform cost-to-go heuristics.