Overview
This lecture explains the A* (A-star) search algorithm, emphasizing its use of admissible heuristics to efficiently find optimal paths in a search space.*
A* Search Algorithm Basics*
- A* search returns the optimal path using heuristic cost estimates to guide the search.
- Each node is assigned a heuristic value: an estimate of the cost from that node to the goal.
- The heuristic must never overestimate actual cost (must be admissible) for A* to guarantee optimality.
- The A* score for a node is the cost so far plus the heuristic value of the node.
- A* expands nodes with the lowest A* score first, similar to uniform cost search but informed by the heuristic.*
Node Expansion and Heuristic Use
- When expanding a node, add its neighbors to the search tree with corresponding path costs and heuristic values.
- If a node is reached with a lower A* score than previously found, consider the new path; otherwise, ignore it.
- Nodes already visited with a better or equal A* score are not re-expanded.
Path Selection and Efficiency
- Among active branches, always expand the one with the lowest A* score.
- If the heuristic is not accurate (far from true cost), A* may still do significant work.
- A* finds the optimal path if the heuristic is admissible, even if it explores many nodes.*
Key Terms & Definitions
- A (A-star) Search* — An informed search algorithm using costs and heuristics to find optimal paths.
- Heuristic — Quick, estimated cost from a node to the goal, used to guide the search.
- Admissible Heuristic — A heuristic that never overestimates the actual minimum cost to the goal.
- A Score* — The sum of the path cost so far and the heuristic value for the current node.
Action Items / Next Steps
- Rerun the A* search algorithm using more accurate heuristic values as assigned.*