You are viewing a free preview of this lesson.
Subscribe to unlock all 10 lessons in this course and every other course on LearningBro.
A (A-star)* is an informed search algorithm that extends Dijkstra's algorithm by adding a heuristic function to guide the search towards the goal. It is widely used in pathfinding and graph traversal, particularly in game AI and robotics. At A-Level, you need to understand how A* works, the role of the heuristic, and how it compares to Dijkstra's algorithm.
Dijkstra's algorithm explores vertices in order of their distance from the source, expanding outwards in all directions equally. This means it may explore many vertices that are far from the goal.
A* improves on this by estimating the total cost of a path through each vertex:
f(n) = g(n) + h(n)
| Component | Meaning |
|---|---|
| f(n) | Estimated total cost of the cheapest path through n |
| g(n) | Actual cost from the start to n (known, calculated) |
| h(n) | Heuristic estimate of the cost from n to the goal (estimated) |
A* always selects the vertex with the lowest f(n) value next.
Subscribe to continue reading
Get full access to this lesson and all 10 lessons in this course.