Q$2.(3$p$)$ Use depth$-$first search to solve the classic river crossing problem. In the missionaries and cannibals

problem, three missionaries and three cannibals must cross a river using a boat which can carry at most

two people, under the constraint that, for both banks, if there are missionaries present on the bank,

they cannot be outnumbered by cannibals $($if they were, the cannibals would eat the missionaries$).$

The boat cannot cross the river by itself with no people on board. How many crossings are needed to

carry all missionaries and all cannibals across the river. Q$3.(4$p$)$ A simple sliding$-$tile puzzle consists of $3$ numbered tiles and an empty space. The puzzle has two

legal moves with associate costs: $($i$)$ A tile may move into an adjacent empty location. This has a cost

of $1.($ii$)$ A tile can move over one other tile into the empty position. This has a cost of $2.$ The start

and goal positions are given below. Set up a state$-$space search formulation for this puzzle:

a$)$ Specify the form of state descriptions, the starting state, and the goal state for this problem.

b$)$ Name the operators on states and describe what each operator does to a state description.

c$)$ Propose a heuristic function hat$(h)$ for solving this problem.

d$)$ Use the $A^{*}$ algorithm to find a solution path using your heuristic function. You can either show

the search tree or the state of the priority queue as $A^{*}$ progresses.

e$)$ Is your solution path optimal? Give a formal argument.$[$Q$4.](6$p$)$ In this question you will use three informed search algorithms to find the path between $A$

and $G$ in the graph below: $($a$)$ Uniform Cost Search, $($b$)$ Best$-$first Search, and $($c$)A^{*}$ search.

Note that the edges are marked by the path cost $g$ and the nodes by the heuristic cost $h$ from the node

to the goal $G.$ For each algorithm you should show the content of the fringe and the closed list at each

step of the algorithm. Note that the fringe should contain paths, rather than nodes.