CS61B Guide
  • This site is now deprecated
  • Object Oriented Programming
    • Inheritance
    • Access Control
    • Dynamic Method Selection
    • Java Objects
    • Generic Types
  • Asymptotics
    • Asymptotic Analysis Basics
    • Amortization
    • Asymptotics Practice
  • Abstract Data Types
    • Collections
      • Arrays
      • Linked Lists
      • Sets
      • Stacks and Queues
    • Binary Trees
      • Heaps
      • Balanced BSTs
      • Tries
    • Graphs
    • Hashing and Hash Tables
    • Union Find (Disjoint Sets)
    • Comparables and Comparators
  • Sorting
    • Sorting
  • Algorithms
    • Minimax Algorithm
    • Searching
      • Binary Search
      • Depth First Search (DFS)
      • Breadth First Search (BFS)
    • Shortest Paths
      • Dijkstra's Algorithm
      • A* Search
    • Minimum Spanning Trees
      • Prim's Algorithm
      • Kruskal's Algorithm
  • Misc Topics
    • Modular Arithmetic and Bit Manipulation
    • Exceptions
    • More Resources
Powered by GitBook
On this page
  • A* Algorithm
  • What's a good heuristic?
  • Want more?

Was this helpful?

  1. Algorithms
  2. Shortest Paths

A* Search

Special thanks to Arin for writing this page!

PreviousDijkstra's AlgorithmNextMinimum Spanning Trees

Last updated 5 years ago

Was this helpful?

In order to understand A*, you'll need to review 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?

Dijkstra's Algorithm
Here's a cool demo!