12,399,799 members (46,712 online)
alternative version

144.5K views
31 bookmarked
Posted

# Solution to Travelling Salesman Problem

, 21 Jan 2005
 Rate this:
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

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.

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

## About the Author

 Engineer India
Engg Student

## Comments and Discussions

 First Prev Next
 thanks saeedmag4-Jul-12 6:47 saeedmag 4-Jul-12 6:47
 Some question. Spas22110-Jan-12 2:29 Spas221 10-Jan-12 2:29
 Documentation garzon326-Jun-11 10:00 garzon3 26-Jun-11 10:00
 heuristic Tamas Bege15-Dec-10 3:07 Tamas Bege 15-Dec-10 3:07
 THANKSSSSSSSSSS hamid_ss28-May-10 11:53 hamid_ss 28-May-10 11:53
 Minor change !! patson3318-Mar-10 14:01 patson33 18-Mar-10 14:01
 Algorithm is not optimal KHDev4u10-Mar-06 12:20 KHDev4u 10-Mar-06 12:20
 Re: Algorithm is not optimal omkar joshi11-Mar-06 0:00 omkar joshi 11-Mar-06 0:00
 Re: Algorithm is not optimal sirb27-Nov-11 0:28 sirb 27-Nov-11 0:28
 P = NP? Cap'n Code22-Jan-05 6:21 Cap'n Code 22-Jan-05 6:21
 Re: P = NP? Rui A. Rebelo22-Jan-05 7:39 Rui A. Rebelo 22-Jan-05 7:39
 Re: P = NP? omkar joshi22-Jan-05 21:03 omkar joshi 22-Jan-05 21:03
 Re: P = NP? omkar joshi22-Jan-05 21:03 omkar joshi 22-Jan-05 21:03
 Re: P = NP? jbstjohn24-Jun-05 5:43 jbstjohn 24-Jun-05 5:43
 Re: P = NP? computerguru923821-Jul-05 7:23 computerguru92382 1-Jul-05 7:23
 Re: P = NP? Anonymous29-Aug-05 10:21 Anonymous 29-Aug-05 10:21
 Re: P = NP? omkar joshi24-Jan-06 1:54 omkar joshi 24-Jan-06 1:54
 Re: P = NP? omkar joshi24-Jan-06 1:27 omkar joshi 24-Jan-06 1:27
 Re: P = NP? omkar joshi24-Jan-06 1:43 omkar joshi 24-Jan-06 1:43
 Re: P = NP? jbstjohn9-Feb-06 4:16 jbstjohn 9-Feb-06 4:16
 Re: P = NP? vishal_chauhan8-May-07 3:26 vishal_chauhan 8-May-07 3:26
 Last Visit: 31-Dec-99 18:00     Last Update: 26-Jul-16 9:30 Refresh 1

General    News    Suggestion    Question    Bug    Answer    Joke    Praise    Rant    Admin

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