Give a graph presentation for the search in the farmer, wolf, goat, and cabbage problem.
| A farmer with his wolf, goat, and cabbage comes 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 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 the nodes represent states of the world, for instance, the farmer and the goat are on the west bank and the wolf and cabbage on the east. Discuss the advantages of breadth-first, depth-first, depth bounded depth-first, and iterative deepening for searching this space.
The sliding-tile puzzle consists of three black tiles, three white tiles, and an empty space in the configuration
| B | B | B | W | W | W |
The puzzle has two legal moves with associated costs: