Need help with traveling salesman problem?

This is a discussion on Need help with traveling salesman problem? within the C Programming forums, part of the General Programming Boards category; We are given 10 cities with latitudes x and longitudes y, and we have to figure out what order visited ...

  1. #1
    Registered User
    Join Date
    Feb 2012
    Posts
    19

    Need help with traveling salesman problem?

    We are given 10 cities with latitudes x and longitudes y, and we have to figure out what order visited will give us the shortest distance traveled. We have to:

    1. Create a function that returns an array of a random permutation 1-10 (this will help randomize which cities we visit in what order). I made this called randPerm. [THIS WORKS PERFECTLY].

    2. Write a function that prints out the cities in the order specified by the permutation. I made this called printInGivenOrder. [THIS PRINTS OUT ALL 0's, DOESN'T WORK]

    3. Write a function that generates random order of the cities and searches for the one with the smallest total distance. [ALSO DOESN'T WORK]


    Here is what I have so far:

    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include <math.h>
    
    
    struct City
    {
        float name;
        float x;
        float y;
    };
    
    
    
    
    void randPerm(int N, int perm[])
    {
        srand(time(NULL));
        int i;
        for(i=0;i<N;i++)//initalize numbers
        {
            perm[i] = i;
        }
        for(i=0;i<N;i++)
        {
        int n=rand() % N;
        if(perm[n]<0)     //not unique, try again
          --i;
        else  {
          printf("%d\n", perm[n]);   //got one
          perm[n]=-1;     //mark that index taken,
        }                    //thus marking that number
        }
    }
    
    
    void printInGivenOrder(struct City cityArray[], int perm[])
    {
        int i,num;
        printf("\nOrder of Cities:\n");
        for(i=0;i<10;i++)
        {
            num=perm[i];
            printf("%d\n", cityArray[num].name);
        }
    }
    
    
    
    
    float getTotalDistGivenPerm(int N, struct City cityArray[], int perm[])
    {
        int i;
        int index1,index2;
        float distance,totaldist=0, a1,a2,b1,b2,x,y;
        for(i=1;i<N;i++)
        {
        index1 = perm[i];
        index2 = perm[i-1];
        a1=cityArray[index1].x;
        a2=cityArray[index1].y;
        b1=cityArray[index2].x;
        b2=cityArray[index2].y;
        x=69.1*(a1-b1); //this is just a formula i found online to 
        y=53.0*(a2-b2); //calculate latitude and longitude and convert
        distance=sqrt(x*x + y*y); //to distance
        totaldist=totaldist+distance;
        }
        return totaldist;
    }
    
    
    int main()
    {
        struct City cityArray[10];
        cityArray[0].name=1; //"Ann Arbor";
        cityArray[0].x=42.28;
        cityArray[0].y=-83.75;
        cityArray[1].name=2;// "Austin";
        cityArray[1].x=30.25;
        cityArray[1].y=-97.75;
        cityArray[2].name=3;// "Boston";
        cityArray[2].x=42.36;
        cityArray[2].y=-71.06;
        cityArray[3].name=4;// "Chicago";
        cityArray[3].x=41.88;
        cityArray[3].y=-87.63;
        cityArray[4].name=5;// "Detroit";
        cityArray[4].x=42.33;
        cityArray[4].y=-83.05;
        cityArray[5].name=6;// "Lansing";
        cityArray[5].x=42.73;
        cityArray[5].y=-84.55;
        cityArray[6].name=7;// "Las Vegas";
        cityArray[6].x=36.18;
        cityArray[6].y=-115.14;
        cityArray[7].name=8;// "Los Angeles";
        cityArray[7].x=34.05;
        cityArray[7].y=-118.25;
        cityArray[8].name=9;// "Miami";
        cityArray[8].x=25.79;
        cityArray[8].y=-80.22;
        cityArray[9].name=10;// "Seattle";
        cityArray[9].x=47.61;
        cityArray[9].y=-122.33;
        int number=10;
        int array[10];
        randPerm(number, array);
        printInGivenOrder(cityArray, array);
        float finalDistancefromPerm= getTotalDistGivenPerm(number, cityArray, array);
        printf("\n %f", finalDistancefromPerm);
        return 0;
    }

    My 3 biggest problems:

    1. How do I enter the name of the city into the structure instead of just 1-10? If I chance int name to char name[50] in the structure and enter the name instead, it gives me an error.

    2. Why doesn't my printInGivenOrder function print out the names (or numbers 1-10 right now until I figure out how to use the names of the cities) in the order of the permutation? All it prints out is all 0's

    3. What am I doing wrong in my last function? It also only prints out 1 zero.


    I know my code is kind of sloppy right now, sorry for the inconvenience, but any help would greatly be appreciated! Thanks!

  2. #2
    Registered User
    Join Date
    Dec 2011
    Posts
    795
    #2 = You need to pass by reference:

    Code:
    randPerm(number, &array);
    
    void randPerm(int N, int *perm[])
    {
        /* ... */
        (*perm)[i] = i;
        /* ... */
    }

  3. #3
    Registered User
    Join Date
    Feb 2012
    Posts
    19
    Ok, I changed it to

    Code:
    randPerm(number, &array);
    void randPerm(int N, int *perm[]) { srand(time(NULL)); int i; for(i=0;i<N;i++)//initalize numbers { (*perm[i]) = i; } for(i=0;i<N;i++) { int n=rand() % N; if(perm[n]<0) //not unique, try again --i; else { printf("%d\n", perm[n]); //got one perm[n]=-1; //mark that index taken, } //thus marking that number } }
    I also tried changing all the perm[] to (*perm[]) but now instead of printing out all 0's the program crashes when it reaches this point. Any other ideas?

  4. #4
    Registered User
    Join Date
    Dec 2011
    Posts
    795
    You have to change all of them ._.

    The problem is that your function won't work even if it does compile, here, try something like this:

    Code:
    void randPerm(int N, int *perm[]) 
    {
    
        int i, n1, n2, tmp;
    
    
        for(i=0;i<N;i++)//initalize numbers
            (*perm)[i] = i;
        for(i=0;i<100;i++) { /* replace 100 with however many shuffles you need */
            n1 = arc4random() % N;
            n2 = arc4random() % N;
            
            tmp = (*perm)[n2];
            (*perm)[n2] = (*perm)[n1];
            (*perm)[n1] = tmp; 
    
            printf("%d\n", (*perm)[n1]);
        }
    }

  5. #5
    Registered User
    Join Date
    Feb 2012
    Posts
    19
    Ok i typed it right in like that, but its still crashing when I run it

  6. #6
    Registered User
    Join Date
    Feb 2012
    Posts
    19
    Has anyone been able to figure out why this still keeps crashing or how to put the names of the cities in the structure as char values?
    The problem seems to be with the arc4random for me, I've never used that before...
    I'm really running out of time, please help!
    Last edited by Le23ron; 02-19-2012 at 07:03 PM.

  7. #7
    Registered User
    Join Date
    Dec 2011
    Posts
    795
    > The problem seems to be with the arc4random for me, I've never used that before...
    Then google it! Or just use srand() and rand() again! Jeez, I didn't say you had to use anything I wrote verbatim

    And I need your full/current code to determine the problem.

  8. #8
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,450
    Quote Originally Posted by Le23ron
    2. Why doesn't my printInGivenOrder function print out the names (or numbers 1-10 right now until I figure out how to use the names of the cities) in the order of the permutation? All it prints out is all 0's
    It would not print the numbers since you did not write it to print the numbers.

    Quote Originally Posted by memcpy
    #2 = You need to pass by reference:
    That is already happening: array is converted to a pointer to its first element. Passing the address of array means passing a pointer to the array itself, in which case the function should be declared as:
    Code:
    void randPerm(int N, int (*perm)[10]);
    But that is completely unnecessary. All that has happened is complication introduced by an additional level of indirection.

    Quote Originally Posted by Le23ron
    Has anyone been able to figure out why this still keeps crashing or how to put the names of the cities in the structure as char values?
    To debug a crash, use a debugger: place breakpoints over where you suspect the crash happens, then step through until the crash happens. The bug lies somewhere before the crash point.

    Anyway, you're right: the problem is probably because memcpy's advice is wrong. If you compiled with a sufficiently high warning level, your compiler would likely have informed you as such: the type of the argument and the type of the parameter are not compatible.

    Quote Originally Posted by Le23ron
    The problem seems to be with the arc4random for me, I've never used that before...
    arc4random is non-standard: stick to rand for now.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  9. #9
    Registered User
    Join Date
    Feb 2012
    Posts
    19
    Ok, here is my updated code:

    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include <math.h>
    #include <time.h>
    
    
    
    
    struct City
    {
        float name;
        float x;
        float y;
    };
    
    
    
    void randPerm(int N, int *perm[])
    {
    
    
        srand(time(NULL));
        int i, n1, n2, tmp;
        for(i=0;i<N;i++)//initalize numbers
            (*perm)[i] = i;
        for(i=0;i<N;i++) 
        {
            n1 = rand()%N;
            n2 = rand()%N;
    
    
            tmp = (*perm)[n2];
            (*perm)[n2] = (*perm)[n1];
            (*perm)[n1] = tmp;
    
    
            printf("%d\n", (*perm)[n1]);
        }
    }
    
    
    
    void printInGivenOrder(struct City cityArray[], int *perm[])
    {
        int i,num;
        printf("\nOrder of Cities:\n");
        for(i=0;i<10;i++)
        {
            num=(*perm[i]);
            printf("%d\n", cityArray[num].name);
        }
    }
    
    
    
    
    float getTotalDistGivenPerm(int N, struct City cityArray[], int perm[])
    {
        int i;
        int index1,index2;
        float distance,totaldist=0, a1,a2,b1,b2,x,y;
        for(i=1;i<N;i++)
        {
        index1 = perm[i];
        index2 = perm[i-1];
        a1=cityArray[index1].x;
        a2=cityArray[index1].y;
        b1=cityArray[index2].x;
        b2=cityArray[index2].y;
        x=69.1*(a1-b1);
        y=53.0*(a2-b2);
        distance=sqrt(x*x + y*y);
        totaldist=totaldist+distance;
        }
    
        return totaldist;
    }
    
    
    int main()
    {
        struct City cityArray[10];
        cityArray[0].name=1; //"Ann Arbor";
        cityArray[0].x=42.28;
        cityArray[0].y=-83.75;
        cityArray[1].name=2;// "Austin";
        cityArray[1].x=30.25;
        cityArray[1].y=-97.75;
        cityArray[2].name=3;// "Boston";
        cityArray[2].x=42.36;
        cityArray[2].y=-71.06;
        cityArray[3].name=4;// "Chicago";
        cityArray[3].x=41.88;
        cityArray[3].y=-87.63;
        cityArray[4].name=5;// "Detroit";
        cityArray[4].x=42.33;
        cityArray[4].y=-83.05;
        cityArray[5].name=6;// "Lansing";
        cityArray[5].x=42.73;
        cityArray[5].y=-84.55;
        cityArray[6].name=7;// "Las Vegas";
        cityArray[6].x=36.18;
        cityArray[6].y=-115.14;
        cityArray[7].name=8;// "Los Angeles";
        cityArray[7].x=34.05;
        cityArray[7].y=-118.25;
        cityArray[8].name=9;// "Miami";
        cityArray[8].x=25.79;
        cityArray[8].y=-80.22;
        cityArray[9].name=10;// "Seattle";
        cityArray[9].x=47.61;
        cityArray[9].y=-122.33;
        int number=10;
        int array[10];
    randPerm(number, &array);
        printInGivenOrder(cityArray, &array);
        float finalDistancefromPerm= getTotalDistGivenPerm(number, cityArray, array);
        printf("\n %f", finalDistancefromPerm);
        return 0;
    }

    I guess my questions still are:

    1. Most important question: How do I enter the names of the cities into the structure? If I change the "float name" to "char name[50]" and "cityArray[0].name"= "Ann Arbor" instead of 1 it says "incompatible types in assignment"

    2. Program still crashes when I hit the randPerm function, and I tried the debugger but couldn't figure out what's wrong

  10. #10
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,450
    Quote Originally Posted by Le23ron
    1. Most important question: How do I enter the names of the cities into the structure? If I change the "float name" to "char name[50]" and "cityArray[0].name"= "Ann Arbor" instead of 1 it says "incompatible types in assignment"
    Well, you have to have the name as an array (or a pointer to char, but that's more complicated) as a float won't do for a name. The problem is, you cannot assign to an array. Therefore, you should #include <string.h> and use strcpy or strncpy, e.g.,
    Code:
    strcpy(cityArray[0].name, "Ann Arbor");
    Note that strcpy assumes that the name to be copied has no more than 49 characters (+1 for the null character). This is fine when you are copying from a string literal as long as you are careful, but for user input you need to assume that the user will enter more characters than the array can store.

    Quote Originally Posted by Le23ron
    2. Program still crashes when I hit the randPerm function, and I tried the debugger but couldn't figure out what's wrong
    Change it back to:
    Code:
    void rand Perm(int N, int perm[])
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  11. #11
    Registered User
    Join Date
    Feb 2012
    Posts
    19
    Great, the program doesn't crash now and the second question works.

    I have 1 last question.
    My code:

    Code:
    char name[50]; //for my structure
    
    strcpy(cityArray[0].name, "Ann Arbor");
        cityArray[0].x=42.28;
        cityArray[0].y=-83.75;
        strcpy(cityArray[1].name, "Austin");
        cityArray[1].x=30.25;
        cityArray[1].y=-97.75;
    ............
    
    
    void printInGivenOrder(struct City cityArray[], int perm[])
    {
        int i,num;
        printf("\nOrder of Cities:\n");
        for(i=0;i<10;i++)
        {
            num=(perm[i]);
            printf("%c\n", cityArray[num].name);
        }
    }
    However, it doesn't print out the names of the cities, but rather a single wierd symbol, i.e.








    X


    α







    instead of the names.

  12. #12
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,450
    Since you want to print the name as a string, use %s not %c
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  13. #13
    Registered User
    Join Date
    Feb 2012
    Posts
    19
    Riiiight, I knew it was some silly mistake, thanks so much for all your help I would have been completely lost!!!

  14. #14
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,450
    For randPerm, a more common shuffle algorithm (Knuth/Fisher-Yates) would be along these lines:
    Code:
    for (i = N; i > 1; --i)
    {
        int r = rand() % i;
        tmp = perm[r];
        perm[r] = perm[i];
        perm[i] = tmp;
    }
    You should move the srand call from randPerm to near the top of the main function. (It is okay for now, but if you want to call randPerm multiple times, then that's not good to re-seed each time.)
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  15. #15
    Registered User
    Join Date
    Feb 2012
    Posts
    19
    I was just about to ask you why my values aren't getting reseeded correctly. Congratulations, you are a mind reader. Thanks so much!

Page 1 of 2 12 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Another traveling salesman problem
    By tcherco in forum C Programming
    Replies: 6
    Last Post: 12-05-2011, 08:38 AM
  2. Travelling salesman problem extension
    By XDenasdc in forum C++ Programming
    Replies: 1
    Last Post: 11-08-2011, 10:34 AM
  3. Traveling Salesman Problem - w/ matrix
    By GuiEssence in forum C Programming
    Replies: 0
    Last Post: 11-08-2011, 09:00 AM
  4. Replies: 5
    Last Post: 03-26-2010, 12:22 PM
  5. Travelling salesman problem algorithm
    By Taturana182 in forum C++ Programming
    Replies: 19
    Last Post: 03-24-2010, 09:26 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21