No doubt you remember the campus tour—the walking backwards, the explanation of meal plans, the intramural sports speech... It's a fine tradition, but the admissions department is running out of willing volunteers. That's where you come in–you've been asked to write a program to calculate tours for campus visitors.
It should accept a list of predefined 'tours', such as a 'Campus Art Tour' or a 'Freshman Dorm Tour'. These tours will be supplied by the Admissions Office. If a stop appears multiple times in the list, it need only be visited once.
Unlike normal tours, these tours have no fixed order. Your program should simply move toward the closest unvisited selected stop, even if this results in tours being interleaved.
Locations in the map will be represented by the
Loc includes its name and location, as well as its neighbors and the distances
in meters to those neighbors. Every location will have a unique, unambiguous name.
(define-type Loc [loc (name : string) (latitude : number) (longitude : number) (neighbors : (listof Loc)) (distances : (listof number))])Tours will be represented by the
Tourstores the name of a tour and a list of its stops' names.
(define-type Tour [tour (name : string) (stops : (listof string))])
The Admissions Office wants a program that provides the following tour-calculating function:
(tour-guide (tours : (listof Tour)) (start-lat : number) (start-lon : number)) : (listof string)
tour-guideproduces a list of location names to walk through, ordered from first to last (including intermediate sites like street corners), to complete the given tours according to the specifications above. Since the user might not begin their tour standing at a site on the map, your
tour-guideshould first find the site closest to the starting position, and then continue to the nearest selected tour stop. Remember, you will be outputting a single path that visits all stops in all the selected tours.
The map data you receive will contain many sites that are not tour stops, such as intersections and intermediate landmarks. All map sites, together with the paths between them, form a graph.
In order to find routes of map sites, your program will need
to find shortest paths on a weighted graph. You should use Dijkstra's
algorithm to take in a starting location from the map and
return a collection of information about each site, including
the length of the shortest path from the starting site to
the current site, and the previous site along that path.
Your implementation of Dijkstra's algorithm should have the
following contract, where
'm is a type with the
above site information:
(dijkstra (start : Loc)) : collection of 'm
dijkstra should run in O([s -> s * log s]) time,
where s is the number of vertices in the graph.
Note that a complete graph (with an edge between every pair of vertices) would
have (s(s-1))/2 edges, making this impossible.
However, graph representations of real maps are not so densely connected,
and you may assume that each vertex has only some constant number of neighbors.
In addition to the types
described above, mapdata.rkt contains the following definitions and helper
loc-list : (listof Loc)
loc-listprovides a complete list of all the locations on the Brown map that your program will be processing.
tours : (listof Tour)
toursprovides a list of the tours from the Admissions Office.
(get-dist (latA : number) (lonA : number) (latB : number) (lonB : number)) : number
get-disttakes the latitude and longitude of two locations, and returns the approximate distance in meters between them.
(get-loc (name : string)) : Loc
loc-listwith the given name.
(oracle (guide : ((listof Tour) number number -> (listof string)))) : booleanConsider what criteria you might test to consider a tour-guide result to be a valid tour and how you might test its optimality by using a brute-force search instead of Dijkstra's algorithm.
tour-guidefunctions. Show your work, as always!
tour-guidealways visits nearest unvisited selected stop. Is this optimal? That is, does this algorithm create the shortest path visiting all the selected tour stops? If so, explain why this is true. If not, provide a counter-example.
tour_guide.rkt, which contains your implementation of the entire Tour Guide program.
analysis.pdf, which has your answers to the analysis questions
Your analysis must be in a