October 16, 2024

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)
• queue.PriorityQueue in Python (docs.python.org)

Questions and exercises

1. 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?)
2. Why is best-first search an improvement over Dijkstra's algorithm?
3. What is the problem with using greedy best-first search?
4. In a brief definition: what makes a heuristic admissible?

Assignments

Upcoming

• Project 3: A* prep due (21 Oct)
• Homework 4 due (21 Oct)
• Project 3: A* design due (23 Oct)

Board photo

.