Thread: Another traveling salesman problem

Ok so i understand conceptually what I have to do. I am having problems with the syntax however. I am dealing with 8 total cities the person has to travel to, including the starting and ending city that are the same. I have decided to go with a brute force method, i.e., solving the total distance for all permutations, and then selecting the shortest one. Here is my code so far:

Code:

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
typedef struct {
double x;
double y;
}city_location;
void permutations( *city)
 void distance( *city)
main() {
city_location *city;
//latitude and longitude converted to xy coordinates with Tucson as origin
//units of meters
city1.x = 0;
city1.y = 0;
city2.x = 2212660;
city2.y = 1142144;
city3.x = 2212660;
city3.y = 1262261;
city4.x = 3480853;
city4.y = 1007221;
city5.x = 3406993;
city5.y = 916664;
city6.x = 1973793;
city6.y = 781752;
city7.x = 575166;
city7.y = 892638;
city8.x = 1313767;
city8.y = 112735;
total_dist = 0;
 
void distance(city_location *city){
double dist;
int I;
for(i=0; i<6; i++){
dist  = sqrt(((x[i+1]*x[i+2])^2)+((y[i+1]*y[i+2])^2));
//store a value for each leg or the trip
double partial_dist = //sum of these values;
double start_dist = sqrt(((x[1])^2)+((y[1])^2));
double end_dist = sqrt(((x[7])^2)+((y[7])^2));
double total_dist = partial_dist + start_dist + end_dist;
if(new_dist < shortest_dist){
//store value and continue loop
}
}

so the things i don't know how to do are:

• how to create all the possible permutations
• how to read all those permutations into my distance function
• how to store various values within a loop and then sum them after loop is finished

Any help at all would be appreciated greatly.

ok so i fixed my distance functions to remove the ^2's and also changed my city coordinates into arrays. can you do that with a struct?

Code:

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
typedef struct {
double x;
double y;
}city_location;
void permutations( *city)
 void distance( *city)
main() {
int j;
city_location *city;
//latitude and longitude converted to xy coordinates with Tucson as origin
//units of meters
city[1].x = 0;
city[1].y = 0;
city[2].x = 2212660;
city[2].y = 1142144;
city[3].x = 2212660;
city[3].y = 1262261;
city[4].x = 3480853;
city[4].y = 1007221;
city[5].x = 3406993;
city[5].y = 916664;
city[6].x = 1973793;
city[6].y = 781752;
city[7].x = 575166;
city[7].y = 892638;
city[8].x = 1313767;
city[8].y = 112735;
total_dist = 0;
for(j=0; j<5040; j++) {
distance(city_location *city);
}
 
 
void distance(city_location *city){
double dist;
int i;
double sum = 0;
for(i=0; i<6; i++){
dist  = sqrt(((x[i+1]*x[i+2])* (x[i+1]*x[i+2]))+((y[i+1]*y[i+2])* (y[i+1]*y[i+2])));
sum = sum + dist;
//store a value for each leg or the trip
double partial_dist = //sum of these values;
double start_dist = sqrt(((x[1])*x[1])+((y[1])*y[1]));
double end_dist = sqrt(((x[7])*x[7])+((y[7])*y[7]));
double total_dist = partial_dist + start_dist + end_dist;
if(new_dist < shortest_dist){
//store value and continue loop
}
}

This is my updated loop. What im confused about is how to create all the different permutations for n=7. I know for n=3:
abc
acb
bac
bca
cab
cba

How would a create an algorithm for n=7? and after i created it how would i save all of them to run through my distance function?
thanks for your help so far

Yes i'm just trying to minimize the total distance traveled. I'm not concerned with other variables. If i were to create a matrix of the distances between each city as you have shown instead of using the distance function i have, I would still need to create all the possible permutations correct?

anyone else got any tips on this?

Originally Posted by tcherco

Yes i'm just trying to minimize the total distance traveled. I'm not concerned with other variables. If i were to create a matrix of the distances between each city as you have shown instead of using the distance function i have, I would still need to create all the possible permutations correct?

I second Salem's suggestion - use a dist[][] (distance) 2D array, and put your figures in there, so when your program needs to know the distance from city 2 to city 3 (and yes, start counting like a C programmer, from zero), then it can just read the dist[2][3], to get that number. More generally, you get the distance from a city, to a certain city, by looking at the number in the dist[from][to] array. Just like the "Distance Between Cities" charts that you frequently see on maps.

This is a huge speed up, since you will only have to generate distances once, between any two cities.

While there are clever ways to *almost* get a guaranteed shortest cycle (it's called a Hamiltonian cycle, btw), the best way for you at this point, would be use the brute force method. That's no problem for only 8 cities. It is an NP-hard problem.

The kind of permutations you want can be generated with swaps and resorts of the digits behind the swaps (if you want them in order, and you do. It makes it very easy to visually check the results). Insertion sort is ideal for this kind of sorting job. Bubble sort is good, here, as well. I don't know the name for this kind of permutation by swapping and resorting, but Google has info on it under "permutations".

I would use a string array with the names of the cities, where Phoenix might be #3, and then in the integer 2D array, the data for Phoenix would be on row 3, so you have that correlation. Now all distances from Phoenix can just be referred to by your program as dis[3][otherCityNumber]. For human eyes though, you can still print out "Phoenix", in your final result.