Thread: 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 = You need to pass by reference:

Code:

randPerm(number, &array);

void randPerm(int N, int *perm[])
{
    /* ... */
    (*perm)[i] = i;
    /* ... */
}

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?

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]);
    }
}

Ok i typed it right in like that, but its still crashing when I run it

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

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

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.

Riiiight, I knew it was some silly mistake, thanks so much for all your help I would have been completely lost!!!

I was just about to ask you why my values aren't getting reseeded correctly. Congratulations, you are a mind reader. Thanks so much!