Inaccuracy of branch and bound algorithm
Abstract
Inaccuracy of branch and bound algorithm
Incoming article date: 10.05.2018The aim of the work is to verify the accuracy of the solution of the traveling salesman problem by the method of branches and boundaries with a large difference in the length of the chords of the transport graph. It is considered an NP-hard task. It is proved that the Vig method can not give an optimal result in a transport graph with a large difference in the values of the elements in the cells of the original matrix, when its zero cells will have very different estimates. The reason for the inaccuracy of solving the travelling salesman problem is the inadequacy of the adopted model for the calculation of the original formulation of the problem. It consists in the injustice of the second hypothesis on the evaluation of the zero element in the evaluation matrix included in the optimal route. The hypothesis is accepted without strict proofs and has probabilistic character. The use of the minimum values of the row and column from the matrix is appropriate, as determined by the route of the smallest length. It is doubtful whether it is true that there is always a need to strike out at each stage the zero element with the maximum total score. The reason is that, firstly, it has a random character in General. Secondly, this assessment does not take into account all possible combinations of combinations of branches giving the optimal combination, since their recursion is not carried out. The technique of improving the method of branches and boundaries is proposed, which consists in additional verification of the obtained optimal route by removing the branch with an estimate one step below the maximum at each stage of branching. Numerical experiment is carried out.
Keywords: salesman, best route, branch and bound method, gaps, hypotheses, algorithm, the inaccuracy of the decision, the reason why numerical experiment, improvement method