A* Algorithms

Question 1

What does A* algorithm do?

Answer 1

Finds shortest path from starting point to goal on graph

Question 2

7 steps of A* algorithm?

Answer 2

1 Initialisation
2 Cost calculation
3 Explore
4 Expand neighbours
5 Close node
6 Repeat
7 Reconstruct path

Question 3

Initialisation

Answer 3

• Start with open list and closed list
• Add starting point to open list with initial cost of 0

Question 4

Formula for total cost: f(n)

Answer 4

Cost from start to node: g(n) + Estimated cost from node to goal: h(n)

Question 5

Explore

Answer 5

While open list isn’t empty, select node with lowest f(n) (if it’s goal then reconstruct path and finish)

Question 6

Expand neighbours

Answer 6

• For each neighbour of current node calculate g(n)
• If it’s lower then update costs and set current node as neighbour’s parent
• Add neighbour to current list if not already present

Question 7

Close node

Answer 7

Move current node to closed list

Question 8

Repeat

Answer 8

Go back to step 3 until goal is found or no paths remain