I understand how the Branch and Bound Algorithm works to solve the Traveling Salesman Problem but I am having trouble trying to understand how the algorithm is faster than brute-force. The way I see it you will go through all the paths in the end. Can someone show an example where the B&B algorithm is faster than brute-forcing all the paths?
1 Answers
Let's say we have the following euclidean TSP instance:
0 7
1 6
2 5
3 4
Each number is a vertex, and the segments between all nodes are the edges (not drawn).
A brute-force approach would check all the 8! = 40320 possible paths.
A branch-and-bound algorithm, on the other hand, may start with the path 0→1→2→3→4→5→6→7, which happens to be optimal, and filter out all other paths that start by alternating between the nodes on the left and the nodes on the right more than once. For example when it considers the partial path 0→4→1 it would see that the length of that prefix already exceeds the length of the shortest path found so far, therefore there's no need to descend and check each of the paths starting with 0→4→1 individually. That prefix alone filters out 5! = 120 individual paths, but there are 96 alternating prefixes like that, which cumulatively filters out 11520 of potential solutions, or 29% of the solution space.
Related