Skip to content

A* Search

A* Search

Optimal pathfinding algorithm that uses heuristics to efficiently find the shortest path from start to goal in weighted graphs.

Family: Planning Algorithms Status: ✅ Complete

Need Help Understanding This Algorithm?

🤖 Ask ChatGPT about A* Search

Overview

A* Search is one of the most popular and effective pathfinding algorithms, combining the best of both

uniform-cost search and greedy best-first search. It uses a heuristic function to estimate the cost from any node to the goal, allowing it to make informed decisions about which paths to explore.

The algorithm is optimal when using an admissible heuristic (one that never overestimates the true cost) and is complete, meaning it will always find a solution if one exists. A* is widely used in robotics, game AI, and navigation systems.

Mathematical Formulation

🧮 Ask ChatGPT about Mathematical Formulation

Mathematical Properties

Evaluation Function

f(n) = g(n) + h(n)

Total estimated cost through node n

Admissibility Condition

h(n) ≤ h*(n)

Heuristic never overestimates true cost

Consistency Condition

h(n) ≤ c(n, n') + h(n')

Heuristic satisfies triangle inequality

Optimality

f(n) = g*(n) + h*(n)

When h is admissible, A* finds optimal path

Key Properties

🔑 Ask ChatGPT about Key Properties

  • Optimal

    Finds shortest path when heuristic is admissible

  • Complete

    Guaranteed to find solution if one exists

  • Efficient

    Uses heuristics to guide search

  • Versatile

    Works with any graph structure and cost function

Implementation Approaches

💻 Ask ChatGPT about Implementation

Classic A* with priority queue and heuristic function

Complexity:

  • Time: O(b^d)
  • Space: O(b^d)

Advantages

  • Optimal solution when heuristic is admissible

  • Efficient exploration using heuristics

  • Complete algorithm

  • Works with any graph structure

  • Widely applicable

Disadvantages

  • Memory intensive for large search spaces

  • Quality depends on heuristic function

  • May explore many nodes in complex environments

  • Requires good heuristic for efficiency

Use Cases & Applications

🌍 Ask ChatGPT about Applications

Application Categories

Game AI

  • pathfinding in games: pathfinding in games

  • NPC movement: NPC movement

  • strategy games: strategy games

Robotics

  • robot navigation: robot navigation

  • motion planning: motion planning

  • autonomous vehicles: autonomous vehicles

Network Routing

  • internet routing: internet routing

  • transportation networks: transportation networks

  • logistics: logistics

Puzzle Solving

  • sliding puzzles: sliding puzzles

  • Rubik's cube: Rubik's cube

  • maze solving: maze solving

Educational Value

  • Understanding heuristic search: Understanding heuristic search

  • Optimality vs efficiency trade-offs: Optimality vs efficiency trade-offs

  • Graph search algorithms: Graph search algorithms

  • Algorithm design principles: Algorithm design principles

References & Further Reading

:material-book: Core Textbooks

:material-file-document:
:material-file-document:

Interactive Learning

Try implementing the different approaches yourself! This progression will give you deep insight into the algorithm's principles and applications.

Pro Tip: Start with the simplest implementation and gradually work your way up to more complex variants.

Need More Help? Ask ChatGPT!

Related Algorithms in Planning Algorithms:

  • M* - Multi-agent pathfinding algorithm that finds collision-free paths for multiple agents by resolving conflicts and coordinating their movements.

  • Depth-First Search - Graph traversal algorithm that explores as far as possible along each branch before backtracking, using stack-based or recursive implementation.

  • Breadth-First Search - Graph traversal algorithm that explores all nodes at the current depth level before moving to the next level, guaranteeing shortest path in unweighted graphs.