Search

Solution of the traveling salesman task online and free

Instructions for using the branch and bound
Select the dimension of the matrix (the number of cities), click Next. The resulting solution is stored in the file MS Word.

Select the number of cities

Solve the traveling salesman problem by branch and bound.

Branch and bound Method

In the traveling salesman problem for the formation of the optimal route detour n Cities must select one of the best (n-1)! variants on the criterion of time, cost and length of the route. This challenge relates to the definition of a Hamiltonian cycle of minimum length. In such cases, the set of all possible solutions should be represented as a tree - a connected graph containing no cycles and loops. The root of the tree unites many options, and the top of the tree - are subsets of partially ordered solutions.
Vertex (i, j) corresponds to a subset of all routes containing the edge (i, j), and the vertex (i*, j*) - a subset of all routes, where the edge is absent.
Process of decomposition of these subsets can be considered as a branching tree. Therefore, the method called search method for decision tree , or method branch and bound .
Branch and bound method is an algorithm directed inspection of the set of options for solving the problem. essence of the method of branches and borders is that from the root of the tree branches are not all vertices.

Add to favorites