A-Star Search
# A* Search
Combines Greedy Best First Search h(n) with Uniform Cost Search g(n)
Evaluation function $$f(n)=g(n)+h(n)$$ Remember to take the full path cost in calculating g(n) for a node
Optimality: Optimal with a admissible heuristic Time Complexity: Exponential in length of solution Space Complexity: Exponential in length of solution
Admissible Heuristic for every node n, it underestimates the cost of getting from n to the closest goal node there is no path from n to a goal that has path cost less than h(n). It prevents A* from skipping the optimal solution.
Suppose you’re trying to drive from Chicago to New York and your heuristic is what your friends think about geography. If your first friend says, “Hey, Boston is close to New York” (underestimating), then you’ll waste time looking at routes via Boston. Before long, you’ll realise that any sensible route from Chicago to Boston already gets fairly close to New York before reaching Boston and that actually going via Boston just adds more miles. So you’ll stop considering routes via Boston and you’ll move on to find the optimal route. Your underestimating friend cost you a bit of planning time but, in the end, you found the right route.
Guaranteed to expand no more nodes than UCS: Heuristics guide the search towards the goal node which prevents expansion of redundant nodes. Where heuristic h(n) = 0, it will expand the same number as UCS.
# Example Graphs
