PA7 The Traveling Salesman Problem
PA7 The Traveling Salesman Problem
Due: Monday, December 5th, 11:59PM
QQ1703105484
Submission:
-
PA11Main.java - the main program
seriously, for the autograder
- DGraph.java - a weighted directed graph
- README.md - results of timing experiments
Overview
The traveling salesman problem (TSP): given a set of cities and the distances between each, what is the shortest path that visits each city once and returns to the starting city? The problem is usually modeled with a weighted graph and has been studied extensively. The solution involves making a decision about which city to visit next and as such it belongs to a large class of combinatorial optimization problems that can be solved by searching for the optimal answer. The time complexity of such a search is exponential and only problems of modest size can be solved. Applications of the TSP include: vehicle routing, scheduling, integrated circuit design, DNA sequencing and the tracking of stars. This assignment involves the implementation of a program to experiment with some basic solutions to the TSP and to time their performance.
Assignment
A program is needed to take as input a directed weighted graph which represents a network of cities in a TSP. The graph is stored in a file and the filename is given to the program as a command line argument. The input files are in the matrix market (.mtx) format. An example input file is:
%%MatrixMarket matrix coordinate real general
| 3 | 3 | 6 |
| 1 | 2 | 1.0 |
| 2 | 1 | 2.0 |
| 1 | 3 | 3.0 |
| 3 | 1 | 4.0 |
| 2 | 3 | 5.0 |
| 3 | 2 | 6.0 |
Also provided on the command line is a directive to indicate which algorithm should be used to solve the TSP and when timing should be performed:
HEURISTIC - an approximate algorithm that uses a heuristic, BACKTRACK - an exact algorithm that uses brute-force search,
MINE - a variation on the heuristic and backtracking approaches that improves performance, TIME - a measuring of the running time of the above approaches.
An example of the output for the above input file using the HEURISTIC command is:
cost = 10.0, visitOrder = [1, 2, 3]
The assignment can be partitioned into five main tasks:
- The Graph
A weighted directed graph is needed to represent the ‘cities’ and their distances. The graph should support operations that will be needed by the algorithms, mainly a method to find all vertices that are adjacent to a given vertex. The graph class should be in DGraph.java.
|
|
- The Heuristic Approach
A simple way to arrive at an approximate solution to the TSP is to traverse the graph and at each vertex that you arrive at, make a decision about which way to go based on the weights of the incident edges. A simple ‘heuristic’ or rule-of-thumb is to take the edge of lowest weight.
The heuristic approach can be implemented as a method in the DGraph class.
|
" |
- The Backtracking Approach
it a method in the DGraph class
Recursive backtracking is a general approach to solving problems that can be represented with a graph. It involves exploring a possible solution, recording its value, and then backing up to the previous vertex to make a different decision and record the value of that solution, and so on.
The backtracking approach can be implemented as a method in the DGraph class.
this also means you really, really should
-
Your Own Variation"
make it a method in the DGraph class
|
|
- Timing
The output for the TIME command should look as follows: heuristic: cost = 935.3299999999999, 0 milliseconds
mine: cost = 935.3299999999999, 0 milliseconds
backtrack: cost = 835.8799999999999, 5 milliseconds
obviously
Grading Criteria
Testcases are provided for this PA. There will also be private grading testcases.
You are encouraged to write your own JUnit testcases to ensure your classes work properly, but these test files will not be collected or graded.
Your grade will consist of similar style and code clarity points as in earlier assignments.