1. Draw the tree and write a number on each node according to the order that you expanded.

2. Show the status of the queue on each move.

There is a boy on the 3x3 board, and he wants to find and eat the strawberry on the same board. He has no idea where the strawberry is. He can see the strawberry only when he is in the same room with the strawberry. We will do a best-first search using a heuristic function which estimates how close each room is to the goal. As a heuristic function, we will use the Manhattan distance. The boy can move left, right, up, and down to an adjacent cell except: * he cannot move between B and C. (There is a border.) * he cannot move between E and H. (There is a border.) The cost of one move is 1 except: the cost between A and D is 5. (There is a high fence.) the cost between E and F is 5. (There is a high fence.) I Boye Strawberry I 2.1 Find the path from the initial state to the goal state through the greedy best-first search algorithm. For simplicity, you do not visit the parent node. Show the status of the queue on each move. Draw the tree and write a number on each node according to the order that you expanded. Calculate the total cost arriving in goal. If there is more than one node which has the same intermediate cost, please expand the node whose letter comes first in alphabetical order. (When you describe the queue status, please also write f value and the path from the initial node to the current node. e.g. (Just an example. It may not be correct.) Queue #0: B(f:4, path:B Be Queue #1: C(f:6, path:BC), A(f:7, path:BA) 1 ce There is a boy on the 3x3 board, and he wants to find and eat the strawberry on the same board. He has no idea where the strawberry is. He can see the strawberry only when he is in the same room with the strawberry. We will do a best-first search using a heuristic function which estimates how close each room is to the goal. As a heuristic function, we will use the Manhattan distance. The boy can move left, right, up, and down to an adjacent cell except: * he cannot move between B and C. (There is a border.) * he cannot move between E and H. (There is a border.) The cost of one move is 1 except: the cost between A and D is 5. (There is a high fence.) the cost between E and F is 5. (There is a high fence.) I Boye Strawberry I 2.1 Find the path from the initial state to the goal state through the greedy best-first search algorithm. For simplicity, you do not visit the parent node. Show the status of the queue on each move. Draw the tree and write a number on each node according to the order that you expanded. Calculate the total cost arriving in goal. If there is more than one node which has the same intermediate cost, please expand the node whose letter comes first in alphabetical order. (When you describe the queue status, please also write f value and the path from the initial node to the current node. e.g. (Just an example. It may not be correct.) Queue #0: B(f:4, path:B Be Queue #1: C(f:6, path:BC), A(f:7, path:BA) 1 ce