Question

Choose the correct statement from the following.

(a) branch and bound is more efficient than backtracking

(b) branch and bound is not suitable where a greedy algorithm is not applicable

(c) branch and bound divides a problem into at least 2 new restricted sub problems

(d) backtracking divides a problem into at least 2 new restricted sub problems

I have been asked this question in final exam.

My doubt stems from Graph Search in division Graph Search of Data Structures & Algorithms II

Answer 1

Correct answer is (c) branch and bound divides a problem into at least 2 new restricted sub problems

For explanation: Both backtracking as well as branch and bound are problem solving algorithms. Branch and bound is less efficient than backtracking. Branch and bound divides a problem into at least 2 new restricted sub problems.