October 11, 2023
Wednesday of Week 8
Topics of the day
- Using priority queues
- A and A*
Suggested readings
- Sections 4.2, 4.3 from George Luger, Artificial Intelligence, 5e
- Sections 4.2, 4.3 from George Luger, Artificial Intelligence, 6e
Online references
- Admissibility (en.wikipedia.org)
- A* (en.wikipedia.org)
- Dijkstra's and A* (www.redblobgames.com)
- priority_queue in C++ (en.cppreference.com)
- PriorityQueue in Java (docs.oracle.com)
Questions and exercises
- In your preferred language (not necessarily C++ or Java), how does the built-in priority queue type know how to order its contents? (That is, how does it decide what has the highest priority?)
- Why is best-first search an improvement over Dijkstra's algorithm?
- What is the problem with using greedy best-first search?
- In a brief definition: what makes a heuristic admissible?
Assignments
Upcoming
- Project 3: A* prep due (16 Oct)
- Project 3: A* design due (18 Oct)
- Homework 4 due (18 Oct)
