A Star Search

overview

Summary

A* finds the shortest path by ranking nodes with f_cost = g_cost + h_cost. In a_star_search, the frontier is the open_set stored in a priority_queue, and visited nodes go to the closed_set. With an admissible_heuristic (never overestimates), A* returns an optimal_path. A consistent_heuristic guarantees no re-openings. A* stops when the goal is removed from the queue. Common domains include grids and graphs. Remember: cost-so-far, heuristic, and tie-breaking guide expansion.