Dynamic.cpp

#include "Dynamic.h"
#include "Graph.h"
#include <iostream>
#include <cstdlib> 
#include <ctime> 
#include <chrono>
#include <vector>
#include <map>
#include <limits.h>
#include <tuple>
#include <climits>
#include <algorithm>
using namespace std;

double Dynamic::last_visited_vertex = -1;
double Dynamic::minimal_cost = INT_MAX;
vector<int> Dynamic::best_path;
bool Dynamic::kill_recursion = false;
double Dynamic::iterations = 0;
chrono::high_resolution_clock::time_point Dynamic::start = chrono::high_resolution_clock::now();


int Dynamic::solve_partial(int start_vertex, int** memo, int** next_vertex, int** matrix, int no_vertices, int path) {

    if (Dynamic::kill_recursion)
        return 0;

    Dynamic::iterations += 1;


    // sprawdzenie czy nie przekroczyliœmy czasu granicznego
    chrono::high_resolution_clock::time_point t2 = chrono::high_resolution_clock::now();
    int solve_time = chrono::duration_cast<chrono::duration<double>>(t2 - Dynamic::start).count();
    if (solve_time >= Dynamic::get_barrier_time()) {
        cout << "Solve time for Branch and Bound lower of " << Dynamic::get_barrier_time() << "s was reached \n";

        cout << iterations;
        cout << endl << Dynamic::get_factorial(no_vertices) << endl;

        float percentageCompletion = (double)Dynamic::iterations / (double)Dynamic::get_factorial(no_vertices) * 100;

        cout << "Calculated " << percentageCompletion << "% of problem \n";
        Dynamic::kill_recursion = true;
        return 0;
    }

    // jeœli wynik jest ju¿ w memo, zwróæ go
    if (memo[start_vertex][path] != 0) {
        return memo[start_vertex][path];
    }

    // przypadek podstawowy: odwiedzono wszystkie miasta
    if (path == (1 << no_vertices) - 1) {
        memo[start_vertex][0] = matrix[start_vertex][0];
        return matrix[start_vertex][0]; // zwróæ koszt powrotu do startu
    }

    

    int best_partial_result = INT_MAX;

    // przegl¹daj wszystkie miasta i sprawdzaj, czy nie zosta³y odwiedzone
    for (int i = 0; i < no_vertices; i++) {
        // miasto i nie zosta³o odwiedzone
        if (!(path & (1 << i))) {
            // rozwi¹¿ rekurencyjnie dla podzbioru miast
            int new_cost = solve_partial(i, memo, next_vertex, matrix, no_vertices, path | (1 << i));

            // sprawdŸ, czy nowy koszt jest lepszy od aktualnie najlepszego
            if (new_cost + matrix[start_vertex][i] < best_partial_result) {
                best_partial_result = new_cost + matrix[start_vertex][i];
                next_vertex[start_vertex][path] = i;  // zapisz najlepszy nastêpny wierzcho³ek
            }
        }
    }

    // zapisz wynik w memo
    memo[start_vertex][path] = best_partial_result;

    return best_partial_result;
}

void Dynamic::solve(Graph* graph, bool is_silent) {
    Dynamic::minimal_cost = INT_MAX;
    Dynamic::kill_recursion = false;
    Dynamic::iterations = 0;
    Dynamic::start = chrono::high_resolution_clock::now();
    

    int no_vertices = graph->no_vertices;
    Dynamic::best_path.clear();

    int vertex_start = 0;
    int** matrix = graph->data;

    // tworzymy macierz N x 2^N gdzie N jest liczb¹ wierzcho³ków w grafie
    // bêdzie nam s³u¿y³a do markowania gdzie doszliœmy
    // np. binarnie 1011 oznacza, ¿e odwiedziliœmy wierzcho³ki 3,1 i 0
    int** memo = new int* [no_vertices];

    // macierz do œledzenia nastêpnego wierzcho³ka potrzebna przy odtwarzaniu najlepszej œcie¿ki
    int** next_vertex = new int* [no_vertices];  

    for (int i = 0; i < no_vertices; i++) {
        memo[i] = new int[1 << no_vertices]();
        next_vertex[i] = new int[1 << no_vertices]();
    }

    // ustalenie pocz¹tkowej maski: zaczynamy w wierzcho³ku 0
    int path = 1 << 0;

    // zaczynamy rozwi¹zywaæ problem
    auto t1 = std::chrono::high_resolution_clock::now();
    int output = solve_partial(vertex_start, memo, next_vertex, matrix, no_vertices, path);
    auto t2 = std::chrono::high_resolution_clock::now();
    double solve_time = std::chrono::duration_cast<std::chrono::duration<double>>(t2 - t1).count();

    // odtwarzamy najlepsz¹ œcie¿kê
    int current_vertex = vertex_start;
    Dynamic::best_path.push_back(current_vertex);
    for (int i = 0; i < no_vertices - 1; i++) {
        current_vertex = next_vertex[current_vertex][path];
        Dynamic::best_path.push_back(current_vertex);
        path |= (1 << current_vertex);  // aktualizujemy maskê, dodaj¹c odwiedzony wierzcho³ek
    }


    if (!is_silent) {
        cout << "\nLength: " << output << '\n' << "Path: ";
        cout << Dynamic::best_path[0];
        for (int i = 1; i < Dynamic::best_path.size(); i++)
            cout << "->" << Dynamic::best_path[i];

        cout << "\nSolving took " << solve_time << "s\n\n";
    }
    

    // czyszczenie pamiêci
    for (int i = 0; i < no_vertices; i++) {
        delete[] memo[i];
        delete[] next_vertex[i];
    }
    delete[] memo;
    delete[] next_vertex;
}


double Dynamic::get_factorial(double number) {
    if (number <= 1)
        return 1;

    return number * Dynamic::get_factorial(number - 1);
}






double Dynamic::get_barrier_time() {
	return 120;
}
void Dynamic::measure(int no_times, int no_vertices) {
	double avg_duration = 0;

	// tyle razy ile zadano, sortuj i zmierz czas
	for (int _ = 0; _ < no_times; _++) {
        Graph* graph = new Graph(no_vertices);

		chrono::high_resolution_clock::time_point t1 = chrono::high_resolution_clock::now();
		Dynamic::solve(graph, true);
		chrono::high_resolution_clock::time_point t2 = chrono::high_resolution_clock::now();

		double duration = chrono::duration_cast<chrono::duration<double>>(t2 - t1).count();
		//cout << "solving took: " << duration << "s" << endl;
		avg_duration += duration;
	}

	cout << "average solving time for dynamic approach: " << avg_duration / no_times << "s" << endl;
}