east, west, north and south of the cell, except that you are not allowed to pass through the thick wall
indicated by the double line. For example, the successors of cell I are H and N (and not D or J).
Trace the operation of A* search applied to the problem of getting from cell R to cell G. The heuristic
function is just the Manhattan distance, ignoring the existence of the wall. The heuristic values for each
node are summarized for you in the table to the right.
• Draw the search tree, starting from cell R. Beside each node in your tree, indicate the f, g and h scores
for the node (in the format g(n)th(n) = f(n)). Assume that the cost of each move is 1.
• To the side of your search tree, provide a list of the order in which paths are expanded. Show the
contents of the frontier after each node is expanded. To make it easier to keep track of what you are
doing, include both the f value and h value as subscripts when you write a path in your priority queue. For
example, WXY Z11,7 would indicate that WXY Z is a path such that f(WXYZ) = 11 and h(Z) = 7.
•If two or more paths are tied for the lowest f value, give priority to the one with minimum h value. Use
alphabetical order if there is still a tie.
• For this question, you can avoid generating states that have already been expanded.
For example, you should not consider going west from cell I to cell H if you had already expanded cell H in
an earlier step.
• Also, when inserting a path onto the priority queue, if a path to the same state is already on the queue,
just keep the copy with the lower f value.
A B с DE
FG HIJ
KIL M N 0
S T
WXY
la b
P Q R
U V

cell
A
B
с
D
E
F
G
H
I
J
K
L
M
h(cell) cell
N
0
2
1
2
3
4
1
0
1
2
3
2
1
2
P
Q
R
S
T
U
V
BED
W
X
Y
What is the solution path returned by the algorithm, and what is its path cost?
h(cell)
3
4
3
2
3
4
5
4
3
4
5
6
Fig: 1