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

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

**Want more?**

**Want more?**

Last updated