====== 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_2024.pdf |subject A}} , while students with family name from L to Z have to solve and upload {{ :courses:be5b33kui:labs:weekly:heuristics_b_2024.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 =====

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.



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