====== 02 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?
  * Search Exercise

===== 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.

> Students should think about representation of Nodes in search Trees, and how to implement ''Node'' and ''NodeList'' classes that permit to create and manipulate Nodes.

++++ For teacher: |
Exemple solution is in ''easy_search_agents.py'' of kui-maze repository.
++++


===== Search programming =====

  * The following Python libraries may help you for searches in a tree: [[https://docs.python.org/3/library/queue.html|queue]] and [[https://docs.python.org/3.6/library/heapq.html|heapq]].


===== Maze search: 1st mandatory assigment =====
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.