BruteForce.cpp

#include "BruteForce.h"
#include "Graph.h"
#include <iostream>
#include <algorithm>
#include <chrono>
#include <vector>
using namespace std;

void BruteForce::solve(Graph* graph, bool is_silent) {
    double solve_time = 0;

    // Liczba wierzcho³ków pomniejszona o 1 (pomijamy 0)
    int num_vertices = graph->no_vertices - 1;
    vector<int> currentPermutation(num_vertices);

    // Inicjalizujemy permutacjê liczbami od 1 do n-1
    for (int i = 0; i < num_vertices; i++) {
        currentPermutation[i] = i + 1;
    }

    int minimalDistance = -1;
    vector<int> bestPermutation;

    double permutationsCalculated = 0;
    do {
        chrono::high_resolution_clock::time_point t1 = chrono::high_resolution_clock::now();
        int currentDistance = 0;
        int startVertex = 0;  // Zaczynamy od wierzcho³ka 0

        // Obliczamy trasê, zaczynaj¹c od wierzcho³ka 0
        currentDistance += graph->edge_weight(startVertex, currentPermutation[0]);

        // Przechodzimy przez pozosta³e wierzcho³ki w permutacji
        for (int j = 0; j < num_vertices - 1; j++) {
            currentDistance += graph->edge_weight(currentPermutation[j], currentPermutation[j + 1]);
        }

        // Dodajemy krawêdŸ powrotn¹ do wierzcho³ka 0
        currentDistance += graph->edge_weight(currentPermutation[num_vertices - 1], startVertex);

        // Je¿eli znaleziono lepsze rozwi¹zanie ni¿ obecne, zapisujemy je
        if (currentDistance < minimalDistance || minimalDistance == -1) {
            minimalDistance = currentDistance;
            bestPermutation = currentPermutation;
        }

        permutationsCalculated++;

        chrono::high_resolution_clock::time_point t2 = chrono::high_resolution_clock::now();
        solve_time += chrono::duration_cast<chrono::duration<double>>(t2 - t1).count();
        if (solve_time >= BruteForce::get_barrier_time()) {
            std::cout << "Solve time for brute force of " << BruteForce::get_barrier_time() << "s was reached \n";

            std::cout << BruteForce::get_factorial(graph->no_vertices - 1) << " " << permutationsCalculated << '\n';
            double percentageCompletion = (double)permutationsCalculated / (double)BruteForce::get_factorial(graph->no_vertices - 1) * 100;
            std::cout << "Calculated " << percentageCompletion << "% of problem\n";
            return;
        }

    } while (next_permutation(currentPermutation.begin(), currentPermutation.end()));

    if (is_silent)
        return;

    // Wypisujemy rozwi¹zanie
    std::cout << '\n';
    std::cout << "Length: " << minimalDistance << '\n' << "Path: ";
    std::cout << "0 -> ";
    for (int vertex : bestPermutation) {
        std::cout << vertex << " -> ";
    }
    std::cout << "0\n";
    std::cout << "Solving took " << solve_time << "s\n\n";
}


double BruteForce::get_barrier_time() {
    return 120;
}

void BruteForce::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();
        BruteForce::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();
        avg_duration += duration;
    }

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



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

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