Solution to Travelling Salesman Problem

• Download source files - 2.08 Kb

Introduction

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.

Problem Statement

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.

Notations

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.

Algorithm

MIN_CKT_LENGTH=INFINITY
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 if
     end for V_N
   end for V

code segment:

//for each vertex, S_V as a staring node


for(int S_V_id=0;S_V_id<n;S_V_id++)

{ 
      //for each and non start vertex as i

      for(i=0;i<n;i++)
      { 
          //set all to unvisited

          set_visited(ALL,FALSE);
          // set staring vertex as visited

          set_visited(S_V_id,TRUE);
          //reset/init minimum circuit

          reset_min_circuit(S_V_id);
          // obtain circuit for combination of S_V and i

          new_circuit_length=get_valid_circuit(S_V_id,i);
          // if newer length is less than the previously

          //calculated min then set it as min and set the

          //current circuit in hamiltonion circuit

          if(new_circuit_length<=min_circuit_length)
                SET_HAM_CKT(min_circuit_length=new_circuit_length);
       }

}

Example

Inputs

infinity: 999
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:

Comments

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.