EGALabs/NearestCitySearchMethod.cpp at master · MalchuL/EGALabs · 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
#include "stdafx.h"
#include "NearestCitySearchMethod.h"
using namespace Salesman;
num Salesman::NearestCitySearchMethod::getNeighbor(num city, set X, const matrix & data, value * ref_distance) {
	//numset neighbors;
	num neighbor = X[0];
	value min = data[city - 1][neighbor - 1];
	for (num xk : X) {
		value distance = data[city - 1][xk - 1];
		if (distance < min) {
			min = distance;
			neighbor = xk;
		}
	}
	if (ref_distance != nullptr)*ref_distance = min;
	return neighbor;
}

//Ïåðâûé àðãóìåíò âîçâðàùàåìîãî çíà÷åíèÿ - ïîçèöèÿ, à âòîðîé - êàêîé íàäî âñòàâèòü
constexpr int FROM = 0;
constexpr int TO = 1;

tuple<num, num> Salesman::NearestCitySearchMethod::getNearestNeighbor(set cities, set X, const matrix & data) {

	clog << "cities:";
	printSet(cities);
	clog << endl;
	clog << "X:";
	printSet(X);
	clog << endl;
	value min = 0;
	num neighbor = getNeighbor(cities[0], X, data, &min);


	tuple<num, num> min_tuple(cities[0], neighbor);
	clog << "min distances:[";
	for (num city : cities) {


		value temp_min = 0;
		neighbor = getNeighbor(city, X, data, &temp_min);
		if (temp_min < min) {
			min = temp_min;
			min_tuple = tuple<num, num>(city, neighbor);
		}
		clog << "from " << city << " to " << neighbor << " distance: " << temp_min << "," << endl;
	}
	clog << "]" << endl;
	//clog << "------" << min << "-------";
	clog << "nearest neighbor ";
	clog << "from:" << get<FROM>(min_tuple) << " to:" << get<TO>(min_tuple) << ": distance " << min << endl;
	return min_tuple;
}

void Salesman::NearestCitySearchMethod::printDisplacementPart(DispacementVector & vector, int from, int to) {
	clog << "(";
	for (size_t i = from; i <= to; i++)
	{
		clog << vector.getNum(i) << ",";
	}
	clog << ")";
}

Salesman::NearestCitySearchMethod::NearestCitySearchMethod(matrix data, int randomSeed) :AbstractSalesmanSearchMethod(data), size(data.size()) { srand(randomSeed); }

DispacementVector Salesman::NearestCitySearchMethod::find() {
	printMatrix();
	DispacementVector returnedvector(size);
	set X;
	for (size_t i = 1; i <= size; i++)
	{
		X.push_back(i);
	}
	random_shuffle(X.begin(), X.end());
	num xi = *X.begin();
	num first_x = xi;
	X.erase(X.begin());
	num si = xi;
	int iteration = 1;
	clog << "Iteration " << iteration << endl;
	returnedvector.setNum(iteration, si);
	set usedCities;
	usedCities.push_back(si);
	clog << "si:";
	printDisplacementPart(returnedvector, 1, iteration);
	clog << endl;
	while (X.size() > 0)
	{
		iteration++;

		clog << "Iteration " << iteration << endl;
		//Âû÷èñëèòü îò êàêîãî ãîðîäà äî êàêîãî äîñòèãàåòñÿ ìèíèìóì
		tuple<num, num> nearestCity = getNearestNeighbor(usedCities, X, getMatrix());
		num fromCity = get<FROM>(nearestCity);
		num toCity = get<TO>(nearestCity);
		//
		//Íàéäåì ñðåäè ïåðåñòàíîâêè íàø ãîðîä
		clog << "si before:";
		printDisplacementPart(returnedvector, 1, iteration - 1);
		clog << endl;
		for (int city = 1; city < iteration; city++)
		{
			if (returnedvector.getNum(city) == fromCity) {
				returnedvector.InsertWithRightOffset(city + 1, toCity);
				break;
			}
		}


		usedCities.push_back(toCity);
		X.erase(std::find(X.begin(), X.end(), toCity));
		si = toCity;
		clog << "si after:";
		printDisplacementPart(returnedvector, 1, iteration);
		clog << endl << endl;


	}

	cout << "from " << si << " to " << first_x << ":" << getMatrix()[si - 1][first_x - 1] << endl;
	value distancev = calculateDistance(getMatrix(), returnedvector);
	clog << returnedvector << ":" << distancev << endl;
	return returnedvector;

}

value Salesman::NearestCitySearchMethod::calculateDistance(matrix data, DispacementVector path) {
	value distance = 0;
	for (size_t city = 1; city <= path.getSize(); city++)
	{
		num from = path.getNum(city);

		num to = path.getNum((city + 1)>path.getSize() ? 1 : city + 1);
		//	clog << from <<" "<< to <<" "<<data[from-1][to-1] <<endl;
		//	clog << from<< " " << to <<" "<< data[from - 1][to-1] << " "<<endl;
		distance += data[from - 1][(path.getNum((city) % (path.getSize()) + 1)) - 1];
	}
	clog << endl;
	return distance;
}