Give the graph representation for the farmer, wolf, goat, and cabbage problem: A

Question

Give the graph representation for the farmer, wolf, goat, and cabbage problem:

A farmer with his wolf, goat, and cabbage come to the edge of a river they wish to cross. There is a boat at the river's edge, but of course, only the farmer can row. The boat also can carry only two things (including the rower) at a time. If the wolf is ever left alone with the goat, the wolf will eat the goat; similarly, if the goat is left alone with the cabbage, the goat will eat the cabbage. Devise a sequence of crossings of the river so that all four characters arrive safely on the other side of the river.

Let nodes represent states of the world; e.g., the farmer and the goat are on the west bank and the wolf and cabbage on the east. Discuss the advantages of breadth-first and depth-first search for this problem.

This problem needs to be in a breadth-first and depth-first search GRAPH!!!

Explanation / Answer

Each state is a four-tuple <F,W,G,C>, where each element is either n or f to indicate if the farmer,
wolf, goat or cabbage is on the near or far side of the river. (4 marks) The initial state is
<n,n,n,n>. (2 marks) A state is a goal iff it is the state <f,f,f,f>. (2 marks) There are four operators,
to represent the farmer rowing across the river with the wolf, goat, cabbage, or with the boat
empty. In what follows, if X is n then -X denotes f, and if X is f then -X denotes n.
RowG: maps <F,W,G,C> to <F,W,G,C> where F=-F, W=W, G=-G and C=C, provided F=G
RowW: maps <F,W,G,C> to <F,W,G,C> where F=-F, W=-W, G=G and C=C, provided F=W
RowC: maps <F,W,G,C> to <F,W,G,C> where F=-F, W=W, G=G and C=-C, provided F=C
RowE: maps <F,W,G,C> to <F,W,G,C> where F=-F, W=W, G=G and C=C.
All operators also have two additional preconditions:
Not( W=G & W neq F)
Not( G=C & G neq F)

In general, BFS is better for problems related to finding the shortest paths or somewhat related problems. Because here you go from one node to all node that are adjacent to it and hence you effectively move from path length one to path length two and so on.

While DFS on the other end helps more in connectivity problems and also in finding cycles in graph(though I think you might be able to find cycles with a bit of modification of BFS too). Determining connectivity with DFS is trivial, if you call the explore procedure twice from the DFS procedure, then the graph is disconnected (this is for an undirected graph).

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.