CS计算机代考程序代写 A* Search = Uniform Cost + Greedy

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.