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

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

کد:

---

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

---