The Traveling Salesman Problem: Graph Implementation

Data Structures

Implementation of a graph data structure and the Traveling Salesperson problem using the standard template library; short proofs of correctness.

In this assignment the student will implement two graph representation structures (adjacency matrix and adjacency list), each inherited from a common abstract graph class, and use these as the bases for an implementation of an exhaustive search TSP solution. Students will compete for fastest implementation (as measured by the amount of nodes that can be processed in a give time limit), ideally leading them to devise branch-and-bound improvements to the exhaustive search. The students are also intended to use this as a chance to gain experience with the C++ Standard Template Library, using the Vector and List container classes as the basis for their graph representation.

Duration: The project is split in to two parts, intended to require one week each.

Background: Students are assumed to have had: at least 2.5 semesters of programming experience, including at least .5 semesters of C++; knowledge of the Vector and List STL templates; exposure to recursion and depth-first search. For the assignment the instructor will need to explain the adjacency matrix and adjacency list graph representations.

John Karro

Implementation, run-time analysis

Two Weeks

Reading, writing

Implementation, Recursion, Graphs

Suppose you are working tech. support for Starbuck’s, and have to tackle the problem of delivery truck routing. Specifically: you need to write a program that will take the location of a supply center and a list of Starbuck locations that are resupplied from that center, and produces a route that will get a truck from the supply center to each of the stores and back while driving the minimum number of miles possible (and hence, presumably, minimizing both fuel and labor costs). It turns out that writing a program to find these optimal route in polynomial time is a really difficult. However, if you are not worried about runtime then the algorithm becomes straight-forward. And really, really slow. You need to design the best tool you can, and be prepared to explain (in writing) why it works to a colleague, boss, or even to yourself.

This is an example of the Traveling Salesperson Problem, a problem that shows up (in some variation) in many important applications. If you are going to address it, you probably want to model the problem with a graph: each node represents a store location, while edges represent distance. Graphs are one of the most useful general models in Computer Science, and having the correct, efficient, implementation of the Graph ADT (along with basic functionality) is of some importance. In this assignment you will implement the two most commonly used graph data types, and on top of that write a TSP implementation.

N/A