# A\* Search

{% hint style="warning" %}
In order to understand A\*, you'll need to review [Dijkstra's Algorithm](/algorithms/shortest-paths/dijkstras-algorithm.md) first! Come back after you're done with that 😉
{% endhint %}

## 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?**

[Here's a cool demo!](https://docs.google.com/presentation/d/177bRUTdCa60fjExdr9eO04NHm0MRfPtCzvEup1iMccM/edit#slide=id.g369665031c_0_350)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://cs61b.bencuan.me/algorithms/shortest-paths/a-search.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.