Reputation: 297
What is the worst case for A* search algorithm?
Under what conditions will the A* search algorithm explore all the states in the search space? Is this the worst case?
According to me, it will be forced to search the entire search space if f(n) for each node on the route to the goal, is higher than the other nodes on the same level. This is the worst case since all the nodes generated must be expanded to reach the goal.
Is this correct?
Upvotes: 3
Views: 3106
Answers (1)
Reputation: 8230
From wikipedia:
The time complexity of A* depends on the heuristic. In the worst case, the number of nodes expanded is exponential in the length of the solution (the shortest path), but it is polynomial when the search space is a tree, there is a single goal state, and the heuristic function h meets a certain criteria:
Upvotes: 1
Related Questions
- A* bug (A star search algorithm)
- A* search two possibilities
- In A* search algorithm what do you check for when looping through the open list?
- What's the difference between best-first search and A* search?
- How would A* search a graph?
- A* Search Algorithm
- A* (star) algorithm: understanding the f/g/h scores
- Why is A* search algorithm better than A?
- A* functionality
- Finding good heuristic for A* search