# Applied CS Skills – Puzzle-8 – A* algorithm

[MUSIC PLAYING] SPEAKER: What is the

A* search algorithm? The A* algorithm is a

path-finding algorithm, which means it’s used to find

a path between two points, usually in a graph. A graph can be used to

model lots of things, such as growth between cities

or even moves in a game. Let’s say you’re

about to start school and you want to

find the shortest path to your new classroom. To do so, you decide

to do some exploring. You could try going

down every path and seeing where it leads

and eventually you’ll find the classroom, but

this might take a long time. Instead of trying every path,

the A* algorithm tries the most promising path first. This means to use

the A* algorithm, you need to be able to compare

two positions in the graph and say which of

the two is better. To determine this, you’ll use

what’s called a heuristic. This should give you the

estimated total cost of taking one path rather than another. In our example, the heuristic

might be the straight line distance the classroom, and

so the total cost at any point is the distance taken to

get to that point added to the estimated cost

given by our heuristic. As you look at potential

next steps through the graph, you will use the heuristic– or

evaluation function– to choose the next node to visit. So that you don’t explore

nodes you’ve been to before, the A* algorithm uses two lists,

sometimes known as the open and closed lists. The closed list

holds all the nodes that you’ve already explored

and don’t need to consider, and the open list holds all

the nodes left to visit. Using these lists, you can

keep track of your exploration through the graph until

you find the best path. [MUSIC PLAYING]