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

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

  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
    #3
  4. 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
    #4
  5. 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
    #5
  6. 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
    #6
  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
    #7
  8. 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
    #8
  9. Default User Guest

    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
    #9
  10. jmcgill Guest

    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
    #10
  11. 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
    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
     
    Elijah Cardon, Sep 11, 2006
    #11
  12. CBFalconer Guest

    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,
    which is reading some thread in your own newsreader. All that
    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
    #12
  13. jmcgill Guest

    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
    > 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.
     
    jmcgill, Sep 11, 2006
    #13
  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?

    Please enlighten me......
    Thanx once again
     
    , Sep 11, 2006
    #14
  15. Guest

    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;



    }
    ===========
     
    , Sep 11, 2006
    #15
  16. CBFalconer Guest

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


    --
    Some informative links:
    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
    #16
  17. 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
    #17
  18. wrote:

    > 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>
     
    Spiros Bousbouras, Sep 11, 2006
    #18
  19. <> 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
    #19
  20. 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
    #20
    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. Luc The Perverse
    Replies:
    12
    Views:
    1,324
    Roedy Green
    May 5, 2006
  2. KantKwitDansin1

    Traveling Salesman Problem

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

    complexity of Traveling Salesman Problem?

    Vinay Adella, Sep 3, 2003, in forum: C Programming
    Replies:
    4
    Views:
    1,765
    Jack Klein
    Sep 4, 2003
  4. Erlend Andreas Garberg

    Travelling salesman variation in python

    Erlend Andreas Garberg, Apr 1, 2004, in forum: Python
    Replies:
    20
    Views:
    4,200
    G√ľnter Jantzen
    Apr 2, 2004
  5. Replies:
    5
    Views:
    976
    Jim Langston
    Sep 11, 2006
Loading...

Share This Page