User Tools

Site Tools


public:t-622-arti-11-1:lab_5_materials

This is an old revision of the document!


Lab 5: Formulating Search Problems (Warning: work in progress)

In this lab we will look at some real world problems and formulate them as Search Problems.

Group work

We will start by splitting the class into several groups. Each group should formulate the following problems (all) as search problems by giving:

  • An Initial State;
  • The Goal Test;
  • The Successor function;
  • The Cost function.

You don't need to write any code, but describe these things precisely enough so that they could be implemented. You will have 15-20 minutes (total) to discuss all the problems and formulate them. After this time, each group will present their solution to one problem (picked randomly) and discuss it with the class.
These are the problem descriptions:

  1. You have three jugs, measuring 12 gallons, 8 gallons, and 3 gallons, and a water faucet. You can fill the jugs up or empty them out from one to another or onto the ground. You need to measure out exactly one gallon.

Extra Discussion

If we have time, we'll also look at the missionaries and cannibals problem. 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 find a way to transport everyone to the other side, without ever leaving a group of missionaries in one place outnumbered by cannibals in that place, because then the missionaries will be eaten.

  1. Formulate the problem precisely, making only those distinctions necessary to ensure a valid solution. Draw a diagram of the complete state space.
  2. Why do you think people have a hard time solving this puzzle, given that the state space is so simple?

To play with this problem and get a feeling for it, have a look at an interactive version online: http://www.learn4good.com/games/puzzle/boat.htm

/var/www/cadia.ru.is/wiki/data/attic/public/t-622-arti-11-1/lab_5_materials.1297171764.txt.gz · Last modified: 2024/04/29 13:32 (external edit)

Donate Powered by PHP Valid HTML5 Valid CSS Driven by DokuWiki