# Travelling salesman problem in C

Discussion in 'C Programming' started by whitehatmiracle@gmail.com, Sep 10, 2006.

1. ### Guest

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

, Sep 10, 2006

2. ### Spiros BousbourasGuest

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.

Spiros Bousbouras, Sep 10, 2006

3. ### Guest

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?

, Sep 10, 2006
4. ### Richard HeathfieldGuest

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)

Richard Heathfield, Sep 10, 2006
5. ### Elijah CardonGuest

Richard Heathfield wrote:
> 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

Elijah Cardon, Sep 10, 2006
6. ### Spiros BousbourasGuest

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.

Spiros Bousbouras, Sep 10, 2006
7. ### Guest

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

, Sep 10, 2006
8. ### ballpointpenthiefGuest

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

ballpointpenthief, Sep 10, 2006
9. ### Default UserGuest

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

Default User, Sep 10, 2006
10. ### jmcgillGuest

Re: Travelling squirrel problem?

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?

jmcgill, Sep 10, 2006
11. ### Elijah CardonGuest

Default User wrote:
> 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

I have 2 separate issues I would like to address here. One is that
everybody seems to be able to google a newsgroup. Would OP be so kind
as to tell me how to do this in a manner that pulls up what this

Number 2 is that I would like to thank Richard Heathfield for ruining my
sabbath. I was just trying to say my hail marys, but then it comes time
to share the peace. This is usually an easy problem for me. It
involves vertices and edges, and I have the advantage of being a faster
salesman than any vertex I don't want to shake hands with.

But there's a kink in this week's salesroute, because now I know that
there exists a brunnette 5 feet away whose hand I would really like to
touch. Will there be a decision?

I seg-faulted. Elijah

Elijah Cardon, Sep 11, 2006
12. ### CBFalconerGuest

Using google and quoting (was: Travelling salesman problem in C)

Elijah Cardon wrote:
>

.... snip ...
>
> I have 2 separate issues I would like to address here. One is
> that everybody seems to be able to google a newsgroup. Would OP
> be so kind as to tell me how to do this in a manner that pulls
> up what this newsgroup has said about this problem before.

Maybe they can, but many don't want to. Googling it involves
getting on line (I operate off line) and locating message id's
and/or threads. It also involves abandoning what you are doing,
should be totally unnecessary with proper quoting (and snipping).

--
Chuck F (cbfalconer at maineline dot net)
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home.att.net>

--
Posted via a free Usenet account from http://www.teranews.com
Warning: Do not use Ultimate-Anonymity
They are worthless spammers that are running a scam.

CBFalconer, Sep 11, 2006
13. ### jmcgillGuest

Elijah Cardon wrote:

> I have 2 separate issues I would like to address here. One is that
> everybody seems to be able to google a newsgroup. Would OP be so kind
> as to tell me how to do this in a manner that pulls up what this

A basic search for "Travelling Salesman Problem" comes up with articles
dating back to at least 1993. There are ways to do more thorough
searches, for more elaborate queries and to include other groups.

The Google Groups interface has its limitations, but it is arguably no
worse than the DejaNews service it replaced.

jmcgill, Sep 11, 2006
14. ### Guest

> No , this would be a huge waste of memory.
> For every permutation you calculate the distance.
> If it is smaller than the minimum distance you have
> so far then you store the new minimum plus the
> permutation which produced it. Continue like this
> until you've examined all permutations.

But what if there is more tha one solution. 3 paths having the smae
distance.

I was thinking of storing all the possibilities and traverssing it in
an inteligent way.

Say i have
ABCDE 45
ABCED 72
ABDEC 55
ACBDE 102
ACBDE 135

I see that the combination ACB > ABC therefore i skip the whole ACB
series...
Its like if i have a tree or a graph, the branch that gives the longest
distance can be skiped... am i right?
If so how do i go about it... is it a simple string compare?

Thanx once again

, Sep 11, 2006
15. ### Guest

Search this group for the word
"permutations" and you'll find threads with plenty
of advice and possibly a complete solution.

On

i found a working example of a c code of permuting ABCDE, but cant

Can someone gimme an insight into whats really happeneiing. Here is the
code.

===========
#include <stdio.h>
#include <string.h>

void Permute(char *Perm,
size_t n,
size_t unchanged)
{
size_t outer = 0;
size_t inner = 0;
int temp = 0;

if(unchanged < n)
{
for(outer = unchanged; outer < n; outer++)
{
temp = Perm[outer];
for(inner = outer; inner > unchanged; inner--)
{
Perm[inner] = Perm[inner - 1];
}
Perm[unchanged] = temp;
Permute(Perm,
n,
unchanged + 1);

for(inner = unchanged; inner < outer; inner++)
{
Perm[inner] = Perm[inner + 1];
}
Perm[outer] = temp;
}
}
else
{
printf("%s\n", Perm);
}

}

int main(int argc, char **argv)
{
char Input[256] = {0};
size_t len = 0;

if(argc > 1)
{
len = strlen(argv[1]);
if(len > sizeof Input - 1)
{
fprintf(stderr, "word too long for demo - truncating\n");
argv[1][sizeof Input - 1] = '\0';
}
strcpy(Input, argv[1]);
len = strlen(Input);
}
else
{
len = 3;
strcpy(Input, "ABC");
}

Permute(Input, len, 0);

return 0;

}
===========

, Sep 11, 2006
16. ### CBFalconerGuest

wrote:
>
> Hi there, i need some help for the traveling salesman prob in C
> I have an array with distances to cities
>

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

Try this:

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

/* Public domain, by C.B. Falconer. *//* 2003-Aug-21 */
/* Attribution appreciated. */

/* Things get out of hand when larger than 8 */
#define MAXWORD 17

/* ------------------ */

/* exchange 0th and ith char in wd */
void trade(char *wd, unsigned int i)
{
char c;

c = *wd;
*wd = wd;
wd = c;
} /* trade */

/* ------------------ */

/* Form all n char permutations of the characters in the
string wd of length lgh into outstring at index ix.
Output the results to stdout. */
void jumble(char *wd, unsigned int lgh,
unsigned int ix, /* output place to fill */
unsigned int n, /* max out places to fill */
char *outstring)
{
unsigned int i;

if (0 == n) {
outstring[ix] = '\0';
puts(outstring);
}
else
for (i = 0; i < lgh; i++) {
trade(wd, i); /* nop when (0 == i) */
outstring[ix] = *wd;
jumble(wd+1, lgh-1, ix+1, n-1, outstring);
trade(wd, i); /* restore the wd string */
}
} /* jumble */

/* ------------------ */

int main(int argc, char *argv[])
{
unsigned int n, lgh, min;
double max;
char outstring[MAXWORD];

if (argc < 2) {
fprintf(stderr,
"Usage: jumble <baseword> [lgh]\n"
" where the (optional) lgh specifies the\n"
" maximum length of the output words\n");
return 0;
}
lgh = strlen(argv[1]);
if (lgh >= MAXWORD) argv[1][lgh = MAXWORD-1] = '\0';

min = lgh;
if ((argc > 2) && (1 == sscanf(argv[2], "%u", &n)))
if (n && (n <= lgh)) min = n;

for (n = lgh, max = 1.0; n > (lgh - min); n--)
max = max * n;

fprintf(stderr, "string=\"%s\", max=%.0f, len=%u\n",
argv[1], max, min);

jumble(argv[1], lgh, 0, min, outstring);
return 0;
} /* main */

--
news:news.announce.newusers
http://www.geocities.com/nnqweb/
http://www.catb.org/~esr/faqs/smart-questions.html
http://www.caliburn.nl/topposting.html
http://www.netmeister.org/news/learn2quote.html

--
Posted via a free Usenet account from http://www.teranews.com
Warning: Do not use Ultimate-Anonymity
They are worthless spammers that are running a scam.

CBFalconer, Sep 11, 2006
17. ### Spiros BousbourasGuest

wrote:

> > No , this would be a huge waste of memory.
> > For every permutation you calculate the distance.
> > If it is smaller than the minimum distance you have
> > so far then you store the new minimum plus the
> > permutation which produced it. Continue like this
> > until you've examined all permutations.

>
> But what if there is more tha one solution. 3 paths having the smae
> distance.

Are you trying to print all journeys which give
the smallest distance or just one ? Usually the
salesman problem asks for the latter and in that
case having more than one paths with the same
distance is no problem ; the approach I suggested
still works. But even if you want all paths with the
minimum distance you still don't need to store all
permutations , just those which so far have produced
the smallest distance.

>
> I was thinking of storing all the possibilities and traverssing it in
> an inteligent way.

But if you have already stored all possibilities you
have already used up a lot of time ; what you do
afterwards , intelligent or not ,won't change that.

>
> Say i have
> ABCDE 45
> ABCED 72
> ABDEC 55
> ACBDE 102
> ACBDE 135
>
> I see that the combination ACB > ABC therefore i skip the whole ACB
> series...
> Its like if i have a tree or a graph, the branch that gives the longest
> distance can be skiped... am i right?

No , because it might be that the distance from B to
D and E is small but the distance from C to D or E
is large so for example ACBDE may turn out to be
shorter than ABCDE or ABCED.

> If so how do i go about it... is it a simple string compare?

The way to go about it is to write first a programme
which implements the "brain dead" method of going
through all permutations. If after that you want to try
and implement something more clever then I would
suggest having a look at the book "Computers and
intractability; a guide to the theory of NP-completeness"
by Garey and Johnson. As far as I can remember the
book does not mention any clever algorithms for the
salesman problem but the bibliography mentions in which
papers you would find such algorithms. If I remember
correctly the best algorithm known has complexity O(c^n)
where c is a constant and n the number of cities while
the permutations approach has complexity O(n!).

Spiros Bousbouras, Sep 11, 2006
18. ### Spiros BousbourasGuest

wrote:

> Search this group for the word
> "permutations" and you'll find threads with plenty
> of advice and possibly a complete solution.
>
>
> On
>
> i found a working example of a c code of permuting ABCDE, but cant
> quite follow it.

Well try "running" the code in your head or on a piece
of paper with "small" input like strings at most 3 characters
long. Or add printf statements in the code which will tell
you the value of variables as the programme is running.
Keep doing that until the logic of the programme becomes
obvious.

>
> Can someone gimme an insight into whats really happeneiing. Here is the
> code.

Someone might but if you want to become
good at programming you need to do the
grunt work yourself.

<CODE SNIPPED>

Spiros Bousbouras, Sep 11, 2006
19. ### Stephen SprunkGuest

<> wrote in message
news:...
>> No , this would be a huge waste of memory.
>> For every permutation you calculate the distance.
>> If it is smaller than the minimum distance you have
>> so far then you store the new minimum plus the
>> permutation which produced it. Continue like this
>> until you've examined all permutations.

>
> But what if there is more tha one solution. 3 paths having the smae
> distance.

Then there are three solutions. Returning one of them may be enough,
but in many cases you'll be expected to return all of the optimal (or
even near-optimal) solutions.

> I was thinking of storing all the possibilities and traverssing it in
> an inteligent way.
>
> Say i have
> ABCDE 45
> ABCED 72
> ABDEC 55
> ACBDE 102
> ACBDE 135
>
> I see that the combination ACB > ABC therefore i skip the whole ACB
> series...
> Its like if i have a tree or a graph, the branch that gives the
> longest
> distance can be skiped... am i right?
> If so how do i go about it... is it a simple string compare?

There is no guarantee that if ACB > ABC then ACBxx > ABCxx.

The traveling salesman problem is NP-complete. There is no known
shortcut, period. The only known way to solve NPC problems is brute
force testing of every possibility.

This is probably why your instructor has assigned you this problem -- to
show you that some problems simply aren't solvable (for a large enough
N) and you can't rely on clever tricks or compiler optimizations to save
you if you pick the wrong algorithm.

S

--
Stephen Sprunk "God does not play dice." --Albert Einstein
CCIE #3723 "God is an inveterate gambler, and He throws the
K5SSS dice at every possible opportunity." --Stephen Hawking

--
Posted via a free Usenet account from http://www.teranews.com
Warning: Do not use Ultimate-Anonymity
They are worthless spammers that are running a scam.

Stephen Sprunk, Sep 11, 2006
20. ### Spiros BousbourasGuest

Stephen Sprunk wrote:

> The traveling salesman problem is NP-complete. There is no known
> shortcut, period. The only known way to solve NPC problems is brute
> force testing of every possibility.

There are shortcuts , just not polynomial time algorithms.

>
> This is probably why your instructor has assigned you this problem -- to
> show you that some problems simply aren't solvable (for a large enough
> N) and you can't rely on clever tricks or compiler optimizations to save
> you if you pick the wrong algorithm.

Of course that shouldn't dissuade the opening poster
from trying to find "tricks". There is a price of one million
dollars for a good enough trick (== polynomial time algorithm).

Spiros Bousbouras, Sep 11, 2006