Estimate the size of the state space, Computer Engineering

1. The missionaries and cannibals problem. Three missionaries and three cannibals are on the left river bank, with a boat that can hold one or two people. If on either side of the river or in the boat the number of cannibals exceeds the number of missionaries, the cannibals will eat the missionaries. There are no other people involved, and any use of the boat must include at least one person. Finally, after each river crossing, all persons in the boat are required to disembark the boat and step onto the river bank; thus, the requirement on the numbers of missionaries and cannibals must be satis ed after each river crossing. The problem is to nd a way for everyone to get safely from the left to the right river bank.

a. Formulate the problem precisely, and estimate the size of the state space.

b. Solve the problem optimally using an appropriate search algorithm. Is it a good idea to search for repeated states?

c. Why do you think people have a hard time solving this problem, given that the state space is so simple?

 

Posted Date: 3/19/2013 2:59:53 AM | Location : United States







Related Discussions:- Estimate the size of the state space, Assignment Help, Ask Question on Estimate the size of the state space, Get Answer, Expert's Help, Estimate the size of the state space Discussions

Write discussion on Estimate the size of the state space
Your posts are moderated
Related Questions
Static RAM: No refreshing, 6 to 8 MOS transistors are needed to form one memory cell, Information stored as voltage level in a flip flop. Dynamic RAM: Refreshed periodically, 3

Explain the term Overlays. An overlay is an element of program that has the same load origin as several other part of the program. These are used for reduce the main memory req

In RDBMS, what is the efficient data structure used in the internal storage representation? B+ tree. Because in B+ tree, all the data is kept only in leaf nodes, that makes sea

Q. Show the Divide and Conquer approach? Divide and Conquer approach is the way of making a complicated problem easier.  In this approach larger problem (System) is divided int

Define BCD. A binary code that distinguishes between 10 elements must contain at least 4 bits, but 6 combinations will remain unassigned. Numerous dissimilar codes can be obtai

Advantages of DDa algorithms for line drawimg

Given a RAID 3 (bit-interleaved parity) with k disks, how well will large block transmits work? How well will it handle a high I/O request rate? Compare the performance to a one di

The Towers of Hanoi Problem Towers of Hanoi problem is described. There are three pegs on which disks are "threaded" (there are holes in the disks to allow them to be placed on

Expalin the History Of Parallel Computers The researches with and implementations of use of the parallelism started long back in the 1950's by IBM Corporation. The IBM STRETCH

Hashed strings can often be deciphered by 'brute forcing'. Bad news, eh? Yes, and particularly if your encrypted passwords/usernames are floating around in an unprotected file some