### Introduction to AI - Worksheet 8

#### EXERCISE: 1

Uninformed Search (taken from [Luger 2004]) 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.

#### EXERCISE: 2

Informed Search (taken from [Luger 2004]) The sliding-tile puzzle consists of three black tiles, three white
tiles, and an empty space in the configuration

The puzzle has two legal moves with associated costs:

- A tile may move into an adjacent empty location. This has cost
1.
- A tile can hop over one or two other tiles into the empty
position. This has a cost equal to the number of tiles jumped over.

The goal is to have all the white tiles to the left of all the black
tiles. The position of the blank is not important.

- Analyse the state space with respect to complexity and looping.
- Propose a heuristic for solving this problem. How do greedy
search and the A
^{*}-algorithm perform with your heuristic. Are
the algorithms admissible (that is, are they guaranteed to find a
minimal path to the solution)?

#### EXERCISE: 3

Why may the A^{*}-algorithm miss the optimal solution if the
heuristic function h is not optimistic?

© Noel Welsh & Manfred Kerber, 2004, Introduction to AI

16.11.2004

The URL of this page is ftp://ftp.cs.bham.ac.uk/pub/authors/M.Kerber/Teaching/AI/e8.html.

URL of module http://www.cs.bham.ac.uk/~mmk/Teaching/AI/