Differences

This shows you the differences between two versions of the page.

--- public:t-622-arti-11-1:lab_5_materials [2011/02/08 13:25] – angelo
+++ public:t-622-arti-11-1:lab_5_materials [2024/04/29 13:33] (current) – external edit 127.0.0.1
@@ Line 1: / Line 1: @@
-===== Lab 5: Formulating Search Problems (Warning: work in progress) =====
+===== Lab 5: Formulating Search Problems =====
 In this lab we will look at some real world problems and formulate them as **Search Problems**.
@@ Line 5: / Line 5: @@
 ==== 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:
+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;
+  * An **Initial State**;
-  * The Goal Test;
+  * The **Goal Test**;
-  * The Successor function;
+  * Available **Actions**;
-  * The Cost function.
+  * The **Transition Model** (or **Successor** 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.
+  * 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:
-  - You have to color a planar map using only four color, in such a way that no two adjacent regions have the same color.
+  - An agricultural robot needs to plant 100 trees in a valley.  The trees should be at least 1 m apart and should generally stand in a flat area if possible.  The robot carries all the trees in a large container on its back;
-  - A 3-foot-tall monkey is in a room where some bananas are suspended from the 8-foot ceiling. He would like to get the bananas. The room contains two stackable, movable, climbable 3-foot-high craters.
+  - A space probe has to find some place outside of earth for humanity to colonize.  It reports that humans want to be able to choose from at least 3 habitable places. The humans have also set the condition that they do not want to travel longer than absolutely necessary;
-  - You have a program that outputs the message "Illegal input record" when fed a certain file of records where one of the records is illegal. You know that processing of each record is independent of the processing of other records. You want to discover which record is illegal.
+  - You start with a sequence ABABAECCEC, or in general any sequence made from A, B, C and E. You can transform this sequence using the following equalities: AC = E, AB = BC, BB = E and E//x// = //x// for any //x//. For example, ABBC can be transformed into AEC, and then AC, then E. Your goal is to produce the sequence E.
   - 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.
-==== Discussion ====
+==== Extra Discussion ====
-If we have time, we'll also look at the missionaries and cannibals problem from problem 3.9. 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.
+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.
   - Formulate the problem precisely, making only those distinctions necessary to ensure a valid solution. Draw a diagram of the complete state space.
   - 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
+To play with this problem and get a feeling of it, take a look at an interactive version online: http://www.learn4good.com/games/puzzle/boat.htm