sem5-pea-proj-1-jm/BranchBound.cpp at master · Ite-2022-pwr/sem5-pea-proj-1-jm · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
#include "BranchBound.h"
#include "Graph.h"
#include <iostream>
#include <algorithm>
#include <chrono>
#include <map>
#include <vector>

using namespace std;


int BranchBound::best_solution_cost = INT_MAX;
chrono::high_resolution_clock::time_point BranchBound::start = chrono::high_resolution_clock::now();
bool BranchBound::kill_recursion = false;
vector<int> BranchBound::best_solution_path = {0};

double BranchBound::iterations = 0;

void BranchBound::solve_lower(Graph* graph, bool is_silent) {

	BranchBound::best_solution_cost = INT_MAX;
	BranchBound::iterations = 0;
    BranchBound::kill_recursion = false;
	vector<bool> visited;
	vector<int> path = {0};
	int bestCost = 0;

    // inicjalizujemy pomocnicz¹ listê booli odpowiedzialn¹ za przechowywanie
    // informacji gdzie ju¿ byliœmy
	for (int i = 1; i < graph->no_vertices; i++) {
		visited.push_back(false);
	}

	BranchBound::start = chrono::high_resolution_clock::now();

    // ustalamy wierzcho³ek pocz¹tkowy jako i zaczynamy rozwi¹zywaæ podproblemy
	BranchBound::solve_lower_recursive( 0, path, graph);
	chrono::high_resolution_clock::time_point t2 = chrono::high_resolution_clock::now();
	double solve_time = chrono::duration_cast<chrono::duration<double>>(t2 - BranchBound::start).count();


	if (!is_silent) {
		cout << '\n';
		cout << "Length: " << BranchBound::best_solution_cost << '\n' << "Path: ";
		cout << BranchBound::best_solution_path[0];
		for (int i = 1; i < BranchBound::best_solution_path.size() - 1; i++)
			cout << "->" << BranchBound::best_solution_path[i];

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


}


void BranchBound::solve_lower_recursive(int currentCost, vector<int>& path, Graph* graph) {

    if (BranchBound::kill_recursion)
        return;

    BranchBound::iterations += 1;

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

        double percentageCompletion = (double)BranchBound::iterations / BranchBound::get_factorial(graph->no_vertices) * 100;
        cout << "Calculated " << percentageCompletion << "% of problem \n";

        BranchBound::kill_recursion = true;
        return;
    }


    // przypadek podstawowy rekurencji : przeszliœmy ca³¹ œcie¿kê
    if (path.size() == graph->no_vertices) {

        // obliczamy powrót do wierzcho³ka pocz¹tkowego
        // jeœli jest mniejszy od aktualnego najlepszego rozwi¹zania, to aktualizujemy
        currentCost += graph->edge_weight(path.back(), 0);
        if (currentCost < BranchBound::best_solution_cost) {
            vector<int> help(path.begin(), path.end());
            help.push_back(0);

            BranchBound::best_solution_path = help;
            BranchBound::best_solution_cost = currentCost;
        }
        return;
    }

    // przechodzimy pêtl¹ po ka¿dym wierzcho³ku w którym jeszcze nie byliœmy
    for (int i = 0; i < graph->no_vertices; i++) {


        // jeœli ju¿ byliœmy w danym wierzcho³ku, to pomijamy
        if (find(path.begin(), path.end(), i) != path.end())
            continue;

        // ograniczenie: jeœli podró¿ do nastêpnego wierzcho³ka by³aby wiêksza b¹dŸ równa
        // obecnie najlepszego, nie rozwijamy podproblemu dla tego wierzcho³ka
        int nextCost = currentCost + graph->edge_weight(path.back(), i);
        if (nextCost >= BranchBound::best_solution_cost)
            continue;

        // Dodajemy nastêpny wierzcho³ek do obecnej trasy i rozwijamy podproblem
        path.push_back(i);
        solve_lower_recursive(nextCost, path, graph);

        if (BranchBound::kill_recursion)
            return;

        // Po obliczeniu podproblemu usuwamy go ze œcie¿ki tzw. backtracking
        path.pop_back();
    }
}


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

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

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

void BranchBound::measure_lower(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();
		BranchBound::solve_lower(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 branch and bound: " << avg_duration / no_times << "s" << endl;
}