Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C++ > Traveling salesman problem

Reply
Thread Tools

Traveling salesman problem

 
 
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
 
 
 
 
ivan.leben@gmail.com
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????????


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

 
Reply With Quote
 
 
 
 
Kai-Uwe Bux
Guest
Posts: n/a
 
      09-10-2006
(E-Mail Removed) 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

 
Reply With Quote
 
David Harmon
Guest
Posts: n/a
 
      09-10-2006
On 9 Sep 2006 21:34:47 -0700 in comp.lang.c++,
"(E-Mail Removed)" <(E-Mail Removed)> 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

 
Reply With Quote
 
PC
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.................................
>
> 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...-software.html

Hope that helps,

PC
 
Reply With Quote
 
Jim Langston
Guest
Posts: n/a
 
      09-10-2006
<(E-Mail Removed)> wrote in message
news:(E-Mail Removed) oups.com...
> 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.


 
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, idea, easy to program? JSH Java 61 08-21-2008 06:07 PM
Traveling salesman problem in C whitehatmiracle@gmail.com C++ 0 09-10-2006 04:34 AM
Traveling Salesman Problem KantKwitDansin1 C++ 9 12-12-2004 09:53 PM
complexity of Traveling Salesman Problem? Vinay Adella C Programming 4 09-04-2003 02:54 AM



Advertisments