Ja na studiach zrobiłem coś takiego i się nawet nieźle sprawdza. Jest to proste wyżarzanie z przełączaniem 2-opt.
W pliku data.txt masz po kolei: numer miast, jego współrzędna x, jego współrzędna y.
#include <fstream>
#include <iostream>
#include <vector>
#include <cmath>
#include <cfloat>
#include <cstdio>
#include <cstdlib>
#include <ctime>
float calculateDistanceBetweenPoints(int x1, int y1, int x2, int y2) {
return sqrt((x2 - x1)*(x2 - x1) + (y2 - y1)*(y2 - y1));
}
double calculateDistance(std::vector<int> &vecI, std::vector<int> &vecX, std::vector<int> &vecY) {
double distance = 0;
int i;
for (i = 0; i < vecI.size() - 1; i++) {
distance += calculateDistanceBetweenPoints((int)vecX[vecI[i] - 1], (int)vecY[vecI[i] - 1], (int)vecX[vecI[i + 1] - 1], (int)vecY[vecI[i + 1] - 1]);
}
distance += calculateDistanceBetweenPoints((int)vecX[vecI[i] - 1], (int)vecY[vecI[i] - 1], 0, 0);
return distance;
}
void generate(std::vector<int> &vec, int x, int y) {
int max;
int min;
if (x > y) {
max = x;
min = y;
}
else {
max = y;
min = x;
}
std::vector<int> tempVec;
tempVec = vec;
for (int i = min; i <= max; i++) {
vec[i] = tempVec[max + min - i];
}
}
int main() {
double vectorX_distance = DBL_MAX;
double vectorY_distance = DBL_MAX;
srand(time(NULL));
int i, x, y;
std::vector<int> vecI, vecX, vecY;
std::vector<int> vectorY, vectorX, vextorX1;
std::ifstream infile("data.txt");
while (infile >> i >> x >> y) {
vecI.push_back(i);
vecX.push_back(x);
vecY.push_back(y);
}
double temperature = 1000.0;
double coolingRate = 0.9999;
double absoluteTemperature = 0.005;
i = 0;
vextorX1 = vecI;
while (temperature > absoluteTemperature) {
int random1 = rand() % vextorX1.size();
int random2 = rand() % vextorX1.size();
vectorX = vextorX1;
//generuje nowy
vectorY = vectorX;
generate(vectorY, random1, random2);
vectorX_distance = calculateDistance(vectorX, vecX, vecY);
vectorY_distance = calculateDistance(vectorY, vecX, vecY);
if (vectorX_distance > vectorY_distance) {
vextorX1 = vectorY;
}
else {
if (((double)rand() / (RAND_MAX)) < pow(M_E, -(vectorY_distance - vectorX_distance) / temperature)) {
vextorX1 = vectorY;
}
else {
vextorX1 = vectorX;
}
}
if (i % 1000 == 0) {
std::cout << "\nIlosc iteracji: " << i << "\tNajkrotszy dystans: " << calculateDistance(vextorX1, vecX, vecY) << "\ttemperatura: " << temperature << std::endl;
}
i++;
temperature *= coolingRate;
}
//system("pause");
return 0;
}