# Thread: Need help with traveling salesman problem?

1. ## 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;
}
}

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

Code:
```randPerm(number, &array);

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

3. 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. 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. Ok i typed it right in like that, but its still crashing when I run it

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

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

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.

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.

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.

9. 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;
}

}

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

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[])`

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

α

ö

ä

12. Since you want to print the name as a string, use %s not %c

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

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

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