A* Algorithm
Computer Science: OCR A Level, topic 8.1.12
A* algorithm
An improved version of Dijkstra’s algorithm. A* finds the shortest path from a starting point to a goal on a graph. A* combines actual travel costs and estimated costs to prioritize promising paths.
Step-by-Step Overview
- Steps include:
- 1 Initialization
- 2 Cost Calculation
- 3 Explore
- 4 Expand Neighbors
- 5 Close Node
- 6 Repeat
- 7 Reconstruct Path
Initialization
- Step 1 Initialization
- Start with an open list (to explore) and a closed list (evaluated).
- Add the starting point to the open list with an initial cost of 0.
Cost calculation
- Step 2: Cost Calculation
- For each node, calculate:
- g(n): Cost from the start to the node.
- h(n): Estimated cost from the node to the goal.
- Total cost: f(n) = g(n) + h(n).
Explore
- Step 3: Explore
- While the open list isn’t empty:
- Select the node with the lowest f(n) (current node).
- If it’s the goal, reconstruct the path and finish.
Expand neighbors
- Step 4: Expand Neighbors
- For each neighbor of the current node:
- Calculate new g(n). If it’s lower than before, update costs and set the current node as the neighbor’s parent.
- Add the neighbor to the open list if not already present.
Close node, repeat, reconstruct path
- Step 5: Close Node
- Move the current node to the closed list.
- Step 6: Repeat
- Go back to step 3 until the goal is found or no paths remain.
- Step 7: Reconstruct Path
- If the goal is reached, trace back from the goal to the start using parent pointers to get the path.
Test yourself on A* Algorithm
What is the expression for the Total Cost?
What are the last 3 steps for the A* algorithm?