Untitled

#include "DP.h"

//glowna funkcja rozwiazujaca TSP
int DP::TSP(int** mainMatrix, int mainSize) {
    size = mainSize;
    Matrix = new int* [size];
    dp = new int* [1 << size];
    routeDecisions = new int* [1 << size];

    for (int i = 0; i < size; i++) {
        Matrix[i] = new int[size];
        for (int j = 0; j < size; j++) {
            Matrix[i][j] = mainMatrix[i][j];
        }
    }

    for (int i = 0; i < (1 << size); i++) {
        dp[i] = new int[size];
        routeDecisions[i] = new int[size];
        for (int j = 0; j < size; j++) {
            dp[i][j] = INT_MAX;
            routeDecisions[i][j] = INT_MAX;
        }
    }

    lastVertex = 0;

    int min_distance = solve(1, 0);

    delete[] dp;
    delete[] Matrix;

    return min_distance;
}

int DP::solve(int mask, int current) {
    if (mask == (1 << size) - 1) {              //jesli wszystkie miasta odwiedzone
        return Matrix[current][0];
    }

    if (dp[mask][current] != INT_MAX) {
        return dp[mask][current];
    }

    int min_distance = INT_MAX;
    int next_vertex = -1;

    for (int next = 0; next < size; next++) {
        if ((mask & (1 << next)) == 0) {            //jesli miasto nie zostało odwiedzona
            int new_distance = Matrix[current][next] + solve(mask | (1 << next), next);
            if (new_distance < min_distance) {
                min_distance = new_distance;
                next_vertex = next;
            }
        }
    }

    routeDecisions[mask][current] = next_vertex;
    return dp[mask][current] = min_distance;
}

//funnkcja wyswietlajaca finalna sciezke
void DP::show() {
    int mask = 1;
    int prevVertex;
    int currentVertex = lastVertex;

    cout << "0";

    while (mask != (1 << size) - 1) {
        int nextVertex = routeDecisions[mask][currentVertex];
        cout << "->" << nextVertex;
        mask |= (1 << nextVertex);
        currentVertex = nextVertex;
    }

    cout << "0" << endl;

    delete[] routeDecisions;
}