sol.cpp

TSP问题的一个类库 有源代码和stl

/* 
   travelsalesman by Kai Schutte ([e-mail])
   started Feb 8th 2000, file: sol.cpp
   personal research for evolutionary computation (IEEE Spectrum Magazine, Feb '00)
   http://www.webpatterns.net/
*/

/*
  Copyright (C) 2000 Kai Schutte
  
  This program is free software; you can redistribute it and/or
  modify it under the terms of the GNU General Public License
  as published by the Free Software Foundation; either version 2
  of the License, or (at your option) any later version.
  
  This program is distributed in the hope that it will be useful,
  but WITHOUT ANY WARRANTY; without even the implied warranty of
  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  GNU General Public License for more details.
  
  You should have received a copy of the GNU General Public License
  along with this program; if not, write to the Free Software
  Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
*/

#include "sol.h"
#include <stdlib.h>
#include <iostream.h>
#include <sys/time.h>
#include <unistd.h>
#include <math.h>
#include <malloc.h>
#include "../include/list"

ccity::ccity(cmap* city_map) {
  m = city_map;
}

ccity::~ccity() {
}

float ccity::calc_distances() {
  distance = 0;
  int size = sol.size()-1;
  list<int>::iterator i=sol.begin();
  list<int>::iterator k=sol.begin();
  k++;
  while (size) {
    distance += m->get_distance((*i), (*k));
    i++;
    k++;
    size--;
  }
  return distance;
}

void ccity::create_rand_sol() {
  struct timeval tv;
  int size = m->get_count();
  int city_reg[size];
  gettimeofday(&tv, NULL);
  srand(tv.tv_usec);
  for (int t=0; t<size; t++) 
    city_reg[t] = 0;
  int t;
  for (t=0; t<size; t++) {
    int try_city_id = rand() % size;
    while (city_reg[try_city_id])
      try_city_id = (try_city_id + 1) % size;
    city_reg[try_city_id] = 1;
    sol.push_back(try_city_id);
  }
}

void ccity::create_vari_sol() {
  struct timeval tv;
  gettimeofday(&tv, NULL);
  srand(tv.tv_usec);
  int size = sol.size();
  int first_cut = rand()%(size);
  list<int>::iterator i=sol.begin();
  while (first_cut) {
    i++;
    first_cut--;
  }
  int temp = (*i);
  sol.erase(i);
  first_cut = rand()%(size-1);
  i = sol.begin();
  while (first_cut) {
    i++;
    first_cut--;
  }
  sol.insert(i, temp);
}

void ccity::operator =(const ccity& b) {
  sol = b.sol;
  distance = b.distance;
}

void ccity::copy(const ccity& b) {
  sol = b.sol;
  distance = b.distance;
}