Thursday, October 4, 2012

Missionaries and Cannibals problem in AI

Missionaries and   Cannibals problem     is very famous      in  Artificial  Intelligence because    it was the   subject of   the first paper     that approached       problem formulation   from an analytical viewpoint.     The problem   can be stated   as follow.   Three missionaries   and three cannibals are on one side of a river, along with a boat that can hold one or two people. Now we have   to find   a   way to   get everyone   to the   other side,   without ever   leaving a   group of missionaries in one place outnumbered by the cannibals in another side. The above problem can be solved   by a   graph search   method.   Here   I   represent the   problem as   a   set of   states and operators. States are snapshots of the world and operators are those which transform one state into another state. States can be mapped to nodes of a graph and operators are the edges of the graph.
Missionaries and   Cannibals can be solved by using different search algorithms like Breadth first and   Depth first   search algorithm to   find the solution. The   node   of   the   graph   to   be   searched   is   represented   by  a   state   space.   Each   state space can be represent by