AI · Theory

A* Search Algorithm

Theory

22/215

A* Search Algorithm

A* expands the node with smallest f = g + h. g is cost so far. h is a guess of cost to goal. If h never overestimates (admissible) and is consistent, A* finds an optimal path. Straight-line distance on a map is the classic admissible h.

If h = 0, A* becomes UCS. If h is wild and overestimates, you may get a fast but non-optimal route. Viva: write f=g+h, say admissible, give straight-line example.

A* Search Algorithm — output — S f= 7 / A f= 6 / B f= 6. Expand smallest f. Admissible h never overestimates.

Diagram

f(n) = g(n) + h(n)
  pick smallest f
  admissible h → optimal

Exam tip

f=g+h + admissible heuristic example.

Example

# A* f = g + h
g = {"S": 0, "A": 2, "B": 5}
h = {"S": 7, "A": 4, "B": 1, "G": 0}
for n in ["S", "A", "B"]:
    print(n, "f=", g[n] + h[n])

A* Search Algorithm — output: S f= 7 / A f= 6 / B f= 6. Expand smallest f. Admissible h never overestimates.

Short notes

Deff(n) = g(n) + h(n).
RuleAdmissible h → optimal.
TrapOverestimate h.

AI · Theory

A* Search Algorithm

← All stacks

Theory

22/215

A* Search Algorithm

If h = 0, A* becomes UCS. If h is wild and overestimates, you may get a fast but non-optimal route. Viva: write f=g+h, say admissible, give straight-line example.

A* Search Algorithm — output — S f= 7 / A f= 6 / B f= 6. Expand smallest f. Admissible h never overestimates.

Diagram

f(n) = g(n) + h(n)
  pick smallest f
  admissible h → optimal

Exam tip

f=g+h + admissible heuristic example.

Example

# A* f = g + h
g = {"S": 0, "A": 2, "B": 5}
h = {"S": 7, "A": 4, "B": 1, "G": 0}
for n in ["S", "A", "B"]:
    print(n, "f=", g[n] + h[n])

A* Search Algorithm — output: S f= 7 / A f= 6 / B f= 6. Expand smallest f. Admissible h never overestimates.

Short notes

Deff(n) = g(n) + h(n).
RuleAdmissible h → optimal.
TrapOverestimate h.

A* Search Algorithm

Example

Short notes

Questions

A* Search Algorithm

Example

Short notes

Questions