A* Search = Uniform Cost + Greedy
Uniform cost search expands the nodes by path cost g(n). Greedy search expands the nodes by goal estimate h(n).
h=5 h=2
h=7 2 A 5 C 12
3
h=0 G
B S 1.5
h=4
4D2
Idea: A* search expands the nodes by the sum: f(n) = g(n) + h(n)
h=0.5
A* Search
Idea: A* search expands the nodes by the sum: f(n) = g(n) + h(n)
h=5 h=2
h=7 2 A 5 C 3 h=0 A C D 12G
B S 1.5
h=4
4D2
Order of the nodes to be expanded in the frontier:
S
h=0.5
S
4=0+4
A* Search
Idea: A* search expands the nodes by the sum: f(n) = g(n) + h(n)
S
h=72 A 5 C 3 h=0 A6=1+5 C4=2+2 D4.5=4+0.5
h=5 h=2 12G
B S 1.5
h=4
4D2
G
Order of the nodes to be expanded in the frontier:
S C
h=0.5
5=5+0
4=0+4
A* Search
Idea: A* search expands the nodes by the sum: f(n) = g(n) + h(n)
h=5 h=2
h=7 2 A 5 C 3 h=0
S A6=1+5 C 4=2+2
D4.5=4+0.5
12G B S 1.5
h=4
4D2
GCG
Order of the nodes to be expanded in the frontier:
S C D
h=0.5
5=5+0 7.5=5.5+2 6=6+0
4=0+4
A* Search
Idea: A* search expands the nodes by the sum: f(n) = g(n) + h(n)
h=5 h=2
h=7 2 A 5 C 3 h=0
S A6=1+5 C 4=2+2
D4.5=4+0.5
12G B S 1.5
h=4
4D2
GCG
Order of the nodes to be expanded in the frontier:
S C
D G
h=0.5
5=5+0 7.5=5.5+2 6=6+0
4=0+4
h=3
h=0 G 1A2
A 1+4
G
4+0
Is A* optimal
S
4
h=4
What went wrong: Heuristic (goal estimate) is greater than actual
cost
A* is optimal if the heuristic <= actual cost (to a nearest goal); we call a heuristic h being admissible if it has this property.
S
0+3
h=5
S
h=1 C
A1+4
C
3+1
A* with closed list and its optimality
Closed list: maintain a list in order not to expand the nodes which have been
expanded before. 3
S
0+5
1A1 h=4
3
h=0
S
G
h=5
S
h=1 C 1A1
A1+4
C
3+1
A* with closed list and its optimality
Closed list: maintain a list in order not to expand the nodes which have been
expanded before. 3
S
0+5
h=4
h=0
C
2+1
G
6+0
G
3
SCA
h=5
S
h=1 C 1A1
A1+4
C
3+1
A* with closed list and its optimality
Closed list: maintain a list in order not to expand the nodes which have been
expanded before. 3
S
0+5
h=4
h=0
C
2+1
G
6+0
G
3
What went wrong: difference between two nodes’ heuristics is greater than the actual cost.
SCA
A* with closed list and its optimality
A* with closed list is optimal if for any two nodes a and b, h(a)‐h(b) <= actual cost of a to b; we call a heuristic being consistent if it has this property.
A* is optimal if for any node a, h(a) <= actual cost to the goal; we call a heuristic being admissible if it has this property.
Consistency is stronger than admissibility: if a heuristic is consistent, then it is admissible as well.