« A* and HeSyllabus for all sect | Main | Lecture #Syllabus for all sect »

March 23, 2006

Homework Syllabus for all sect

1. R&N Problem 4.1: Trace the operation of A* search applied to the problem of getting to Bucharest from Lugoj using the straight-line distance heuristic. That is, show the sequence of nodes that the algorithm will consider and the f, g, and h score for each node. Here is the map of Romania.

The following problem from the Russell and Norvig book sketches an interesting approach to solving the TSP using branch and bound. Do not do this problem, but use the idea in question 2 below.

The traveling salesperson problem (TSP) can be solved via the minimum spanning tree (MST) heuristic, which is used to estimate the cost of completing a tour, given that a partial tour has already been constructed. The MST cost of a set of cities is the smallest sum of the link costs of any tree that connects all the cities. (a) Show how this heuristic can be derived from a relaxed version of the TSP. (b) Show that the MST heuristic dominates straight-line distance. (c) Write a problem generator for instances of the TSP where cities are represented by random points in the unit square. (d) Find an efficient algorithm in the literature for constructing the MST, and use it with an admissible search algorithm to solve instances of the TSP

2. Which MST algorithm would you recommend for addressing problem part (d) above and why? As your search progresses and the reduced cost matrix for a given search state gets filled with infinities (i.e., as the set of remaining edges shrinks), would you change your recommendation for an MST algorithm? Why?

Posted by ringger at March 23, 2006 05:45 PM

Comments

The distance from Pitesti is 100. the map given above makes it look like 10 (although it does look cut off), but according to Dr. Ringger it is 100 as stated by Russel and Norvig.

Posted by: Daniel Larsen [TypeKey Profile Page] at March 24, 2006 12:57 PM

sorry, this distance is AS THE CROW FLIES and not the actual distance, which is still 101 as stated by the map. so 101 is actual. 100 is as the crow flies. i hope that is clear.

Posted by: Daniel Larsen [TypeKey Profile Page] at March 24, 2006 12:59 PM

Post a comment

Thanks for signing in, . Now you can comment. (sign out)

(If you haven't left a comment here before, you may need to be approved by the site owner before your comment will appear. Until then, it won't appear on the entry. Thanks for waiting.)


Remember me?