{{indexmenu_n>6}}

<timer 2000-01-01 00:00:01=2016-02-28 00:00:01>
The content of this page is going to be accessible from Mar 28.
</timer>

<timer 2016-02-28 00:00:01=->
====== 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.
</timer>