#include "stdafx.h"
#include <iostream>
#include <string>
#include <fstream>
#include <math.h>
using namespace std;
class sa_tsp{
public:
void init(int);
void wczytaj(string);
int symulacja();
int* copy(int*);
bool accept(int , int, double);
void run(string, int);
void piszTrase(int*);
int n; //liczba miast
int** koord; //wspolrzedne miast
int** odl; // odleglosci miedzy miastami
int* trasa; //aktualna trasa
int* sasiad; // trasa zmutowana(sąsiad)
int* trasaBest;// najlepsza trasa
int dlg; // dlugosc aktualnej trasy
int dlgBest; //dlugosc najlepszej trasy
static const int maxRows = 5000;
double** stat;
};
void sa_tsp::init(int n){
odl = new int*[n];
koord = new int*[n];
trasa = new int[n];
sasiad = new int[n];
trasaBest = new int[n];
for (int i = 0; i < n; i++){
odl[i] = new int[n];
koord[i] = new int[2];
}
}
// funkcja wczytujaca wspolrzedne z pliku. Nazwa pliku przekazywana jest
// jako parametr wejściowy
void sa_tsp::wczytaj(string plik){
ifstream ifs;
string tekst;
ifs.open(plik);
if (ifs.good()){
while (tekst.find("DIMENSION:") == string::npos){
getline(ifs, tekst);
}
}
else
cout << "Nie udalo sie otworzyc pliku." << endl;
}
int sa_tsp::symulacja()
{
int i, j;
int jj = 0;
// Liczba tras do wyznaczenia temperatury
int ile = 10;
// Długość mutanta
int dlgTemp;
double T = 0;
double Tlen = 0;
double alpha = 0.95;
dlgBest = pow(2,31-1);
// Wyznaczanie startowej trasy
for(i=0; i<ile; i++)
{
makeTour();
Tlen += dlg;
if(dlg<dlgBest)
{
trasaBest = copy(trasa);
dlgBest = dlg;
}
}
T = 600;
cout << "T: " << T << " " << dlgBest << " " << Tlen;
// Początkowa trasa
trasa = copy(trasaBest);
// Długość początkowej trasy
dlg = dlgBest;
bool success = false;
bool found = false;
bool done = false;
// Liczy iteracje
int iter = 0;
// Liczy porażki
int fail = 0;
//Liczy sukcesy
int succ;
while(!done)
{
i = 0;
succ = 0;
success = false;
while(!success)
{
dlgTemp = mutacja1(dlg);
if(accept(dlgTemp, dlg, T))
{
trasa = copy(sasiad);
dlg = dlgTemp;
if(dlgTemp < dlgBest)
{
trasaBest = copy(sasiad);
dlgBest = dlgTemp;
found = true;
succ++;
}
}
i++;
iter++;
if(iter%100 == 0)
{
if(jj < maxRows)
{
stat[jj][0]++;
stat[jj][1] += dlgBest;
jj++;
}
}
success = (i>100*n || succ>10*n);
}
T = T*alpha;
if(found)
{
fail = 0;
}
else
fail++;
done = (fail == 5);
}
cout << "Tend: " << T;
return dlgBest;
}
int* sa_tsp::copy(int* tour)
{
int* tmp = new int[n];
for(int i=0; i<n; i++)
tmp[i] = tour[i];
return tmp;
}
bool sa_tsp::accept(int dlgTemp, int dlg, double T)
{
double yes = false;
float r = 1.0;
do
{
r = static_cast <float> (rand()) / static_cast <float> (RAND_MAX);
}
while(r<0.0 || r>=1.0);
if(dlgTemp<dlg)
{
yes = true;
}
else
{
yes = (r<exp(-(dlgTemp-dlg)/T));
}
return yes;
}
void sa_tsp::run(string fname, int maxEpoch)
{
readData(fname);
computeDist();
//maxEpoch = 1;
for(int epoch = 0; epoch<maxEpoch; epoch++)
{
symulacja();
}
for(int i=0; i<maxRows; i++)
{
if(stat[i][0]>0)
{
stat[i][1] /= stat[i][0];
cout << (100*i) << " " << stat[i][1];
}
}
}
void sa_tsp::piszTrase(int* trasa)
{
for(int i=0; i<n; i++)
cout << trasa[i] << " ";
}
int _tmain(int argc, _TCHAR* argv[])
{
sa_tsp problem = sa_tsp();
problem.wczytaj("kroA100.tsp");
cin.clear();
cin.sync();
cin.get();
return 0;
}
