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 other 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   cab 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