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
    #1
    1. Advertising

  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
    #2
    1. Advertising

  3. Kai-Uwe Bux Guest

    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::eek: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
    #3
  4. David Harmon Guest

    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
    #4
  5. PC 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????????
    >


    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
    #5
  6. Jim Langston Guest

    <> 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
    #6
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. KantKwitDansin1

    Traveling Salesman Problem

    KantKwitDansin1, Dec 11, 2004, in forum: C++
    Replies:
    9
    Views:
    5,538
    Surendra Singhi
    Dec 12, 2004
  2. Vinay Adella

    complexity of Traveling Salesman Problem?

    Vinay Adella, Sep 3, 2003, in forum: C Programming
    Replies:
    4
    Views:
    1,763
    Jack Klein
    Sep 4, 2003
  3. Replies:
    0
    Views:
    646
  4. JSH
    Replies:
    61
    Views:
    1,527
    Michael Press
    Aug 21, 2008
  5. Ruby Quiz
    Replies:
    17
    Views:
    307
    Rick DeNatale
    Apr 29, 2009
Loading...

Share This Page