public:t-622-arti-11-1:lab_5_materials
Differences
This shows you the differences between two versions of the page.
| Both sides previous revisionPrevious revisionNext revision | Previous revision | ||
| public:t-622-arti-11-1:lab_5_materials [2011/02/08 14:01] – 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 | + | ===== Lab 5: Formulating Search Problems ===== |
| In this lab we will look at some real world problems and formulate them as **Search Problems**. | In this lab we will look at some real world problems and formulate them as **Search Problems**. | ||
| Line 8: | Line 8: | ||
| * An **Initial State**; | * An **Initial State**; | ||
| * The **Goal Test**; | * The **Goal Test**; | ||
| + | * Available **Actions**; | ||
| * The **Transition Model** (or **Successor** function); | * The **Transition Model** (or **Successor** function); | ||
| * The **Cost** function. | * The **Cost** function. | ||
| Line 14: | Line 15: | ||
| - An agricultural robot needs to plant 100 trees in a valley. | - An agricultural robot needs to plant 100 trees in a valley. | ||
| - A space probe has to find some place outside of earth for humanity to colonize. | - A space probe has to find some place outside of earth for humanity to colonize. | ||
| + | - 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. | - 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 ==== | ==== 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. | + | 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. | - 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? | - 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 | + | To play with this problem and get a feeling |
/var/www/cadia.ru.is/wiki/data/attic/public/t-622-arti-11-1/lab_5_materials.1297173670.txt.gz · Last modified: 2024/04/29 13:32 (external edit)