Warning

This page is located in archive.

A Guide for the Seminar

*Authors: Milan Rollo, Eduard Semsch, Štěpán Urban, Viliam Lisý a Petr Benda*

*Translator: Radek Píbil*

*Edit: Tibor Strašrybka*

Practice the solutions presented in the lectures and explain concepts like state space, state, state operator, state expansion and theory of complexity using examples.

You are given a map of the maze. Black squares are inaccessible. The task is to plan a path from square A to square B (or C). *(Grey squares have a meaning in the seminar aimed at informed search.)*

Find a path from square A to square B using the following algorithms:

- Breadth-first search
- Depth-first search
- Iterative deepening depth-first search

*For each of the algorithms, say whether are complete, finite, optimal and what is their respective time and space complexity.*

Here, we have the same situation for depth-first search with a different order of node expansion. The returned path is not the shortest one. Compare it with the previous example.

X – closed O – open

A group of 3 cannibals and 3 missionaries reach a river and have to cross it. They have a ship with a two-person capacity at their disposal. If there are more cannibals on the river bank than missionaries, then cannibals overpower and eat the missionaries. Propose a solution to get all the missionaries and cannibals to the other river bank.

s = (# of cannibals on the right river bank, # of missionaries on the right river bank, ship location, # of cannibals on the left river bank, # of missionaries on the left river bank)

*State space*

You have 2 empty vessels of 3 and 4 litre volumes that are not labelled – you do not know which is which – and an unlimited source of water. The goal is to reach a state with one of the vessels containing 2 litres of water.

You have a 3-by-3 game board and 8 labelled stones. You begin with a random distribution of stones over the board. The final state is characterised by each of the stones being assigned to their respective squares.

courses/ae3b33kui/seminars_and_labs/06.txt · Last modified: 2016/03/03 10:36 by saifueli