coordinates for lowest randomly generated route

[jlmchang]

My code compiles and runs fine. The problem is that I am not sure if it is outputting the correct thing. It should continue to test routes and save the shortest one. Once it reaches the desired number of routes tested it outputs the shortest length as well as the order in which to go to each coordinate to get that distance. I think my code may be outputting the last route tested not the shortest.

  #include <iostream> 
#include <cstdlib>    
#include <time.h>       
#include <cmath> 
#include <algorithm>
#include <iomanip>

using namespace std;

int main()
{
	double routes;
	double current_length;
	double min=10000;
	
	//State coordinates of each house and saves them into 2 1x15 arrays
	double x_coords[15] = {4, 18, 2, 48, 88, 36, 57, 83, 64, 77, 35, 84, 3, 95, 3};
	double y_coords[15] = {58, 1, 25, 96, 22, 50, 12, 97, 4, 53, 63, 12, 42, 88, 45};
	
	//ask the user for the desired number of routes to test
	cout << "How many routes would you like to test? ";
	cin >> routes;
	
	//Set seed based on clock
	int order[15]={0,1,2,3,4,5,6,7,8,9,10,11,12,13,14};
	srand (time(NULL));
	
	//generate a random route and calculate distance, repeat until "routes" has been met
	for ( int i = 0 ; i < routes ; i= i + 1)
	{ 
		random_shuffle(&order[0],&order[15]);
	
		//calculate distance of route using pathagorean theorem
		
		current_length = sqrt(pow(x_coords[order[1]] - x_coords[order[0]],2)+pow(y_coords[order[1]] - y_coords[order[0]],2))+
      		   sqrt(pow(x_coords[order[2]] - x_coords[order[1]],2)+pow(y_coords[order[2]] - y_coords[order[1]],2))+
               sqrt(pow(x_coords[order[3]] - x_coords[order[2]],2)+pow(y_coords[order[3]] - y_coords[order[2]],2))+
               sqrt(pow(x_coords[order[4]] - x_coords[order[3]],2)+pow(y_coords[order[4]] - y_coords[order[3]],2))+
               sqrt(pow(x_coords[order[5]] - x_coords[order[4]],2)+pow(y_coords[order[5]] - y_coords[order[4]],2))+
               sqrt(pow(x_coords[order[6]] - x_coords[order[5]],2)+pow(y_coords[order[6]] - y_coords[order[5]],2))+
               sqrt(pow(x_coords[order[7]] - x_coords[order[6]],2)+pow(y_coords[order[7]] - y_coords[order[6]],2))+
               sqrt(pow(x_coords[order[8]] - x_coords[order[7]],2)+pow(y_coords[order[8]] - y_coords[order[7]],2))+
               sqrt(pow(x_coords[order[9]] - x_coords[order[8]],2)+pow(y_coords[order[9]] - y_coords[order[8]],2))+
               sqrt(pow(x_coords[order[10]] - x_coords[order[9]],2)+pow(y_coords[order[10]] - y_coords[order[9]],2))+
               sqrt(pow(x_coords[order[11]] - x_coords[order[10]],2)+pow(y_coords[order[11]] - y_coords[order[10]],2))+
               sqrt(pow(x_coords[order[12]] - x_coords[order[11]],2)+pow(y_coords[order[12]] - y_coords[order[11]],2))+
               sqrt(pow(x_coords[order[13]] - x_coords[order[12]],2)+pow(y_coords[order[13]] - y_coords[order[12]],2))+
               sqrt(pow(x_coords[order[14]] - x_coords[order[13]],2)+pow(y_coords[order[14]] - y_coords[order[13]],2));
    	
		min = (current_length < min)? current_length:min;  // test whether new route is shorter than previous minimum
	}
	cout << "The shortest route tested is " << min << " miles. " <<endl << "The coordinates are: " << endl;
	for (int i = 0; i < 15; i = i+1)
{
	cout << "(" << x_coords[order[i]] << "," << y_coords[order[i]] << ")" << endl;  //outputs the (x,y) coordinates in the randomized order generated
	// cout << (order[i]) << " " << endl;  //checks if order of route and coordinates match.
}
return 0;
}

[Duthomhas]

Right, because you are saving the shortest distance, but not the order[] that produces that shortest distance. You'll need to save the order too.

You are also not necessarily calculating the shortest distance. You are randomly sampling N out of N! possibilities and returning the best of those.

This particular problem is known to be NP hard. If you wanted to go totally brute force with it, use std::next_permutation() instead of std::random_shuffle().

That would take forever, though, so you can increase the probability of getting a good answer without being deterministic by simply upping the number of tests you do to some large number any order of magnitude less than N!. [edit] which I see you can do by specifying a large value of routes — good job! [/edit]

You can also significantly increase the time the algorithm takes by memoizing all those distance calculations into a simple 2D matrix.

And, if you wanted to spend all kinds of time on it that you probably don’t want to, you can massage the data quite a bit to find good locii in your data and split the data into subroutes that you can get much better results from.

Good luck!

[48T7M4Gy]

Why not use a dataset you know the answer to that you can compare with. Also setup the data so it forces an answer other than the suspect end one.