Understanding the Search Behaviour of Greedy Best-First Search
Understanding the Search Behaviour of Greedy Best-First Search
复制标题
了解贪婪最佳优先搜索的搜索行为
DOI：
--
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
M. Helmert
中科院分区：
文献类型：
--
作者：
Manuel Heusner;Thomas Keller;M. Helmert
最优搜索中的一个经典结果表明，A* 与一个容许的和一致的启发式扩展的每个状态的f-值是低于最优解的成本和没有状态的f-值是高于最优解的成本。对于满意搜索算法，目前缺乏类似的清晰理解。我们研究的贪婪最佳优先搜索（gbfs）的搜索行为，以取得进展，朝着这样的理解。我们引入了高水位线长凳的概念，它将搜索空间分成由gbfs算法按顺序搜索的区域。高水位线长凳允许我们精确地确定在任何gbfs平局打破策略下不被扩展的状态集。对于其余的国家，我们表明，一些扩展的所有gbfs的搜索，而其他扩展只有在某些条件得到满足。
A classical result in optimal search shows that A* with an admissible and consistent heuristic expands every state whose f-value is below the optimal solution cost and no state whose f-value is above the optimal solution cost. For satisficing search algorithms, a similarly clear understanding is currently lacking. We examine the search behaviour of greedy best-first search (gbfs) in order to make progress towards such an understanding. We introduce the concept of high-water mark benches, which separate the search space into areas that are searched by a gbfs algorithm in sequence. High-water mark benches allow us to exactly determine the set of states that are not expanded under any gbfs tie-breaking strategy. For the remaining states, we show that some are expanded by all gbfs searches, while others are expanded only if certain conditions are met.