Best-Case and Worst-Case Behavior of Greedy Best-First Search
Abstract
We study the impact of tie-breaking on the behavior of greedy best-first search with a fixed state space and fixed heuristic. We prove that it is NP-complete to determine the number of states that need to be expanded by greedy best-first search in the best case or in the worst case. However, the best- and worst-case behavior can be computed in polynomial time for undirected state spaces. We perform computational experiments on benchmark tasks from the International Planning Competitions that compare the best and worst cases of greedy best-first search to FIFO, LIFO and random tie-breaking. The experiments demonstrate the importance of tie-breaking in greedy best-first search.
Cite
Text
Heusner et al. "Best-Case and Worst-Case Behavior of Greedy Best-First Search." International Joint Conference on Artificial Intelligence, 2018. doi:10.24963/IJCAI.2018/203Markdown
[Heusner et al. "Best-Case and Worst-Case Behavior of Greedy Best-First Search." International Joint Conference on Artificial Intelligence, 2018.](https://mlanthology.org/ijcai/2018/heusner2018ijcai-best/) doi:10.24963/IJCAI.2018/203BibTeX
@inproceedings{heusner2018ijcai-best,
title = {{Best-Case and Worst-Case Behavior of Greedy Best-First Search}},
author = {Heusner, Manuel and Keller, Thomas and Helmert, Malte},
booktitle = {International Joint Conference on Artificial Intelligence},
year = {2018},
pages = {1463-1470},
doi = {10.24963/IJCAI.2018/203},
url = {https://mlanthology.org/ijcai/2018/heusner2018ijcai-best/}
}