The Travelling Salesman Problem
java代写/数据结构代写/算法钉鞋/javafx代写:该项目不仅涉及了java的图形界面编程，还涉及到了数据结构的图的问题，是一个综合性很强的项目，对编程能力和图相关的知识要求较高
The travelling salesman problem is one of the best known problems in computer science. It asks this
question: given a set of cities and roads connecting these cities, what is the shortest path the salesman
can take that visits all of the cities and returns to the start location. The problem is known to be NP
complete, meaning that exact solutions are difficult to find even for moderately sized data sets. We will
be attempting to solve a small TSP problem known as berlin52. The data for this problem will be
provided as an ASCII file on the Sakai web page.
Purpose of this Assignment
The purpose of this assignment is to give students experience working with threads and working with
Swing and AWT. You must not use BasicIO for this assignment. If the marker finds an import
BasicIO.*; statement in your program, he will remove it. If your program then fails to compile
you will get zero. Further, you must not use a GUI builder to create your GUI. You must program the
GUI yourself.
Normally, as you know, I insist that classes adhere to the single responsibility principle. In the case of
the GUI for this assignment I will make an exception. If you can get your GUI to work by placing all of
the code in one GUI class you will not lose marks for this. For many students this will be their first
time working with Swing and AWT, and I think it is more important just to get the GUI working. Note
that this only applies to the GUI class(es). The rest of your program should still conform to the single
responsibility principle. Having said this, I will add that I think it is easier to implement the GUI using
two classes.
The Search
Many different types of searches have been applied to the TSP. Ant algorithms, genetic algorithms, and
K-opt searches are a few of the more common ones. We will be using a very simple type of search
called an Evolutionary Strategy. This is a pseudo-code description of its operation:
current path = random path;
for number of iterations
mutated path = mutate(current path);
if length of mutated path < length of current path
current path = mutated path
end if
end for
Suggested Sequence for Writing Your Program
The first step is to write the code to read the input file and create the adjacency matrix for the graph. I
have copied and pasted the first few lines of the berlin52 text file below.
52
1 565.0 575.0
2 25.0 185.0
3 345.0 750.0
4 945.0 685.0
...
The first integer 52 represents the number of vertices in the graph. It is followed by 52 lines where each
line has 3 values: an integer representing the vertex number, a float representing the x coordinate of
that vertex and a float representing the y coordinate of that vertex. When you read this data I think it
would be best just to discard the vertex number. If you save it you will effectively be using 1-based
indexing which might cause problems.
After you have read this data you should next create the adjacency matrix. We will assume three things
about the graph data. One, the graph is maximally connected (this means an edge directly connects
every vertex to every other vertex.) Two, the edges are straight lines in Euclidean space. Three, the
edges are not directed. We will use the Pythagorean theorem to find the edge lengths and fill the
adjacency matrix. The formula for the distance between two points x1y1 and x2y2 is
sqrt((x1-x2)*(x1-x2) + (y1-y2)*(y1-y2))
Once you have created and filled the adjacency matrix, you can implement the search. The first step in
the search is the generation of a random path. The best way to do this is to create this path array
int[] path = new int[numVertices];
for(int i=0;i
mutation we will have:
path[1]=16 path[2]=48 path[3]=37
Note that it is possible that a mutation will only interchange two of the vertices. This is OK because
sometimes the best move will be to only interchange two.
You should run your search for about 1,000,000 iterations. This seems like a lot but the search is so
simple it should only take a few seconds. Next, you should wrap your search in another for loop that
runs the complete search about 30 times. The reason for this is that some random start paths will give
much better results than others. After 1,000,000 iterations it is unlikely there will be any further
improvement, so it is better to just generate a new random path and start over. Save the best path and
the length of the best path and print them when the 30 searches complete. If the search is working
properly you should expect a shortest path of roughly 8300 to 8800. (Best known is 7544.37)
The next step should be to thread your search and run three or four (whatever your computer will
allow) searches simultaneously. Be aware that there is an issue using random numbers in threads. The
normal way most people will seed random is by using System.currentTimeMillis(). The
problem with using this method in threads is that all the threads will be created within one millisecond
of each other, seed random with the same seed, and generate exactly the same sequence of random
numbers. The method I used to circumvent this problem was to pass the thread index into the search
function and seed with System.currentTimeMillis()*(1 + thread index). The one is
just to prevent seeding with zero for index zero. You might also try putting a sleep command in your
thread creation loop.
There is a Java structure called ThreadLocalRandom that is meant to be used with threads, but I
couldn’t get it to work. Every thread generated the same random numbers.
Finally, you should create a GUI for the search as shown below
The user enters the file path, the number of iterations, the number of searches, and the number of
threads, then clicks the Run Search button.
The GUI shown will create 4 search threads. Each thread should maintain a local best path (best over
all searches so far). If the thread finds that its current path is shorter than the local best, it should update
the local best, then check to see if it is also shorter than the global best by reading the Current Best text
field in the GUI. If the path is also shorter than the global best, then the thread should update the
current best text field and draw the path in the JPanel.
Your threads must use appropriate measures to ensure they cannot access shared resources
simultaneously.
Drawing the path may be the most difficult part of the assignment. If you are unable to get drawing to
work you can remove the JPanel and replace it with a JTextArea and simply print the path array to the
text area. Of course you will not get full marks for this, but it will at least demonstrate that the rest of
your program functions properly.
Submission Requirements
All assignments must be completed individually. Programs may be checked for plagiarism using
MOSS.
Programs must be written in Java. You can use any IDE that is available on the Brock Lab computers.
Your program must run and compile on the lab computers or it will not be marked. You should provide
a statement specifying the IDE used as well as any additional information needed to run your program.
No paper submission is required for this assignment. All assignments are to be submitted through
Sakai. You should have a folder for the assignment (Assign_3). This folder should include what is
needed for the marker to run and compile your program. Zip this folder as Assign_3.zip. Log on to
Sakai and select the COSC 2P05 site. On the Assignments page select Assignment 3. Attach your
.zip file (e.g. Assign_3.zip) to the assignment submission (use the Add Attachments button and
select Browse. Navigate to where you stored your assignment and select the .zip file (e.g.
Assign_3.zip). The file will be added to your submission. Be sure to read and check the Honour
Pledge check box. Press Submit to submit the assignment. You should receive a confirmation
email.
Note: The due date will be set in Sakai to Friday, March 16 at 12 noon. The accept until date is set to
Monday, March 19 at 12 noon to allow any late assignments to be submitted. Late assignments will be
penalized 25%. Sakai is currently configured to allow one re-submission up to the late date. Be sure your
program is correct before you submit it.
Mark Allocation
2 marks for a working search, 3 marks for threads properly implemented, 3 marks for the GUI with path
drawing, 2 marks for proper commenting, indentation, naming conventions and class structure etc.