 صفحه:    پایین نويسنده موضوع: الگوریتم فروشنده دوره گرد  (دفعات بازدید: 6685 بار)
علی برغمدی
Aiapir Team تشكرها : 20 آفلاین

جنسيت : تعداد ارسال: 92 برنامه نویس شرکت آرین   « : 27 آذر 1388,ساعت 11:55:01 »

کسی الگوریتم فروشنده دوره گرد رو داره؟ خارج شده است

تقدسی
Super Manager تشكرها : 100 آفلاین

جنسيت : تعداد ارسال: 380

هیهات من الذله ...   « پاسخ #1 : 27 آذر 1388,ساعت 14:28:42 »

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

// 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
solveall(s);
s->backtrack();
}
}
}
}
*/ خارج شده است كاربران گرامی : لطفاً قبل از هرگونه فعاليت ابتدا قوانين انجمن را مطالعه  و قبل از ارسال جديد در انجمن جستجو نماييد.
انجمن تخصصی استادان و دانشجویان کامپیوتر ایران  خارج شده است
 صفحه:    بالا
پرش به :