Click here to Skip to main content
Click here to Skip to main content

Solution to Travelling Salesman Problem

, 21 Jan 2005
Rate this:
Please Sign up or sign in to vote.
Solution to a Travelling Salesman problem using Hamiltonian circuit, the efficieny is O(n^4) and I think it gives the optimal solution.

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:

V V_N V_N-path ckt_length, ckt
(started with INFI,-)
MIN_CKT_LENGTH, HAM_CKT
(started with INFI,-)
0 1 1-2-3 9,0-1-2-3-0* 9,0-1-2-3-0
  2 2-3-1 13,0-2-3-1-0 9,0-1-2-3-0
  3 3-2-1 9,0-3-2-1-0* 9,0-3-2-1-0
1 0 0-3-2 9,1-0-3-2-1* 9,1-0-3-2-1
  2 2-3-0 9,1-2-3-0-1* 9,1-2-3-0-1
  3 3-2-0 13,1-3-2-0-1 9,1-2-3-0-1
2 0 0-1-3 13,2-0-1-3-2 9,1-2-3-0-1
  1 1-0-3 9,2-1-0-3-2* 9,2-1-0-3-2
  3 3-0-1 9,2-3-0-1-2* 9,2-3-0-1-2
3 0 0-1-2 9,3-0-1-2-3* 9,3-0-1-2-3
  1 1-0-2 13,3-1-0-2-3 9,3-0-1-2-3
  2 2-1-0 9,3-2-1-0-3* 9,3-2-1-0-3

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.

License

This article has no explicit license attached to it but may contain usage terms in the article text or the download files themselves. If in doubt please contact the author via the discussion board below.

A list of licenses authors might use can be found here

Share

About the Author

omkar joshi
Engineer
India India
Engg Student

Comments and Discussions

 
Questionthanks Pinmembersaeedmag4-Jul-12 6:47 
QuestionSome question. PinmemberSpas22110-Jan-12 2:29 
QuestionDocumentation Pinmembergarzon326-Jun-11 10:00 
Questionheuristic PinmemberTamas Bege15-Dec-10 3:07 
GeneralTHANKSSSSSSSSSS Pinmemberhamid_ss28-May-10 11:53 
GeneralMinor change !! Pinmemberpatson3318-Mar-10 14:01 
GeneralAlgorithm is not optimal PinmemberKHDev4u10-Mar-06 12:20 
GeneralRe: Algorithm is not optimal Pinmemberomkar joshi11-Mar-06 0:00 
GeneralRe: Algorithm is not optimal [modified] Pinmembersirb27-Nov-11 0:28 
QuestionP = NP? [modified] PinmemberCap'n Code22-Jan-05 6:21 
AnswerRe: P = NP? PinmemberRui A. Rebelo22-Jan-05 7:39 
GeneralRe: P = NP? Pinmemberomkar joshi22-Jan-05 21:03 
AnswerRe: P = NP? Pinmemberomkar joshi22-Jan-05 21:03 
AnswerRe: P = NP? Pinmemberjbstjohn24-Jun-05 5:43 
GeneralRe: P = NP? Pinmembercomputerguru923821-Jul-05 7:23 
GeneralRe: P = NP? PinsussAnonymous29-Aug-05 10:21 
GeneralRe: P = NP? Pinmemberomkar joshi24-Jan-06 1:54 
GeneralRe: P = NP? Pinmemberomkar joshi24-Jan-06 1:27 
GeneralRe: P = NP? Pinmemberomkar joshi24-Jan-06 1:43 
GeneralRe: P = NP? Pinmemberjbstjohn9-Feb-06 4:16 
GeneralRe: P = NP? Pinmembervishal_chauhan8-May-07 3:26 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

| Advertise | Privacy | Mobile
Web02 | 2.8.140827.1 | Last Updated 22 Jan 2005
Article Copyright 2005 by omkar joshi
Everything else Copyright © CodeProject, 1999-2014
Terms of Service
Layout: fixed | fluid