For the Man, Cabbage, Goat, Wolf problem: a) List all the invalid states for thi
ID: 3858168 • Letter: F
Question
For the Man, Cabbage, Goat, Wolf problem:
a) List all the invalid states for this problem, that is, in which the goat is left alone with the cabbage, or the wolf is left alone with the goat.
b) Give the shortest sequence of steps that solves the MCGW problem.
c) Give the sequence of state representations that correspond to your solution starting with (E,E,E,E) and ending with (W,W,W,W).
d) There is an alternate means of representing states. Rather than a sequence representation, a set representation can be used.
In this representation, if an item is on the east side of the river, its symbol is in the set, and if on the west side, the symbol is not in the set as shown below, {M,C,G,W}—all items on east side of river (start state) {C,W}—cabbage and wolf on east side of river, man and goat on west side { }—all items on the west side of the river (goal state) Give the sequence of states for your solution to the problem using this new state representation.
Explanation / Answer
The answer is as follows:
a) Invalid states are as follows:
1.The goat and cabbage together with man and wolf to the other side
2.The goat and wolf together with the man and cabbage on the other side
3.The goat, wolf and cabbage together with Man on the other side.
b) Shortest sequence of steps to solve:
1.Man takes goat with him to other side
2.Man comes back and carry the cabage to the other side.
3.Man brings back goat and leaves the cabbage to the other side
4.Man caries the wolf to other side
5.Man comes back and carries the goat.
c) The states consisting of occupants on both side of the river is as follows:
1.E:MCWG
W:
2.E:CW
W:MG
3.E:CW
W:MG
4.E:CWM
W:G
5.E:W
W:GCM
6.E:WMG
W:C
7.E:G
W:CWM
8.E:GM
W:CW
9.E:
W:CWMG
d) As per the new approach states are as follows:
(MCWG)---->(CW)--->(MCW)---->(W)----->(MWG)---->(G)---->(MG)--->()