Question 1. Consider the search tree shown below. The numbers on the branches are the costs.
Assume that the nodes are expanded in alphabetical order when no other order is specified by the search, and that the goal is state G. What order would the states be expanded by each type of search? Stop when you expand G.
(i) Depth First:
(ii) Breadth First:
(iii) Uniform Cost Search:
Question 2. Consider the water jugs problem. You have a tap, a 5 litre bucket, and a 7 litre bucket. You need EXACTLY 4 litres of water. You may fill either bucket from the tap or the other bucket; you may empty either bucket into the drain or into the other bucket.
(i) What are the actions possible in a state where you have S litres of water in the smallbucket and L litres in the large bucket
(ii) Starting from the initial state (0, 0), draw the search tree until you reach a goal node,with 4 litres of water in one or other of the buckets.
1
(iii) Would breadth or depth first search be best to find the optimal solution? Why?
Question 3.
Below is a graph to be searched (from node S to node G). You are given a list of heuristic estimates at the states.
A=2
B=3
C=1
D=4
S=10
G=0
Break ties using alphabetical order.
Perform a best-first greedy search. Show the path to the goal.
Question 4.
We are given the following graph, where each node has an identifier and a heuristic value, while each edge has a cost.
Question 4a Show the order in which A∗ search sees nodes from S to G (goal node). For each node during the search show its f and g values. If a node is reached on multiple paths show its f and g values each time the node is reached, and indicate its parent node.
Question 4b What is the solution path found?
Question 4c Is the h function admissible? is it consistent?
Question 4d Suppose you decide to do best-first search using the following evaluation function:
f(n) = (1 −w)g(n) + wh(n)
Assuming that h(n) is admissible, what are the values of w that guarantee the algorithm will find an optimal solution?
