Velocity Reviews > Travelling salesman problem in C

# 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

CLUESSSSS????????

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
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.

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?

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)

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
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

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.

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

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

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

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?

 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 OffTrackbacks are On Pingbacks are On Refbacks are Off Forum Rules

 Similar Threads Thread Thread Starter Forum Replies Last Post whitehatmiracle@gmail.com C++ 5 09-10-2006 11:45 PM Luc The Perverse Java 12 05-05-2006 09:06 PM KantKwitDansin1 C++ 9 12-12-2004 09:53 PM Erlend Andreas Garberg Python 20 04-02-2004 09:09 PM Vinay Adella C Programming 4 09-04-2003 02:54 AM