Missionaries and Cannibals Problem - Solving

Solving

Amarel devised a system for solving the Missionaries and Cannibals problem whereby the current state is represented by a simple vector . The vector's elements represent the number of missionaries on the wrong side, the number of cannibals on the wrong side, and the number of boats on the wrong side, respectively. Since the boat and all of the missionaries and cannibals start on the wrong side, the vector is initialized to <3,3,1>. Actions are represented using vector subtraction/addition to manipulate the state vector. For instance, if a lone cannibal crossed the river, the vector <0,1,1> would be subtracted from the state to yield <3,2,0>. The state would reflect that there are still three missionaries and two cannibals on the wrong side, and that the boat is now on the opposite bank. To fully solve the problem, a simple tree is formed with the initial state as the root. The five possible actions (<1,0,1>, <2,0,1>, <0,1,1>, <0,2,1>, and <1,1,1>) are then subtracted from the initial state, with the result forming children nodes of the root. Any node that has more cannibals than missionaries on either bank is in an invalid state, and is therefore removed from further consideration. The valid children nodes generated would be <3,2,0>, <3,1,0>, and <2,2,0>. For each of these remaining nodes, children nodes are generated by adding each of the possible action vectors. The algorithm continues alternating subtraction and addition for each level of the tree until a node is generated with the vector <0,0,0> as its value. This is the goal state, and the path from the root of the tree to this node represents a sequence of actions that solves the problem.

Read more about this topic:  Missionaries And Cannibals Problem

Famous quotes containing the word solving:

    “Science is a dynamic undertaking directed to lowering the degree of the empiricism involved in solving problems; or, if you prefer, science is a process of fabricating a web of interconnected concepts and conceptual schemes arising from experiments and observations and fruitful of further experiments and observations.”
    —James Conant (1893–1978)

    “There are horrible people who, instead of solving a problem, tangle it up and make it harder to solve for anyone who wants to deal with it. Whoever does not know how to hit the nail on the head should be asked not to hit it at all.”
    —Friedrich Nietzsche (1844–1900)

    “If we parents accept that problems are an essential part of life’s challenges, rather than reacting to every problem as if something has gone wrong with universe that’s supposed to be perfect, we can demonstrate serenity and confidence in problem solving for our kids....By telling them that we know they have a problem and we know they can solve it, we can pass on a realistic attitude as well as empower our children with self-confidence and a sense of their own worth.”
    —Barbara Coloroso (20th century)