## 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.