-
Assignment 3: Travelling Salesman Problem(TSP)
Weight :
30
-
Due Date: 23th Feb.
- Make FORTRAN 90 Source and output into one file and upload to
your HUxx account in MUSICB.
- E-MAIL that file to HUAC on MUSICB from your HUxx
account.
This assignment has to be done in FORTRAN 90, using the LAHEY compiler,
which you can download for free from www.lahey.com
or this is available in the EMF.See the documentation on the LAHEY website
for installation and running programs on your own machine. Note your FORTRAN
90 source code should be the ELF90 directory with the compiler for easy
operation.
-
Given N cities C1,C2, ....Ci,Cj,.... Cn and one way road between each pair
Ci,Cj with travel cost Kij, find the cheapest round trip roads starting
at C1 passing through every other city exactly once and returning to C1.
The costs are normally given in an N x N matrix.
-
In theory, the TSP is easy to solve because we can find it exhaustively.
Given N cities, first choose C1 and next consider N-1 cities . In
each N-1 cities, we consider again N-2 possibilities.The
possibilities are (N-1)x(N-2)x(N-3) ... 3x2x1 = (N-1)!
-
In practice, this is not feasible when the number of cities exceeds about
15. Even the fastest computers can not evaluate the cost of tours when
N goes much more than 15.
-
-
Given 5 x 5 costs matrix , print all possible tours starting at C1 and returning
C1, passing through every other city exactly once.
-
Print out the paths and costs.
-
(Costs matrix shows the cost from Ci to Cj starting at 1 to 5 . Ex : Cost
of C4 to C2 is 6 )
-
0 5 3 3 9
-
5 0 9 5 8
-
2 7 0 9 5
-
8 6 4 0 3
-
5 3 2 8 0
-
-
-
Remark : To make the program easier, question is changed to print all
paths and costs instead of finding the cheapest path.
-
-