Travelling salesman problem in C

[whitehatmiracle]

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

 

[Spiros Bousbouras]

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.

 

[whitehatmiracle]

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]

(e-mail address 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!

 

[Elijah Cardon]

(e-mail address removed) said:

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

 

[Spiros Bousbouras]

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

He said the only *known* way.

 

[whitehatmiracle]

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]

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]

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]

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?

 

[Elijah Cardon]

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
newsgroup has said about this problem before.

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

 

[CBFalconer]

.... 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,
which is reading some thread in your own newsreader. All that
should be totally unnecessary with proper quoting (and snipping).

 

[jmcgill]

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.

Google Groups: http://groups.google.com/group/comp.lang.c

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.

 

[whitehatmiracle]

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?

Please enlighten me......
Thanx once again

 

[whitehatmiracle]

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


On
http://groups.google.com/group/comp.lang.c/browse_thread/thread/e0a154ce13c7199d/#

i found a working example of a c code of permuting ABCDE, but cant
quite follow it.

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;



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

 

[CBFalconer]

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


--
Some informative links:
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

 

[Spiros Bousbouras]

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]

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


On
http://groups.google.com/group/comp.lang.c/browse_thread/thread/e0a154ce13c7199d/#

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>

 

[Stephen Sprunk]

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

 

[Spiros Bousbouras]

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