====== 03 Search I ======
How to search when we do not know how far is the goal. What does it mean that an algorithm is //complete, optimal//?

  * discussion on the first assignment
  * AI-gym works for everyone?
  * Quiz

===== search exercise =====
Let us start with a simple graph to practice searching. It is easier to debug and understand. The lecture example you can try out here: {{ :courses:b3b33kui:cviceni:program_po_tydnech:kuigraphs.py |''kuigraphs.py''}}. 

The basic communication is the same as for ''kuimaze''. I.e.:
<code python>
import kuigraphs
env = kuigraphs.KuiGraph()
observation = env.reset()
states_with_costs = env.expand(state) # list of tuples ('a',1)
env.set_path(path)
</code>

''state'' is a letter like in the lecture: 'S', 'a', ... 'G'. Try out some search strategies. If you write them generally enough, your code will work also in the following case:
<code python>
env = kuimaze.InfEasyMaze()
</code>

Think a little bit about the types of data structures you will need.

> {{page>courses:b3b33kui:internal:cviceni:tyden_02#programming}}

===== maze search =====
In the environment from [[courses:be5b33kui:labs:search:start|Search]] program an algorithm that will find the cheapest path. Do not forget that changing positions does not have to cost the same in every case.