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?

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.

• 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 */

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.

• 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: queue and heapq (nevertheless, you can also implement it without them).

• Finish and submit to BRUTE the first optional task 01-easy-search.
• Start working on the first mandatory task 03-search.