Difference between revisions of "Ferryman Problem"
From Wiki Notes @ WuJiewen.com, by Jiewen Wu
(New page: The ferryman problem is popular, which has many variants. It seeks a solution to the following synopsis. A ferryman wants to take his goods, i.e., a goat, a cabbage and a wolf to the othe...) |
m (Protected "Ferryman Problem" [edit=sysop:move=sysop]) |
||
| (4 intermediate revisions by the same user not shown) | |||
| Line 1: | Line 1: | ||
| + | ==Problem Statement== | ||
The ferryman problem is popular, which has many variants. It seeks a solution to the following synopsis. | The ferryman problem is popular, which has many variants. It seeks a solution to the following synopsis. | ||
| − | A ferryman wants to take his goods, i.e., a goat, a cabbage and a wolf to the other side of a river. He can take at most one of the three things in the boat to cross the river. Note that the following pair cannot stay together unless they are under the supervision of the ferrymen: (goat, cabbage) (wolf, goat). | + | A ferryman wants to take his goods, i.e., a goat, a cabbage and a wolf to the other side of a river. He can take at most one of the three things in the boat to cross the river. Note that the following pair cannot stay together unless they are under the supervision of the ferrymen: (goat, cabbage) (wolf, goat). Otherwise, the ferrymen will lose one of them in each pair. Now we are looking for a solution for the ferryman to transport all goods to the other side without any loss. |
| − | + | To solve the problem by Model Checking, we are asked to check if a solution is possible, i.e., a decision problem requiring only YES or NO. | |
| − | + | ||
| − | + | ==Solution== | |
| + | |||
| + | |||
| + | ==Reference== | ||
| + | *[http://www.dti.unimi.it/~riccobene/MetodiFormali/smv.pdf Notes] from Elvinia Riccobene at Università di Milano. | ||
Latest revision as of 14:23, 28 January 2009
Problem Statement
The ferryman problem is popular, which has many variants. It seeks a solution to the following synopsis.
A ferryman wants to take his goods, i.e., a goat, a cabbage and a wolf to the other side of a river. He can take at most one of the three things in the boat to cross the river. Note that the following pair cannot stay together unless they are under the supervision of the ferrymen: (goat, cabbage) (wolf, goat). Otherwise, the ferrymen will lose one of them in each pair. Now we are looking for a solution for the ferryman to transport all goods to the other side without any loss.
To solve the problem by Model Checking, we are asked to check if a solution is possible, i.e., a decision problem requiring only YES or NO.
Solution
Reference
- Notes from Elvinia Riccobene at Università di Milano.
