Hereby, I am giving a program to find a solution to a Traveling Salesman Problem using Hamiltonian circuit, the efficiency is O (n^4) and I think it gives the optimal solution. Though I have provided enough comments in the code itself so that one can understand the algorithm that I m following, here I give the pseudocode.
Find the order of cities in which a salesman should travel in order to start from a city, reaching back the same city by visiting all rest of the cities each only once and traveling minimum distance for the same.
ALT statement: Find a Hamiltonian circuit with minimum circuit length for the given graph.
G: Symmetric weighted undirectional graph with,
- Number of vertices = No. of cities
- Number of links = Number of paths
- Weight of the link = Distance of the path.
for each vertex V in the graph G
for each vertex V_N in the graph G such that V and V_N are different
mark all vertices unvisited
mark V as visited
for staring vertex as V and succeeding vertex as V_N, find circuit
such that path staring from V_N in that circut yeilds minimum
pathlength from V_N for all unvisited vertices by
visiting each vertex.( this path is obtained by greedy method).
if currently obtained circuit length <= MIN_CKT_LENGTH then
set MIN_CKT_LENGTH=newly obtained value
copy the new circuit as hamiltonion circuit
end for V_N
end for V
//for each vertex, S_V as a staring node
//for each and non start vertex as i
//set all to unvisited
// set staring vertex as visited
//reset/init minimum circuit
// obtain circuit for combination of S_V and i
// if newer length is less than the previously
//calculated min then set it as min and set the
//current circuit in hamiltonion circuit
no. of cities: 4
no. of paths: 6
S D Dist
path0: 0 1 2
path1: 0 2 4
path2: 0 3 3
path3: 1 2 3
path4: 1 3 6
path5: 2 3 1
Algorithm proceeds as follows:
(started with INFI,-)
(started with INFI,-)
This might be the overrun for lower values of vertex count but for large values of n, it's surely less than the exhaustive search as n increases n^4 < n! for n>6.
The optimality is the issue with this problem and as far as I am concerned, I think this algorithm yields the optimal Hamiltonian circuit if it exists at all.
Hereby I ask you people to evaluate my algorithm for different sets of test cases. In case of failure, please inform me with the set of input values, answer found by my code and the actual optimal answer.