Search
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:
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.