Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
Assignment
You will be solving the traveling salesman problem using three different ways: recursive
backtracking, heuristic, and your own approach.
To use the program, you (or us when grading) will need to put two command line arguments into your program:
PathTo/infile.mtx [HEURISTIC, BACKTRACK, MINE, TIME]
The input files are in the same format as the matrix market format used by the SuiteSparse
Matrix Collection. More importantly, see this link for a description of the .mtx format. You
can write code similar to this link to read in the .mtx format. Here is an example input file:
%%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
Example output to standard out is provided in the PublicTestCases/ for HEURISTIC and
BACKTRACK. Here is the output for the above input file and the HEURISTIC command:
cost = 10.0, visitOrder = [1, 2, 3]
You will be running your own algorithm with the MINE command. The output for time
is shown later in this spec.
This assignment is broken down into parts. You will need to understand recursive backtracking clearly, before finishing that part. I expect you to finish reading in the .mtx file into
a graph data structure, and the heuristic part of the assignment in the first week. Then in
the second week, all that is left to do is to finish the recursive backtracking, mine, and time
commands.
There is pseudocode in this spec. As with the last assignment (pseudocode from the lecture), it is crucial that you understand how the pseudocode works, what it is doing, and why
it is doing what it is doing before actually writing the code for it, or else you will be lost. Not
to mention it will be very difficult to improve upon an algorithm that you do not understand
well.
Part One: DGraph
Before you can run algorithms on a graph, you need a graph. The first part of this assignment
will be reading in a .mtx file and converting the file into a code representation of a graph.
You will need to fill in certain methods and fields in the DGraph.java file. This file exports a
2
class called DGraph. This class will store all necessary information about the graph. See the
DGraph.java file in the starter code for a list of methods to fill in. You should extensively test
this class before moving on. Lingering bugs in the DGraph class will make debugging the
later part of the assignment nearly impossible.
With your DGraph class working, it is time to write code to read in a .mtx file and store it
properly into your DGraph class. This should be done in PA11Main.java. File format descriptions are listed above in the ’Assignment’ section. Additionally, we have provided testcases
and their corresponding .dot files. These files will be a great testing tool. There are many
graph visualizers on the web that accept a .dot file and show you a visualization of the graph.
For instance, check out the example.mtx file and then use an online .dot visualizer to view
the example.mtx.dot file as a visual graph to understand this file format. The starter code we
gave you has methods that will build the dot file as a string for you. I just used this site which
happened to be the first google result for me.
Part Two: Heuristic
Below is the pseudocode we expect you to follow for the HEURISTIC command. If you have
ideas on how to improve it, great, save those for the MINE command. Note now would be a
good time to review Trip.java which was given as part of the starter code.
create a trip
choose city 1 first, call it the current city
for k=2 to numNodes inclusive
for each neighbor of the current city
find the neighbor that is available AND the closest to the current city
choose the closest city that is available for the trip
call that closest city the current city
Part Three: Recursive Backtracking
We will make the decisions starting with node 1 and continuing through the nodes in order.
Every time a node is chosen, that choice will be checked before recursing to do some pruning.
We cannot stop at the first node we find, because it is possible that paths through other nodes
will cost less.
create a trip
choose city 1 first
call backtrackingFunction on the trip
backtrackingFunction( graph data structure, current trip so far,
min trip previously found )
if all nodes are in trip then
3
process the current trip:
does it have less cost than min trip?
if so then modify min trip previously found (hint: copyOtherIntoSelf())
return
if trip so far has less cost than the min trip previously found
for each city x of the cities left
choose x next
backtrackingFunction( graph data structure, updated trip,
min trip previously found )
unchoose x
Part Four: Your own approach
You will also implement the command MINE that executes your own faster algorithm for
performing the traveling salesman problem. The code you submit should be able to execute
the MINE command. For your own approach you can choose to do one of the following (or
both if you come up with something really fancy and fast!):
• improve upon the heuristic approach while not resorting to a trivial solution like just
listing all of the nodes in order
• improve upon the recursive backtracking approach by putting in more pruning and
then show this is faster than the suggested recursive backtracking approach
Part Five: Timing all of the approaches
Using code similar to the following, you will have a TIME command that times all of the
algorithms.