7
Oct

# 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]

Tags: , ,