# A* Search

Special thanks to Arin for writing this page!

In order to understand A*, you'll need to review Dijkstra's Algorithm first! Come back after you're done with that 😉

The A* Search Algorithm is

**incredibly similar to Dijkstra's Algorithm**with one addition: a**heuristic function.**This heuristic function calculates weights of a path

**from a vertex to a goal vertex.**This way, we can help bias our algorithm in the right direction so that it doesn’t make a bunch of bad moves.This has an important implication:

**not all vertices get visited.**The algorithm only cares about finding the best path to the goal, and not any other vertex (assuming we design our heuristic well).The

**order**that the vertices get visited is lowest**distance + heuristic**. This is basically the same as Dijkstra's, just with that added heuristic term.Heuristic functions can be really tricky to design, since there isn't much to go off of.

**A good heuristic has these two properties:**

**Admissible**- heuristic of each vertex returns a cost that is <= the true cost/distance i.e. h(A) <= cost(A, goal)**Consistent**- difference between heuristics of two vertices <= true cost between them i.e. h(A) - h(B) <= cost(A, B)

Last modified 3yr ago