c) Repeat (a) using a breadth-first search

d) Repeat (b) using a iterative deepening search

e) Based on this experience, discuss which algorithms are best suited for this problem.

Note: For you solutions to a-d, simply provide the tree that generated by each search. Make sure to follow the up, left, right, down order as specified. Also, for the sake of consistency, label the nodes based on their row and column values in the grid. For example, the top left square in the grid would be node 11 and the bottom right square would be node 88.

3. Consider the problem of finding a path in the grid shown in Figure 3.14 from the position s to the position g. A piece can move on the grid horizontally or vertically, one square at a time. No step may be made into a forbidden shaded area. 9 Figure 3.14: A grid-searching problem (a) On the grid shown in Figure 3.14, number the nodes expanded (in order) for a depth- first search from s to g, given that the order of the operators is up, left, right, and down. Assume there is cycle pruning. What is the first path found? On a copy of the same grid, number the nodes expanded, in order, for a greedy best- first search from s to g. Manhattan distance should be used as the evaluation function. The Manhattan distance between two points is the distance in the x-direction plus the distance in the y-direction. It corresponds to the distance traveled along city streets arranged in a grid. Assume multiple-path pruning. What is the first path found? (b)