A-star algorithm
A* is an informed graph-search algorithm that prioritizes paths or states by combining the cost incurred so far with a heuristic estimate of the remaining cost to a goal.
Classic Computer Science Problems in Swift: Essential techniques for practicing programmers
A* search explores a state graph using the sum of a path cost and a heuristic estimate of the remaining cost to prioritize states.
- How it is used
- Finds shortest paths by prioritizing promising states rather than exploring breadth-first layers.
- How deep it goes
- Defines cost and heuristic scores, gives the optimality condition, and implements generic Swift search without a formal proof.
- Examples
- Uses a grid maze with blocked cells, four-direction movement, and Swift functions for Euclidean and Manhattan distance.
- What you can do after
- Build it from scratch with a Swift priority queue, goal test, successor function, and heuristic function.
Optimization Algorithms: AI techniques for design, planning, and control problems
An informed graph search algorithm that ranks states using path cost plus a heuristic estimate of remaining cost.
- How it is used
- Uses informed graph search to find routes between source and destination nodes while reducing explored states.
- How deep it goes
- Explains evaluation functions, pseudocode, heuristics, weighting, and routing code, but does not provide formal optimality proofs.
- Examples
- Demonstrates A* on an eight-point road network and a geographic route built with OSMnx, NetworkX, and Haversine distance.
- What you can do after
- Apply via Python routing code using graph nodes, cost functions, frontier management, and heuristic functions.
Advanced Algorithms and Data Structures
The A* algorithm is a best-first shortest-path search algorithm that prioritizes vertices using the cost already incurred plus a heuristic estimate of the remaining cost.
- How it is used
- Finds minimum-distance or minimum-time routes while using goal-directed domain information to reduce unnecessary search.
- How deep it goes
- Develops a generic implementation, compares BFS and Dijkstra’s algorithm, and discusses heuristic scaling and performance limits.
- Examples
- Uses delivery routes, straight-line distance, traffic-aware navigation, and graph cases where A* does or does not outperform Dijkstra’s algorithm.
- What you can do after
- Build an extensible shortest-path search and tune its distance and heuristic functions for route-planning data.
Read how Advanced Algorithms and Data Structures explains A-star algorithm →
Grokking AI Algorithms, Second Edition
A* is a heuristic graph and tree search algorithm that prioritizes nodes using the cost already incurred plus a heuristic estimate of the remaining cost to the goal.
- How it is used
- Uses heuristic guidance to search trees or graphs efficiently for a goal, especially when finding a low-cost path.
- How deep it goes
- Explains cost calculation, heuristic conditions, priority-queue ordering, path reconstruction, and a maze-oriented implementation.
- Examples
- Demonstrates maze navigation with parent-linked nodes, a min-heap priority queue, path length, move cost, and Manhattan distance.
- What you can do after
- Apply it via a priority queue to explore a maze or other graph and reconstruct a shortest path under suitable heuristic conditions.
Read how Grokking AI Algorithms, Second Edition explains A-star algorithm →
Clojure: The Essential Reference
A* is a graph-search algorithm that selects paths using the sum of accumulated path cost and a heuristic estimate of remaining cost.
- How it is used
- Guides shortest-path searches through graphs for robot navigation, games, and navigation software.
- How deep it goes
- Explains graph representation, heuristic scoring, queue ordering, neighbor discovery, recursion, and sample routes.
- Examples
- Uses a cyclic location graph, composite sorted-map keys, and routes from :orig to :dest and from :d to :c.
- What you can do after
- Builds a small A* pathfinder in Clojure using sorted-map-by as its priority queue.
Read how Clojure: The Essential Reference explains A-star algorithm →
Related concepts
- heuristicuses · A heuristic is a practical rule or approximate method for guiding judgment, search, or problem solving without guaranteeing an exact or optimal result.
- informed searchkind of · Informed search is a search strategy that uses problem-specific knowledge or heuristic estimates to prioritize promising states or paths.
- uniform-cost searchequivalent to · Uniform-cost search is a graph-search algorithm that repeatedly expands the frontier node with the lowest accumulated path cost.
- priority queueuses · A priority queue is an abstract data type that retrieves or removes elements according to assigned priority rather than insertion order.
- distanceuses · Distance is a measure of separation between points or entities in a defined space or context.
These guides are generated from the text of Manning books by Manning's knowledge graph and link to the sections they draw on. The full books are available on liveBook and at manning.com.