# A* Search

Content Note

In order to understand A*, you’ll need to be comfortable Dijkstra’s Algorithm first!

## A* Algorithm #

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.

## What’s a good heuristic? #

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)