# Traveling salesman problem

Discussion in 'C++' 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. ### Guest

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

What is actually your goal? Are the distances already calculated or are
you asking how to calculate the distances? Are you trying to find a
path by visiting each city once, or maybe even the shortest path?

regards
Ivan Leben

, Sep 10, 2006

3. ### Kai-Uwe BuxGuest

wrote [3 times]

This is a news group, not a chat room. Be patient. It takes a long time for
your post to propagate through all the news servers. Posting the same
message over and over again doesn't get you answers any quicker, messes up
the threading of many news readers, and is considered inconsiderate.

> Hi there, i need some help for the traveling salesman prob in C

Ahem, this is a C++ group.

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

You may want to look into std::next_permutation:

#include <iostream>
#include <vector>
#include <iterator>
#include <algorithm>

int main ( void ) {
std::vector< unsigned int > v;
for ( unsigned int i = 0; i < 5; ++i ) {
v.push_back( i );
}
do {
std::copy( v.begin(), v.end(),
std:stream_iterator< unsigned int >( std::cout, " " ) );
std::cout << '\n';
} while ( std::next_permutation( v.begin(), v.end() ) );
}

> In a corresponding array i store the distances by claculating with the
> help of the table look up.

[snip]

Sounds like homework. Show us what you have and ask more specific questions.

Best

Kai-Uwe Bux

Kai-Uwe Bux, Sep 10, 2006
4. ### David HarmonGuest

On 9 Sep 2006 21:34:47 -0700 in comp.lang.c++,
"" <> wrote,
>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.

Or you could use std::next_permutation()

But however you do it, the thing that made the Traveling Salesman
problem famous is the fact that brute force is unusable, because as
the number of cities increases the time required quickly becomes
astronomical.

You need a better method than brute force. Do some research.

>In a corresponding array i store the distances by claculating with the
>help of the table look up.

The size of that table would also become astronomical, except that
you don't need it anyway. All you would need is to remember the
best found so far.

>SOS....HELP URGENT

If you need help urgently then (1) Post your best effort at solving
the problem and (2) ask very specific questions about the part
that's not working. Try to post just once.

This issue is covered in Marshall Cline's C++ FAQ. It is always
good to check the FAQ before posting. You can get the FAQ at:
http://www.parashift.com/c++-faq-lite/

See the welcome message posted twice per week in comp.lang.c++ under
the subject "Welcome to comp.lang.c++! Read this first." or
available at http://www.slack.net/~shiva/welcome.txt

David Harmon, Sep 10, 2006
5. ### PCGuest

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

Have a look at Ant-Colony optimization; below is a link to an
implementation in ANSI C (there's a number of downloads on that page,
get ACOTSP.V1.0.tar.gz)
http://iridia.ulb.ac.be/~mdorigo/ACO/aco-code/public-software.html

Hope that helps,

PC

PC, Sep 10, 2006
6. ### Jim LangstonGuest

<> wrote in message
news:...
> 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????????

If you want to do this brute force in the program you can. Just do it the
same way you did in your head or on paper and pencil. There are better
algorithms out there, better being faster, in that they don't try every
possible combination. They don't neccessarily produce the shortest
distance, but one that okay. They can be tuned to be better than okay or
worst than okay.

Now, lets go back to your problem, which I suspect is a homework problem.
Think about how you did it using brute force. I suspect your howework
question is something along the lines of, You have a table with distance
between cities. Find the shortest possible path to visit every city once.

How can you produce something that lists every way to travel the 5 cities?
Each entry in this list would have 5 elements, one for each city. The list
would have some number of entries. First think about what you want each
entry to be. It could be an array of 5 chars ('A', 'B', 'C', 'D', 'E') or 5
numbers (A = 1, B=2, C=3, E=4, F=5) or you could make it a structure, or a
std::vector. For simplicity I would probably go with an array of 5 chars
and probably encapsulate it in a class. Then I would make a std::vector of
this class, then start populating it.

That is the real root of your homework, how do you populate it? How do you
come up with a list of each possible combination of visiting cities? You
have to make sure not to have duplicates, 'A', 'B', 'A', 'D', 'E' is invalid
because it has 'A' twice. Your 5 for loops is one way to do it, and is
probably the way I would do it for simplicity.

Pseudo code which will not compile, which is brute force and slow:
for ( FirstCity = 'A' to 'E' )
for ( SecondCity = 'A' to 'E' )
if ( SecondCity != FirstCity )
for ( ThirdCity = 'A' to 'E' )
if ( ThirdCity != FirstCity && ThirdCity != SecondCity )
for ( ForthCity = 'A' to 'E' )
if ( ForthCity != ThirdCity && ... )
for ( FifthCity = 'A' to 'E' )
if ( FifthCity != FirstCity && ... )
Add Element FirstCity + SecondCity + ThirdCity
+ ForthCity + FifthCity

The iterations can reach 5^5 = 3125
If there were 6 cities it would be 6^6 or 46656
7 would be 823543
As you can see it grows exponentionally.

But, in reality, we won't iterate though 3125 because if FirstCity == 'A'
and SecondCity == 'A' we won't iterate though the rest. It is an excersice
for the reader to determine how many iterations there would actually be if
they care.

Jim Langston, Sep 11, 2006