Solving the traveling salesman problem using the branch and bound method
Hello, Habr! Implementing various algorithms for finding the lowest-cost Hamiltonian cycle, I came across a publication offering my own version. After trying the case, I got the wrong answer:
Further searches on the Internet did not bring the expected result: either a difficult theoretical description for non-mathematicians, or an understandable one, but with errors.
')
Under the cat you will have to wait for the corrected algorithm and the online calculator.
The method itself, published by Little, Mertie, Sweeney, and Karel in 1963, is applicable to many NP-complete problems, and is a very theoretically material that you cannot immediately use as a traveling salesman without good knowledge of English and mathematics.
Briefly about the method - it is a complete enumeration of all possible options with the screening of obviously non-optimal solutions.
There was only one mistake - one should choose a set with a minimum boundary for splitting from all possible paths, and not from two obtained as a result of the last splitting of children.
But the solution with the corrected algorithm:
The answer is: the path: 3 => 4 => 2 => 1 => 5 => 3 length: 41
As you can see, including the edge 5: 2 in the decision will be a mistake. Q.E.D
Graph comparing the method of branches and borders and time spent for a random table from 5x5 to 10x10:
The graph of the maximum and minimum time spent for matrices from 5x5 to 66x66.
You can try with a detailed solution here .
Measurement data were obtained from 100 random matrices. not a good number, but a general idea.
Sources on GitHub (updated).
Further searches on the Internet did not bring the expected result: either a difficult theoretical description for non-mathematicians, or an understandable one, but with errors.
')
Under the cat you will have to wait for the corrected algorithm and the online calculator.
The method itself, published by Little, Mertie, Sweeney, and Karel in 1963, is applicable to many NP-complete problems, and is a very theoretically material that you cannot immediately use as a traveling salesman without good knowledge of English and mathematics.
Briefly about the method - it is a complete enumeration of all possible options with the screening of obviously non-optimal solutions.
Corrected algorithm to find a really minimal route.
1. Calculate the smallest element in each row (reduction constant for a string)
2. Go to the new cost matrix, subtracting from each row its constant cast
3. Calculate the smallest element in each column (reduction constant for a column)
4. We proceed to the new cost matrix, subtracting from each column its constant of reduction.
As a result, we have a cost matrix, in which in each row and in each column there is at least one zero element.
5. We calculate the border at this stage as the sum of reduction constants for columns and rows (this border will be the cost, less than which it is impossible to build the desired route)
1. The calculation of the penalty for non-use for each zero element of the reduced cost matrix.
The penalty for not using an element with an index (h, k) in the matrix means that this edge is not included in our route, and therefore the minimum cost of “not using” this edge is equal to the sum of the minimum elements in row h and column k.
a) We are looking for all zero elements in the matrix
b) For each of them we consider his penalty for non-use.
c) Select the element to which the maximum penalty corresponds (any, if there are several)
2. Now we divide our set S into sets — containing an edge with a maximum penalty (S w ) and not containing this edge (S w / o ).
3. Calculate cost estimates for routes that are included in each of these sets.
a) For the set S w / o, everything is simple: since we do not take the corresponding edge with the maximum penalty (h, k), then for it the cost estimate is equal to the estimate of the cost of the set S + penalty for not using the edge (h, k)
b) When calculating the cost for the set S w, we take into account that once the edge (h, k) enters the route, it means the edge (k, h) cannot enter the route, therefore in the cost matrix we write c (k, h) = infinity, and since we have already “left” from point h, and we have “already arrived” at point k, then no edge that goes from h, and not one edge that comes to k, can already be used, therefore we delete from the cost matrix, row h and column k. After that we give the matrix, and then the cost estimate for S w is equal to the sum of the cost estimates for S and r (h, k), where r (h, k) is the sum of the reduction constants for the modified cost matrix.
4. Of all unbroken sets, the one with the lowest estimate is chosen.
So we continue, until in the cost matrix there will be one row not crossed out and one column not crossed out.
Small optimization - we connect heuristics
Yes, really, why don't we introduce heuristics? Indeed, in the algorithm of branches and borders, we actually build a tree, in the nodes of which we decide to take an edge (h, k) or not, and hang two children - Sw (h, k) and Sw / o (h, k). But the best option for the next iteration is selected only by assessment. So let's choose the best not only by assessment, but also by the depth in the tree, because the deeper the selected item, the closer it is to the end of the count. Thus, we can finally wait for an answer.
The algorithm consists of two stages:
First stage
Bringing the cost matrix and calculating the lower estimate of the cost of the route r.
1. Calculate the smallest element in each row (reduction constant for a string)
2. Go to the new cost matrix, subtracting from each row its constant cast
3. Calculate the smallest element in each column (reduction constant for a column)
4. We proceed to the new cost matrix, subtracting from each column its constant of reduction.
As a result, we have a cost matrix, in which in each row and in each column there is at least one zero element.
5. We calculate the border at this stage as the sum of reduction constants for columns and rows (this border will be the cost, less than which it is impossible to build the desired route)
Second (main) stage
1. The calculation of the penalty for non-use for each zero element of the reduced cost matrix.
The penalty for not using an element with an index (h, k) in the matrix means that this edge is not included in our route, and therefore the minimum cost of “not using” this edge is equal to the sum of the minimum elements in row h and column k.
a) We are looking for all zero elements in the matrix
b) For each of them we consider his penalty for non-use.
c) Select the element to which the maximum penalty corresponds (any, if there are several)
2. Now we divide our set S into sets — containing an edge with a maximum penalty (S w ) and not containing this edge (S w / o ).
3. Calculate cost estimates for routes that are included in each of these sets.
a) For the set S w / o, everything is simple: since we do not take the corresponding edge with the maximum penalty (h, k), then for it the cost estimate is equal to the estimate of the cost of the set S + penalty for not using the edge (h, k)
b) When calculating the cost for the set S w, we take into account that once the edge (h, k) enters the route, it means the edge (k, h) cannot enter the route, therefore in the cost matrix we write c (k, h) = infinity, and since we have already “left” from point h, and we have “already arrived” at point k, then no edge that goes from h, and not one edge that comes to k, can already be used, therefore we delete from the cost matrix, row h and column k. After that we give the matrix, and then the cost estimate for S w is equal to the sum of the cost estimates for S and r (h, k), where r (h, k) is the sum of the reduction constants for the modified cost matrix.
4. Of all unbroken sets, the one with the lowest estimate is chosen.
So we continue, until in the cost matrix there will be one row not crossed out and one column not crossed out.
Small optimization - we connect heuristics
Yes, really, why don't we introduce heuristics? Indeed, in the algorithm of branches and borders, we actually build a tree, in the nodes of which we decide to take an edge (h, k) or not, and hang two children - Sw (h, k) and Sw / o (h, k). But the best option for the next iteration is selected only by assessment. So let's choose the best not only by assessment, but also by the depth in the tree, because the deeper the selected item, the closer it is to the end of the count. Thus, we can finally wait for an answer.
Now, actually, about errors in that publication
There was only one mistake - one should choose a set with a minimum boundary for splitting from all possible paths, and not from two obtained as a result of the last splitting of children.
Evidence
Let's return to the picture at the beginning of the post:
But the solution with the corrected algorithm:
The answer is: the path: 3 => 4 => 2 => 1 => 5 => 3 length: 41
As you can see, including the edge 5: 2 in the decision will be a mistake. Q.E.D
Graph comparing the method of branches and borders and time spent for a random table from 5x5 to 10x10:
The graph of the maximum and minimum time spent for matrices from 5x5 to 66x66.
You can try with a detailed solution here .
Measurement data were obtained from 100 random matrices. not a good number, but a general idea.
Sources on GitHub (updated).
Source: https://habr.com/ru/post/246437/
All Articles