Thomas Keller

Best-Case and Worst-Case Behavior of Greedy Best-First Search

2018

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 …