Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C Programming > Travelling salesman problem in C

Reply
Thread Tools

Travelling salesman problem in C

 
 
whitehatmiracle@gmail.com
Guest
Posts: n/a
 
      09-10-2006
Hi there, i need some help for the traveling salesman prob in C
I have an array with distances to cities

A B C D E
A 0 5 7 1 9
B 5 0
C 7 0
D 1 0
E 9 0
etc.................................


With a brute force i get all combinations ABCDE ABDCE ABCED ...........

I guess i have to use 5 for loops. Not sure how to do that.
In a corresponding array i store the distances by claculating with the
help of the table look up.
SOS....HELP URGENT


THANKING YOU ALL IN ADVANCE


CLUESSSSS????????

 
Reply With Quote
 
 
 
 
Spiros Bousbouras
Guest
Posts: n/a
 
      09-10-2006
http://www.velocityreviews.com/forums/(E-Mail Removed) wrote:

> Hi there, i need some help for the traveling salesman prob in C
> I have an array with distances to cities
>
> A B C D E
> A 0 5 7 1 9
> B 5 0
> C 7 0
> D 1 0
> E 9 0
> etc.................................
>
>
> With a brute force i get all combinations ABCDE ABDCE ABCED ...........
>
> I guess i have to use 5 for loops. Not sure how to do that.
> In a corresponding array i store the distances by claculating with the
> help of the table look up.
> SOS....HELP URGENT
>
>
> THANKING YOU ALL IN ADVANCE
>
>
> CLUESSSSS????????


No , you don't have to write 5 for loops. What if you
had 10 cities , would you write 10 loops ? What you
do need is a way to generate all permutations of the
string ABCDE. Search this group for the word
"permutations" and you'll find threads with plenty
of advice and possibly a complete solution.

The other thing to consider is that there are two
variations of the salesman problem. In the first
variation the salesman has to return to the city
where he started his trip so he visits this city and
only this twice. In the second variation he visits
every city exactly once. If it is the first variation
you want to solve then you need to take into account
that for every permutation there are 4 others which
produce the same total distance. For example the
permutations ABCDE , BCDEA , CDEAB , DEABC ,
EABCD all describe a trip with the same total distance.

 
Reply With Quote
 
 
 
 
whitehatmiracle@gmail.com
Guest
Posts: n/a
 
      09-10-2006
Hi there
Thanx a lot for the reply.
I guess the salesman visits every city only once.
This problem is actually under the section of graphs that i am
studying.
But where does the graphing come in?

 
Reply With Quote
 
Richard Heathfield
Guest
Posts: n/a
 
      09-10-2006
(E-Mail Removed) said:

> Hi there
> Thanx a lot for the reply.
> I guess the salesman visits every city only once.
> This problem is actually under the section of graphs that i am
> studying.
> But where does the graphing come in?


The graph is the data structure that you use to describe nodes (cities) and
edges (the existence and length of roads between cities).

Finding the shortest route is an NP-complete problem. That is, the only
known way to get the optimum result is to brute-force it. But you can get
pretty good results much more quickly, a fact that many travelling salesmen
undoubtedly appreciate.

I don't watch TV at home, but at a friend's house some years ago I saw a
wonderful documentary about squirrels, which showed that they appear to
solve the travelling salesman problem every time they go to pick up a bunch
of nuts. They reject the naive algorithm "go to the nearest unpicked-up
nut" in favour of a route that (as far as the computers have been able to
work out) minimises their total travelling distance - i.e. their exposure
to potential danger.

Let's hear it for the squirrels!

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at above domain (but drop the www, obviously)
 
Reply With Quote
 
Elijah Cardon
Guest
Posts: n/a
 
      09-10-2006
Richard Heathfield wrote:
> (E-Mail Removed) said:
>
>> Hi there
>> Thanx a lot for the reply.
>> I guess the salesman visits every city only once.
>> This problem is actually under the section of graphs that i am
>> studying.
>> But where does the graphing come in?

You're not going to end up making a squiggly line for a problem like
this. The answer is determined by calculation. Your development
probably uses 'vertex' instead of 'node'.

> The graph is the data structure that you use to describe nodes (cities) and
> edges (the existence and length of roads between cities).
>
> Finding the shortest route is an NP-complete problem. That is, the only
> known way to get the optimum result is to brute-force it. But you can get
> pretty good results much more quickly, a fact that many travelling salesmen
> undoubtedly appreciate.

I thought the jury was still out on whether this had an efficient soln.

> I don't watch TV at home, but at a friend's house some years ago I saw a
> wonderful documentary about squirrels, which showed that they appear to
> solve the travelling salesman problem every time they go to pick up a bunch
> of nuts. They reject the naive algorithm "go to the nearest unpicked-up
> nut" in favour of a route that (as far as the computers have been able to
> work out) minimises their total travelling distance - i.e. their exposure
> to potential danger.
>
> Let's hear it for the squirrels!

Not my favorite animal, but what the heck. EC
 
Reply With Quote
 
Spiros Bousbouras
Guest
Posts: n/a
 
      09-10-2006
Elijah Cardon wrote:

> Richard Heathfield wrote:
> > Finding the shortest route is an NP-complete problem. That is, the only
> > known way to get the optimum result is to brute-force it. But you can get
> > pretty good results much more quickly, a fact that many travelling salesmen
> > undoubtedly appreciate.
> >

> I thought the jury was still out on whether this had an efficient soln.


He said the only *known* way.

 
Reply With Quote
 
whitehatmiracle@gmail.com
Guest
Posts: n/a
 
      09-10-2006
I guess the main steps (pseudo code) in this program are:
Finding and storing all the permutations of the string ABCDE:
Calculating the corresponding distances
And go through all the permutations comapring every value to find the
shortest route


ANything missing?

Thanx again all of you

 
Reply With Quote
 
ballpointpenthief
Guest
Posts: n/a
 
      09-10-2006

(E-Mail Removed) wrote:
> Hi there, i need some help for the traveling salesman prob in C
> I have an array with distances to cities
>
> A B C D E
> A 0 5 7 1 9
> B 5 0
> C 7 0
> D 1 0
> E 9 0
> etc.................................
>


If you don't want to solve this with the brute force method, then I
would suggest looking up the Transhipment Model. It looks like it could
be a Network Minimisation problem also. (I'm looking through my
Operations Research book.)

There are some simple yet clever algorithms for solving this kind of
problem, which are all based on linear programming, and the Simplex
Method.

You probably need to start off by setting the 0's to a sufficiently
large number, and then find an algorithm which would suit the problem.
I would guess there a very few people who would be able to devise there
own algorithm without investing a lot of time studying the field
though.

If you do want to use the brute force method, then you will need to
write a function to work out the distance given the order of the places
visited, then check every permutation, and spit out the lowest number.
Although that would be much less fun.

Matt

 
Reply With Quote
 
Default User
Guest
Posts: n/a
 
      09-10-2006
(E-Mail Removed) wrote:

> I guess the main steps (pseudo code) in this program are:


Please quote enough of the previous message for context. See the other
messages in the newsgroup.




Brian
 
Reply With Quote
 
jmcgill
Guest
Posts: n/a
 
      09-10-2006
Richard Heathfield wrote:

> I don't watch TV at home, but at a friend's house some years ago I saw a
> wonderful documentary about squirrels, which showed that they appear to
> solve the travelling salesman problem every time they go to pick up a bunch
> of nuts.


It would be interesting to see the research data that were used for the
documentary. I don't expect you have a cite for it, but perhaps someone
else does?
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Traveling salesman problem whitehatmiracle@gmail.com C++ 5 09-10-2006 11:45 PM
Travelling Salesman with Spherical Coordinates. Luc The Perverse Java 12 05-05-2006 09:06 PM
Traveling Salesman Problem KantKwitDansin1 C++ 9 12-12-2004 09:53 PM
Travelling salesman variation in python Erlend Andreas Garberg Python 20 04-02-2004 09:09 PM
complexity of Traveling Salesman Problem? Vinay Adella C Programming 4 09-04-2003 02:54 AM



Advertisments