# A* search algorithm

> algorithm used for pathfinding and graph traversal

**Wikidata**: [Q277680](https://www.wikidata.org/wiki/Q277680)  
**Wikipedia**: [English](https://en.wikipedia.org/wiki/A*_search_algorithm)  
**Source**: https://4ort.xyz/entity/a-search-algorithm

## Summary
The A* search algorithm is a pathfinding and graph traversal algorithm widely used in computer science to find the shortest path between nodes. It combines the precision of Dijkstra’s algorithm with heuristic estimates to efficiently navigate toward a goal. A* is both optimal and complete when using admissible heuristics.

## Key Facts
- Invented in 1968 by Peter E. Hart, Nils John Nilsson, and Bertram Raphael.
- Classified as a best-first search algorithm and an admissible search algorithm.
- Uses graph data structures and solves the shortest path problem.
- Has a worst-case time complexity of **O(b^d)** and space complexity of **O(b^d)**, where *b* is the branching factor and *d* is the depth of the solution.
- Subclass of best-first search and parent to algorithms like Simplified Memory-Bounded A* and Iterative Deepening A*.
- Described in detail in *Artificial Intelligence: A Modern Approach* (p. 93).
- Derivative algorithms include Jump Point Search.

## FAQs
### Q: What is the A* search algorithm used for?
A: The A* search algorithm is used for pathfinding and graph traversal, particularly in applications requiring the shortest path between two points, such as GPS navigation, robotics, and game AI.

### Q: Is A* better than Dijkstra's algorithm?
A: A* can be more efficient than Dijkstra’s algorithm because it uses a heuristic function to guide the search, reducing the number of explored nodes while still guaranteeing an optimal solution if the heuristic is admissible.

### Q: Who invented the A* algorithm?
A: The A* algorithm was developed in 1968 by Peter E. Hart, Nils John Nilsson, and Bertram Raphael at the Stanford Research Institute.

## Why It Matters
The A* search algorithm revolutionized pathfinding by introducing a balance between accuracy and efficiency through heuristic guidance. Unlike uninformed search methods like breadth-first or Dijkstra’s, A* intelligently prioritizes paths likely to lead to the goal, making it essential in fields like robotics, artificial intelligence, and video game development. Its ability to guarantee optimal solutions under specific conditions ensures reliability across critical systems, from autonomous vehicles to network routing protocols.

## Notable For
- First algorithm to combine heuristic estimation with guaranteed optimality under admissible conditions.
- Foundational in modern AI and pathfinding applications including GPS and game AI.
- Basis for numerous optimized variants like Jump Point Search and Memory-Bounded A*.
- Recognized in leading AI textbooks and academic literature for completeness and practical utility.

## Body
### Overview
The A* search algorithm is a graph traversal and path search algorithm designed to find the least-cost path from a start node to a target node. It extends Dijkstra’s algorithm by incorporating a heuristic function that estimates the cost from any given node to the goal, enabling faster convergence.

### History and Development
- **Invented**: 1968
- **Creators**:
  - Peter E. Hart
  - Nils John Nilsson (American AI researcher, 1933–2019)
  - Bertram Raphael (American computer scientist)

The algorithm emerged from work on Shakey the Robot at SRI International, aiming to improve automated planning and navigation.

### Technical Characteristics
- **Classifications**:
  - Instance of: pathfinding algorithm, graph algorithm, complete search algorithm, admissible search algorithm
  - Subclass of: best-first search
- **Heuristic Requirement**: Must be admissible (never overestimate) and consistent (monotonic) for optimality.
- **Completeness**: Guaranteed to find a solution if one exists in a finite, locally finite graph.
- **Optimality**: Ensured when using admissible heuristics.

### Performance Metrics
- **Time Complexity**:  
  - Standard version: **O(b^d)**  
  - Worst case (without pruning): **O(2^|S|)**  
- **Space Complexity**: **O(b^d)**  
Where *b* is the branching factor and *d* is the solution depth.

### Applications
- Game development (NPC movement, map navigation)
- Robotics (motion planning)
- Geographic Information Systems (GPS route calculation)
- Network routing protocols
- AI planning systems

### Variants and Extensions
- **Iterative Deepening A*** (IDA*)
- **Memory-Bounded A*** (MA*)
- **Simplified Memory-Bounded A*** (SMA*)
- **Weighted A***
- **Recursive Best-First Search** (RBFS)
- **Jump Point Search** (derivative work)

### Related Algorithms and Concepts
- **Based On**: Dijkstra's algorithm
- **Related To**: Admissible search algorithms, heuristic functions, graph theory

### Resources and References
- Described in *Artificial Intelligence: A Modern Approach* (page 93)
- Featured on platforms like Brilliant.org, Rosetta Code, Quora Topics
- Documented in multiple languages on Wikipedia (en, es, de, etc.)

```json
{
  "@context": "https://schema.org",
  "@type": "Thing",
  "name": "A* search algorithm",
  "description": "algorithm used for pathfinding and graph traversal",
  "sameAs": [
    "https://www.wikidata.org/wiki/Q510919",
    "https://en.wikipedia.org/wiki/A*_search_algorithm"
  ],
  "additionalType": "pathfinding algorithm"
}

## References

1. [Source](https://cs.stanford.edu/people/eroberts/courses/soco/projects/2003-04/intelligent-search/astar.html)
2. [Source](https://ieeexplore.ieee.org/document/10050009)
3. Freebase Data Dumps. 2013
4. [Source](https://doi.org/10.1016/0004-3702(77)90002-9)
5. [OpenAlex](https://docs.openalex.org/download-snapshot/snapshot-data-format)