Geekly Articles each Day
📜 ⬆️ ⬇️

The traveling salesman task by the Little method in C ++

Studying at the university, everyone had to do all sorts of tasks. Here, the end of the half year comes, the session is in the nose, the beginning of the issuance of course assignments, and I was fortunate enough to be the one who should implement the Little method for the traveling salesman task. So, let's begin.

Who is a salesman? A salesman is a traveling sales agent of a firm that offers customers samples of products and catalogs. His task is to travel around all destinations without having been to twice or return to the starting point.

image


Little Method


The purpose of this method is to search for a Hamiltonian cycle with a minimum value in the graph. To find it, you need to follow the following steps:
')
  1. In each row of the cost matrix, we find the minimum element and subtract it from all the elements of the line. We will do this for non-zero columns. We obtain a cost matrix, each row and each column of which contains at least one zero element.
  2. For each zero element of the matrix, we calculate the coefficient k, which is equal to the sum of the minimum elements of the column and the row of this zero. Choose a zero with the maximum coefficient (if there are several, choose any of them). We bring in the Hamiltonian circuit the corresponding arc.
  3. Delete the row and column, at the intersection of which the selected zero.
  4. We check the graph for the presence of cusps, if there are any, then we change their value to the maximum. Repeat the previous steps until there is a matrix of order 2.
  5. We bring in the Hamiltonian circuit missing arcs. We get the desired cycle.

Implementation


To further expand and work with other algorithms, create the Algorithm class:

Algorithm
//Algorithm.h class Algorithm { public: char* name = "Algorithm"; //   std::vector<std::vector<int>> data; //   () Algorithm(); Algorithm(std::vector<std::vector<int>>); Algorithm(char*); bool LoadData(std::vector<std::vector<int>>); bool LoadData(char*); virtual void Run(); //     protected: int GetStrCount(std::ifstream&); //      int GetColCount(std::ifstream&); //      virtual bool validateData(); //      .   Run() };


As seen above, methods for loading data from a file and manually will be implemented here. Their implementation can be found in the application.

Next, create a class of the algorithm that interests us. In our case, LittleAlgorithm.

LittleAlgorithm
 class LittleAlgorithm : public Algorithm { public: vector<pair<int,int>> result; // .      LittleAlgorithm(); LittleAlgorithm(vector<vector<int>>); LittleAlgorithm(char*); virtual void Run(); private: enum check{Row, Col}; int getMin(vector<vector<int>>, int, check); //    / void matrixProcedure(vector<vector<int>>); //       void showMatrix(vector<vector<int>>); //   int getResultSum(); //      virtual bool validateData(); };


Implementing helper methods:

Other
 void LittleAlgorithm::Run() { name = "Little algorithm"; Algorithm::Run(); matrixProcedure(vector<vector<int>>(data)); } int LittleAlgorithm::getMin(vector<vector<int>> matrix, int sel, check pos) { int min = INT32_MAX; for (int i = 0; i < matrix[sel].size() - 1; i++) switch (pos) { case LittleAlgorithm::Row: if (min > matrix[sel][i]) min = matrix[sel][i]; break; case LittleAlgorithm::Col: if (min > matrix[i][sel]) min = matrix[i][sel]; break; } return min; } void LittleAlgorithm::showMatrix(vector<vector<int>> temp) { std::cout << endl; std::cout << "\t"; for (int i = 0; i < temp[temp.size() - 1].size() - 1; i++) { std::cout << temp[temp.size() - 1][i] << "\t"; } std::cout << endl; std::cout << "\t"; for (int i = 0; i < temp[0].size(); i++) for (int j = 0; j<6; j++) std::cout << "_"; std::cout << endl <<endl; for (int i = 0; i < temp.size() - 1; i++) { std::cout << temp[i][temp.size() - 1] << " | " << "\t"; for (int j = 0; j < temp[i].size() - 1; j++) if(temp[i][j] != INT32_MAX && j != temp.size() - 1)std::cout << temp[i][j] << "\t"; else std::cout << "inf" << "\t"; std::cout << endl; } std::cout << endl << endl; } int LittleAlgorithm::getResultSum() { int sum = 0; for (int i = 0; i < result.size(); i++) sum += data[result[i].first - 1][result[i].second - 1]; return sum; } bool LittleAlgorithm::validateData() { //             for (int i = 0; i < data.size(); i++) for (int j = 0; j < data[i].size(); j++) if (data[i][j] == 0) data[i][j] = INT32_MAX; vector<vector<int>> temp(data); for (int i = 0; i < data.size(); i++) data[i].push_back(i + 1); vector<int> numeration; for (int i = 0; i < data[0].size(); i++) numeration.push_back(i + 1); data.push_back(numeration); return true; }


And here is the actual method itself, which implements the Little method:

matrixProcedure
 void LittleAlgorithm::matrixProcedure(vector<vector<int>> matrix) { //       if (matrix.size() - 1 > 2){ vector<int> vertexes; for (int i = 0; i < result.size(); i++) { vertexes.push_back(result[i].first); vertexes.push_back(result[i].second); } for (int i = 0; i < vertexes.size(); i++) { pair<int, int> elem(INT32_MAX, INT32_MAX), elem1(INT32_MAX, INT32_MAX); for (int j = 0; j < vertexes.size(); j++) { if (vertexes[i] != vertexes[j]) { for (int k = 0; k < matrix[matrix.size() - 1].size() - 1; k++) { if (vertexes[i] == matrix[k][matrix[k].size() - 1]) elem.first = k; if (vertexes[j] == matrix[k][matrix[k].size() - 1]) elem1.first = k; } for (int k = 0; k < matrix.size() - 1; k++) { if (vertexes[i] == matrix[matrix.size() - 1][k]) elem.second = k; if (vertexes[j] == matrix[matrix.size() - 1][k]) elem1.second = k; } } } for (int i = 0; i < matrix.size() - 1; i++) for (int j = 0; j<matrix.size() - 1; j++) if (i == elem1.first && j == elem1.second) matrix[elem1.first][elem1.second] = INT32_MAX; for (int i = 0; i < matrix.size() - 1; i++) for (int j = 0; j < matrix.size() - 1; j++) if (i == elem.first && j == elem.second) matrix[elem.first][elem.second] = INT32_MAX; } } //      for (int i = 0; i < matrix.size() - 1; i++) { int min = 0; if ((min = getMin(matrix, i, check::Row)) == INT32_MAX) { showMatrix(matrix); std::cout << endl << "Bad road" << endl; return; } if ((min = getMin(matrix, i, check::Row)) != 0) for (int j = 0; j < matrix[i].size() - 1; j++) if(matrix[i][j] != INT32_MAX) matrix[i][j] -= min; } //      for (int i = 0; i < matrix[matrix.size() - 1].size() - 1; i++) { int min = 0; if ((min = getMin(matrix, i, check::Col)) == INT32_MAX) { showMatrix(matrix); std::cout << endl << "Bad road" << endl; return; } if ((min = getMin(matrix, i, check::Col)) != 0) for (int j = 0; j < matrix.size() - 1; j++) if (matrix[j][i] != INT32_MAX) matrix[j][i] -= min; } //    int Max = 0; for (int i = 0; i < matrix.size() - 1; i++) for (int j = 0; j < matrix[i].size() - 1; j++) if (matrix[i][j] == 0) { matrix[i][j] = INT32_MAX; int max = (getMin(matrix, i, check::Row) == INT32_MAX || getMin(matrix, j, check::Col) == INT32_MAX)? INT32_MAX: getMin(matrix, i, check::Row) + getMin(matrix, j, check::Col); if (max > Max) Max = max; matrix[i][j] = 0; } //       Max vector<pair<int, int>> Maxs; for (int i = 0; i < matrix.size() - 1; i++) for (int j = 0; j < matrix[i].size() - 1; j++) if (matrix[i][j] == 0) { matrix[i][j] = INT32_MAX; int max = (getMin(matrix, i, check::Row) == INT32_MAX || getMin(matrix, j, check::Col) == INT32_MAX) ? INT32_MAX : getMin(matrix, i, check::Row) + getMin(matrix, j, check::Col); if (max == Max) Maxs.push_back(pair<int, int>(matrix[i][matrix.size() - 1], matrix[matrix.size() - 1][j])); matrix[i][j] = 0; } //    std::cout << "Maxs - "; for (int i = 0; i < Maxs.size(); i++) std::cout << Maxs[i].first << " " << Maxs[i].second << "\t"; std::cout << endl; //  showMatrix(matrix); std::cout << endl; //       if (Maxs.size() == 0) { std::cout << "Bad road." << endl; return; } for (int i = 0; i < Maxs.size(); i++) { //      result.push_back(Maxs[i]); //    1,       if (matrix.size() - 1 == 1) { for (int i = 0; i < result.size(); i++) std::cout << "(" << result[i].first << ", " << result[i].second << ")\t"; std::cout << endl; std::cout << "Result: " << getResultSum() << endl; result.pop_back(); return; } //             vector<vector<int>> temp(matrix); pair<int, int> elem(INT32_MAX, INT32_MAX), elem1(INT32_MAX, INT32_MAX); for (int j = 0; j < temp[temp.size() - 1].size() - 1; j++) { if (Maxs[i].first == temp[j][temp[j].size() - 1]) elem.first = j; if (Maxs[i].second == temp[j][temp[j].size() - 1]) elem1.first = j; } for (int j = 0; j < temp.size() - 1; j++) { if (Maxs[i].second == temp[temp.size() - 1][j]) elem.second = j; if (Maxs[i].first == temp[temp.size() - 1][j]) elem1.second = j; } for(int i = 0; i < temp.size() - 1; i++) for(int j = 0;j<temp.size() - 1; j++) if(i == elem1.first && j == elem1.second) temp[elem1.first][elem1.second] = INT32_MAX; for (int j = 0; j < temp[temp.size() - 1].size(); j++) temp[j].erase(temp[j].begin() + elem.second); temp.erase(temp.begin() + elem.first); //         matrixProcedure(temp); //       result.pop_back(); } }


Result


For example, for the matrix:

0 5 8 10 0 0 3 6
5 0 2 0 0 0 0 1
8 2 0 4 5 6 0 7
10 0 4 0 12 9 7 0
0 0 5 12 0 9 0 12
0 0 6 9 9 0 8 0
3 0 0 7 0 8 0 2
6 1 7 0 12 0 2 0

The result will be:

Result
Little algorithm:
Maxs - 1 7 7 1

1 2 3 4 5 6 7 8
______________________________________________________

1 | inf 2 5 5 inf inf 0 3
2 | 3 inf 1 inf inf inf inf 0
3 | 5 0 inf 0 0 0 inf 5
4 | 5 inf 0 inf 5 1 3 inf
5 | inf inf 0 5 inf 0 inf 7
6 | inf inf 0 1 0 inf 2 inf
7 | 0 inf inf 3 inf 2 inf 0
8 | 4 0 6 inf 8 inf 1 inf

Maxs - 7 8

1 2 3 4 5 6 8
________________________________________________

2 | 0 inf 1 inf inf inf 0
3 | 2 0 inf 0 0 0 5
4 | 2 inf 0 inf 5 1 inf
5 | inf inf 0 5 inf 0 7
6 | inf inf 0 1 0 inf inf
7 | inf inf inf 3 inf 2 0
8 | 1 0 6 inf 8 inf inf

Maxs - 8 2

1 2 3 4 5 6
__________________________________________

2 | 0 inf 1 inf inf inf
3 | 2 0 inf 0 0 0
4 | 2 inf 0 inf 5 1
5 | inf inf 0 5 inf 0
6 | inf inf 0 1 0 inf
8 | inf 0 6 inf 8 inf

Maxs - 2 3

1 3 4 5 6
____________________________________

2 | inf 0 inf inf inf
3 | 0 inf 0 0 0
4 | 0 0 inf 5 1
5 | inf 0 5 inf 0
6 | inf 0 1 0 inf

Maxs - 4 1

1 4 5 6
______________________________

3 | inf 0 0 0
4 | 0 inf 5 1
5 | inf 5 inf 0
6 | inf 1 0 inf

Maxs - 5 6 6 4

4 5 6
________________________

3 | inf 0 0
5 | 4 inf 0
6 | 0 0 inf

Maxs - 3 5 6 4

4 5
__________________

3 | inf 0
6 | 0 inf

Maxs - 6 4

4
____________

6 | 0

(1, 7) (7, 8) (8, 2) (2, 3) (4, 1) (5, 6) (3, 5) (6, 4)
Result: 41
Maxs - 3 5

5
____________

3 | 0

(1, 7) (7, 8) (8, 2) (2, 3) (4, 1) (5, 6) (6, 4) (3, 5)
Result: 41
Maxs - 3 5 5 6

5 6
__________________

3 | 0 0
5 | inf 0

Maxs - 5 6

6
____________

5 | 0

(1, 7) (7, 8) (8, 2) (2, 3) (4, 1) (6, 4) (3, 5) (5, 6)
Result: 41
Maxs - 3 5

5
____________

3 | 0

(1, 7) (7, 8) (8, 2) (2, 3) (4, 1) (6, 4) (5, 6) (3, 5)
Result: 41
Maxs - 2 8

2 3 4 5 6 7 8
________________________________________________

1 | 0 3 3 inf inf inf 1
2 | inf 1 inf inf inf inf 0
3 | 0 inf 0 0 0 inf 5
4 | inf 0 inf 5 1 2 inf
5 | inf 0 5 inf 0 inf 7
6 | inf 0 1 0 inf 1 inf
8 | 0 6 inf 8 inf 0 inf

Maxs - 3 2

2 3 4 5 6 7
__________________________________________

1 | inf 0 0 inf inf inf
3 | 0 inf 0 0 0 inf
4 | inf 0 inf 5 1 1
5 | inf 0 5 inf 0 inf
6 | inf 0 1 0 inf 0
8 | inf 0 inf 2 inf inf

Maxs - 1 4 8 5

3 4 5 6 7
____________________________________

1 | inf 0 inf inf inf
4 | 0 inf 5 1 1
5 | 0 5 inf 0 inf
6 | 0 1 0 inf 0
8 | inf inf 0 inf inf

Maxs - 6 7 8 5

3 5 6 7
______________________________

4 | inf 4 0 inf
5 | 0 inf 0 inf
6 | 0 0 inf 0
8 | inf 0 inf inf

Maxs - 4 5 5 3 5 6 8 5

3 5 6
________________________

4 | inf 0 inf
5 | 0 inf 0
8 | inf 0 inf

3 6
__________________

5 | 0 0
8 | inf inf

Bad road

5 6
__________________

4 | 0 inf
8 | 0 inf

Bad road

3 5
__________________

4 | inf 0
8 | inf 0

Bad road

3 6
__________________

4 | inf inf
5 | 0 0

Bad road
Maxs - 4 6 5 6 6 3 6 7

3 6 7
________________________

4 | inf 0 inf
5 | inf 0 inf
6 | 0 inf 0

3 7
__________________

5 | inf inf
6 | 0 0

Bad road

3 7
__________________

4 | inf inf
6 | 0 0

Bad road

6 7
__________________

4 | 0 inf
5 | 0 inf

Bad road

3 6
__________________

4 | inf 0
5 | inf 0

Bad road
Maxs - 1 4

3 4 6 7
______________________________

1 | inf 0 inf inf
4 | 0 inf 1 1
5 | inf 5 0 inf
6 | 0 1 inf 0

Maxs - 4 6 5 6 6 3 6 7

3 6 7
________________________

4 | inf 0 inf
5 | inf 0 inf
6 | 0 inf 0

3 7
__________________

5 | inf inf
6 | 0 0

Bad road

3 7
__________________

4 | inf inf
6 | 0 0

Bad road

6 7
__________________

4 | 0 inf
5 | 0 inf

Bad road

3 6
__________________

4 | inf 0
5 | inf 0

Bad road

Naturally, the complete solution output and the output of all branches can be turned off. Maybe I did a lot of extra work, but I hope my article will help you with something.

→ Source Files

Source: https://habr.com/ru/post/316014/

More articles:


All Articles