-
Notifications
You must be signed in to change notification settings - Fork 0
/
tsp.hpp
56 lines (37 loc) · 1.8 KB
/
tsp.hpp
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
//
// Created by Julia on 16.11.2019.
//
#ifndef UNTITLED1_TSP_HPP
#define UNTITLED1_TSP_HPP
#include <iostream>
#include <utility>
#include <vector>
#include <limits>
#include <map>
double get_forbidden_cost();
class TSP_cost_matrix {
public:
// INICJALIZACJA ZMIENNYCH I STAŁYCH
using vector = std::vector<double>;
using matrix = std::vector<std::vector<double>>;
using ulong = unsigned long long;
double INF = get_forbidden_cost();
double low_bound = 0;
using register_t1 = std::map<double, std::vector<int>>;
std::vector<int> rows;
std::vector<int> cols;
std::vector<std::vector<int>> visited;
void rows_cols(matrix &cost_matrix1);
void reduce_all_rows(matrix &cost_matrix1, std::vector<double> min); // REDUKACJA WARTOŚCI W RZĘDACH
vector find_min(matrix cost_matrix1); // ZNAJDYWANIE MINIMUM W MACIERZY
void reduce_all_cols(matrix &cost_matrix1); // REDUKCJA W KOLUMNACH
static void transform(matrix &cost_matrix1, int k, int l); // TRANSPONOWANIE MACIERZY
double sum_min_val(matrix cost_matrix1, int i, int j); // SUMA MINIMALNYCH WARTOŚCI (DROGA)
int if_visited(int i, int j); // SPRAWDZANIE CZY DANY PKT BYŁ ODWIEDZONY
std::vector<int> find_next_path(matrix cost_matrix1); // ZNAJDYWANIE DROGI
void delete_row_col(matrix &cost_matrix1, int i, int j); // USUWANIE KOLUMN I PUNKTÓW
void del_point(matrix &cost_matrix1, int i, int j);
std::vector<std::vector<int>> findBestPath(matrix cost_matrix1);
};
std::vector<int> tsp(std::vector<std::vector<double>> cost_matrix1);
#endif //UNTITLED1_TSP_HPP