{{indexmenu_n>6}}
The content of this page is going to be accessible from Mar 28.
====== 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// \\ //Translator: Radek Píbil// \\ //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.)//
{{:courses:a3b33kui:cviceni:obrazky:06_obr1.png?800|Map of a maze - initial state}}
=== Task ===
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.
{{:courses:a3b33kui:cviceni:obrazky:06_obr2.png?800|Map of a maze - expanded nodes}}
X – closed O – open
===== Additional tasks =====
==== 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)
{{:courses:a3b33kui:cviceni:obrazky:06_obr3.png?800|State space}}
//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.