====== 02 Search II ======
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

===== Exercise for bonus points =====
  * Resolve the questions in the given heuristic exercise.
  * 0.5 points
  * Submit your solution to [[https://cw.felk.cvut.cz/brute/|BRUTE]] **lab02quiz** by February 27, midnight.
  * Format: text file, photo of your solution on paper, pdf - what is convenient for you.
  * Solution will be discussed on the next lab.
  * Students with their family name starting from A to K (included) have to solve and upload {{ :courses:be5b33kui:labs:weekly:heuristics_a_2023.pdf |subject A}} , while students with family name from L to Z have to solve and upload {{ :courses:be5b33kui:labs:weekly:heuristics_b_2023.pdf |subject B}}.

> {{page>courses:be5b33kui:internal:quizzes#Heuristics exercise}}


===== Completeness and optimality =====
We will discuss how to best search when we don't know how far is the goal. What does it mean that a search algorithm is  //complete, optimal//. 

==== Exercise I / Solving together ====

>  {{page>courses:be5b33kui:internal:quizzes#A forgetful traveler }}


===== Search exercise =====
Let us start with a simple graph to practice searching, as 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.