#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;
}