oblem $1$ Formulating A Searching Problem $(20$ marks$)$

Consider a famous problem in AI$,$ the missionaries and cannibals problem, which is stated

as follows. Three missionaries and three cannibals are on one side of a river, along with

a boat that can hold one or two people. The task is to get everyone to the other side of

the rivier, but you cannot leave a group of missionaries in one place outnumbered by the

cannibals in the same place.

$($a$)(6$ marks$)$ Formulate the problem into a search problem. Define precisely its state

space, the initial state, the goal state, and all possible actions.

$($b$)(10$ marks$)$ Draw the complete state space according to your formulation.

$($c$)(4$ marks$)$ Which search algori