The above is a graph version of a road map of various cities in Romania. Questions $1$ and $2$ deal with

this graph. For this homework, the distances between cities are irrelevant. Two copies of the map are

included on the next page, if you want to print it out and write your answers on it$.$

Show the results of performing a breadth$-$first search on the graph above. Assume that the start

node is Bucharest, and the goal node is Arad. Label each node in the graph with the order in which

it was first expanded $($for example, Bucharest should be numbered $1).$ Show the final path found.

Assume that if multiple nodes are generated at the same time, they are added to OPEN so that they

will be removed in alphabetical order $($for example, Fagaras should be the second node expanded$).$

Show the results of performing a depth$-$first search on the graph above. Assume that the start node

is Bucharest, and the goal node is Hirsova. Label each node in the graph with the order in which it

was expanded $($for example, Bucharest should be numbered $1).$ Show the final path found. Assume

that if multiple nodes are generated at the same time, they are added to OPEN so that they will be

removed in alphabetical order $($for example, Fagaras should be the second node expanded$).$

The missionaries and cannibals problem is usually stated as follows. Three missionaries and three

cannibals are on one side of a river. On the same side is a boat that can hold one or two people. Find

a way to get everyone to the other side, without ever having more cannibals than missionaries on a

single side of the river. This problem is famous in Al because it was the subject of the first paper that

approached problem formulation from an analytical viewpoint $($Amarel$,1968).$

Draw a diagram of the complete state space for this problem $($this is not as large as you might think$).$

Omit states that are impossible or that violate the rules of the game. Also, only drawing each state

once will help. I suggest starting with the start state and working out from there.