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

[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();
}
}
}
}
*/