Zadanie: Rozwiąż problem komiwojażera metoda funkcji nagród i kar.

0

Cześć jak w temacie, mam do rozwiązania ten problem (lub jego częściowe rozwiązanie) jako zadanie na studiach. W sieci można znaleźć kilkanaście implementacji dla tego problemu Niestety leżę troszeczkę z algorytmiki i nie bardzo wiem z jakiego algorytmu mogę skorzystać. Z tego co czytałem, mogę wykorzystać algorytmy genetyczne. Czy ktoś jest wstanie mi podpowiedzieć, jak ugryźć ten problem? Z jakiego algorytmu skorzystać?

Dodam, że to treść całego zadania więc dane mogą być dowolne.

Ew. będę wdzięczny za podrzucenie jakichś materiałów :)

Znalazłem np. coś takiego:

0

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

1 użytkowników online, w tym zalogowanych: 0, gości: 1