Warning

Searching a State Space – Uninformed Search

A Guide for the Seminar

Authors: Milan Rollo, Eduard Semsch, Štěpán Urban, Viliam Lisý a Petr Benda
Edit: Tibor Strašrybka

Goals

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

A maze

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:

• 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

Cannibals and Missionaries

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.

States specification

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

Water juggling

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.

Loyd’s eight

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.