Advantage of Using backtracking and branch and bound

Question

I understand that DP gives a better performance for many NP complete problems like TSP. Though the space needed is large, it reduces the complexity well.

But I couldn't understand the efficiency of branch and bound and backtracking as compared to an brute force search.

In worst case whether brute force equals b&b or backtracking ?

Answer 1

With exhaustive search, you would compute all N! possible routes between the nodes. With backtracking, you might compute a route visiting half the nodes, notice that it is already more expensive than the best route found so far, and stop investigating that partial route at that point. By doing so, you have skipped computing all of the routes that are produced by completing that partial route, thus saving time over exhaustive search, which would have continued to check them all.