Performance and Test, Spring 2008 : Episode 4.2
Subject: Shortest Paths
Text : RS 21.0, 21.1 until p.288 including (without path relaxation), 21.2 + handout from RN (S. Russell and P. Norvig. Artificial Intelligence. A Modern Approach.) [35pp, 4h]
Prerequisites: graphs and graph traversals, asymptotic complexity, basic data structures (lists, arrays), hash tables.
Comment : Chapter 21 assumes some knowledge from earlier chapters. Basic notions (like digraph and a weighted digraph) are defined in RS 17.1. If you need more explanation on how these are realized in Java then review RS 19.1 and 20.1. In chapter 21 our main focus is to appreciate various applications of shortest paths algorithms, and to understand how Dijkstra's algorithm works. The description of this algorithm suffers from many references to earlier chapters, which we have not studied. Please either study the referenced stuff (if you are keen on it), or ignore references (more expected). The most important description is hidden in Program 21.1 p. 298 in RS.
Download: Lecture and Dijkstra-demo
In the RN handout you want to understand the A* algorithm, and the requirements for the heuristics function (admissability and consistency).
RS exercise 21.4 p. 284
RS exercise 21.20 p. 302
RS exercise 21.25 p. 302, perhaps just design the algorithm and describe it in pseudocode.
[RN exercise 4.5 p. 134] We saw on page 96 [in RN] that the straight-line distance heuristic leads greedy best-first search astray on the problem of going from Iasi to Fagaras. However, the heuristic is perfect on the opposite problem: going from Fagaras to Iasi. Are there problems for which the heuristic is misleading in both directions?
RS exercise 21.27 p. 303. Instead of implementing the class, design the algorithm that computes the sensitivity matrix mentioned in the exercises, describe it and analyze the asymptotic complexity of your algorithm.
|
|
|
|
Last updated Feb 28, 2008 11:25Dan Witzner Hansen, Kristian Støvring |