====== 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//?

===== Learning outcomes =====
After this lab session, a student
  * recognizes a discrete search problem, identifies states and actions, and evaluates a candidate plan;
  * understands the concepts of //complete// and //optimal// search algorithm;
  * understands why the search algorithm needs to remember the visited states;
  * can distinguish between a state in the search space and a node in the search tree;
  * understands data structures suitable for the implementation of A* algorithm.


===== Program =====
  * Discussion on the first assignment
  * Quiz from the last week: flight plan (discussion, solution)
  * Exercise: Forgetful traveler
  * Data structures for A* implementation
/*   * Quiz for the next week: heuristics */



===== 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 programming =====
  * How does a //state// differ from a //node//?
  * Think about the types of data structures you will need. How can you implement a ''Node'', and maybe a ''NodeQueue''?
  * The following Python libraries may help you implement the A* algorithm: [[https://docs.python.org/3/library/queue.html|queue]] and [[https://docs.python.org/3.6/library/heapq.html|heapq]] (nevertheless, you can also implement it without them).


/*
===== Bonus quiz: heuristics =====
  * Resolve the questions in the given heuristic exercise.
  * 0.5 points
  * Submit your solution to [[https://cw.felk.cvut.cz/brute/|BRUTE]] **lab02quiz**, deadline in BRUTE.
  * Format: text file, photo of your solution on paper, pdf - what is convenient for you.
  * Solution will be discussed on the next lab.
  * Solve and upload the right version according to the first character of your family name:
    * family name starting from A to L:  {{ :courses:be5b33kui:labs:weekly:heuristics_a_2025.pdf |version A}}
    * family name starting from M to Z:  {{ :courses:be5b33kui:labs:weekly:heuristics_b_2025.pdf |version B}}.

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

===== Homework =====
/*  * Finish and submit to BRUTE the ''lab02quiz''. */
  * Finish and submit to BRUTE the first optional task ''01-easy-search''.
  * Start working on the first mandatory task ''03-search''.