Branch and Bound

Backtracking is for search problems whereas this is for optimization problems.
Instead of testing subproblems for failure, we discard a subproblem when we are sure it leads to solutions with a higher cost than our best known solution.

Start with a problem P₀
Let S = {P₀} be the set of active subproblems
bestsofar = inf
 
while S is non-empty:
    choose a subproblem P ∈ S and remove it from S
    expand it into larger subproblems P₁, P₂, ..., Pₖ
 
    for each Pᵢ:
        if test(Pᵢ) is a complete solution with cost < bestsofar:
            update bestsofar
        else if lowerbound(Pᵢ) < bestsofar:
            add Pᵢ to S
 
return bestsofar

Here, we still use the choose, expand, test, framework except we can do something in lowerbound which is a quick lower bound on the cost of any solution that includes $P_i$.

The algorithm operates as follows:

1. Pick a start vertex a
2. Subproblem $P_0$ is $[a,\{a\},a]$
3. First branch creates $|V|-1$ subproblems $[a,\{a,x_1\},x_1],[a,\{a,x_2\},x_2],\dots ,[a,\{a,x_n\},x_n]$
4. Compute the lowerbound for each subproblem and add to S
5. Choose one of the new subproblems with the smallest lowerbound to expand next
6. Once you complete a tour, update bestsofar and drop subproblems whose lowerbound is < bestsofar For graphs, we use the Minimum Spanning Tree to quickly find a lowerbound of a Traveling Salesman Problem of a graph, since the TSP is inherently a spanning tree of the graph.