الگوریتم فروشنده دوره گرد

[Y@SiN]

الگوریتم فروشنده دوره گرد به زبان سي

// tsp.cpp
// contains the distance matrix for the problem space as  well
//      as several helper functions

#include  <iostream.h>
#include <string.h>
#include  <stdlib.h>
#include "solution.h"
#include  "tsp.h"

/**********************************************************/
//  constructor
tsp::tsp(void)  {
	init_terrain();
}

//  destructor
tsp::~tsp(void)  {

}

/**********************************************************/
void  tsp::init_terrain(void) {
// pre: true
// post: distance matrix has been  initialized
//	distances between 1 and  50
//	time weights set to 1
	int dist_num;	// for random numbers
	int time_num;

	// initialize the  distance array with random values (1 to 50)
	for (int  i=0;i<DISTANCE_COUNT-1;++i) {
		terrain[i][i].dist  = 0;
		terrain[i][i].time  = 1;
		terrain[i][i].res  = 0;

		for  (int j=i+1;j<DISTANCE_COUNT;++j) {
			dist_num  = 1 + (int)((float)MAX_DISTANCE*rand()/(RAND_MAX+1.0));
			time_num  = 1 + (int)((float)MAX_TIME_WEIGHT*rand()/(RAND_MAX+1.0));
			terrain[i][j].dist  = dist_num;
			terrain[i][j].time  = time_num;
			terrain[i][j].res  = dist_num*time_num;
			terrain[j][i].dist  = dist_num;
			terrain[j][i].time  = time_num;
			terrain[j][i].res  = dist_num*time_num;
		}
	}

	#ifdef  DEBUG
	dump_terrain();
	#endif

}

/**********************************************************/
void  tsp::dump_terrain(void) {
// pre: terrain has been initialized
// post:  prints the distance matrix to stdout

	for (int  i=0;i<DISTANCE_COUNT;++i) {
		for  (int j=0;j<DISTANCE_COUNT;++j) {
			cout  << terrain[i][j].dist << "," << terrain[i][j].time << "   ";
		}
		cout  <<  "\n";
	}
}

/**********************************************************/
void  tsp::change_time(void) {
// pre: terrain has been initialized
// post:  randomly changes a time weight for a path

	// choose path to change
	int city1 =  (int)((float)DISTANCE_COUNT*rand()/(RAND_MAX+1.0));
	int  city2 = (int)((float)DISTANCE_COUNT*rand()/(RAND_MAX+1.0));

	//  don't change the time weight within a city
	if (city1 == city2) {
		city2++;
	}

	//  check for a city value out of  bounds
	if (city2 > CITY_COUNT)  {
		city2  = 0;
	}

	//  new time weight
	int time = 1 +  (int)((float)MAX_TIME_WEIGHT*rand()/(RAND_MAX+1.0));

	//  set time weights and compute new time*dist result
	terrain[city1][city2].time =  time;
	terrain[city1][city2].res =  terrain[city1][city2].dist *  time;
	terrain[city2][city1].time =  time;
	terrain[city2][city1].res =  terrain[city2][city1].dist *  time;
}

/**********************************************************/
/*   this wasn't part of the ga plan, just made this for testing

void  tsp::solveall(void) {
// recursively find all tsp solutions

	solution* sol = new  solution();
	solveall(sol);
	delete  sol;
}
*/
/**********************************************************/
/*   this wasn't part of the ga plan, just made this for testing

void  tsp::solveall(solution *s) {
// recursively find all tsp solutions

	if (s->complete() ==  1) {
		cout  << "path complete: ";
		s->dumppath();
		//cout  << "distance: " << s->distance(terrain) << endl;
		//cout  << "travel time: " << s->time(terrain) << endl;

	} else {
		for  (int i=1; i<=CITY_COUNT; ++i) {
			if  (s->visited(i) == 0) {	// take a trip  and continue
							//  but only if the path would be valid
				s->roadtrip(i);
				solveall(s);
				s->backtrack();
			}
		}
	}
}
*/