Artificial intelligenceLesson 1 of 1 in the course Search

A* Search: Pathfinding, Heuristics, Guarantees, and Variants

5 flashcards · 5 quiz questions · 5 match pairs · 5 fill-in sentences · English

Save course
Lesson progress
0 / 5

Your progress is kept in this browser only.Sign up to save it

Summary

A* is a widely used algorithm for finding a least-cost route through a weighted graph. This lesson introduces the problem it solves, its place among search algorithms, and its origins.

A graph consists of nodes (states or locations) connected by edges (possible moves). Each edge has a weight, such as distance, time, or another cost. Given a start node and a goal node, a pathfinding algorithm seeks a route whose total edge weight is as small as possible.

All flashcards

What is A*?
An informed graph-search algorithm that seeks a least-cost path from a specified start node to a specified goal node.
What does f(n)=g(n)+h(n)f(n)=g(n)+h(n) represent?
f(n)f(n) estimates the total route cost through nn; g(n)g(n) is the known cost so far, and h(n)h(n) estimates the remaining cost.
What is a weighted graph?
A graph whose edges have costs, such as distance, travel time, or energy.
Who published A*, and when?
Peter Hart, Nils Nilsson, and Bertram Raphael published A* in 1968.
How does A* relate to Dijkstra's algorithm?
A* adds an estimate of the remaining cost to cost-based search; with a zero heuristic, it reduces to Dijkstra's algorithm.

Quiz questions

  1. What problem is A* primarily designed to solve?Answer: Finding a least-cost path between a start and a goal in a weighted graph.
  2. In a typical A* implementation, which frontier node is selected for expansion?Answer: The node with the lowest estimated total cost, f(n)f(n).
  3. How does Dijkstra's algorithm arise as a special case of A*?Answer: Set h(n)=0h(n)=0 for every node.
  4. How does greedy best-first search differ from A*?Answer: Greedy best-first search prioritizes the heuristic estimate and generally ignores the cost already paid.
  5. What distinguishes beam search from standard A*?Answer: Beam search limits how many candidates it retains.

Based on the Wikipedia article A* search algorithm, licensed CC BY-SA 4.0. Adapted into a summary, flashcards and quizzes.

More in Artificial intelligence

All Artificial intelligence lessons
Artificial intelligencePDDL Core Structure, Version History, and Planning Extensions5 flashcards · 5 quiz questions · 4 gamesPlay free →Artificial intelligenceDescription Logic: Knowledge Bases, ALC Semantics, and Reasoning5 flashcards · 5 quiz questions · 4 gamesPlay free →