10. How the branch and bound technique is different from backtracking? Solve the following instance of knapsack problem using Branch and Bound technique. Give knapsack capacity = 10.
Answer:
The branch and bound technique is different from backtracking in the following ways:
- Backtracking is used to find all possible solutions to a problem, while branch and bound is used to find the optimal solution to a problem.
- Backtracking incrementally builds candidates to the solutions and discards them if they do not satisfy the constraints of the problem, while branch and bound systematically enumerates candidates to the solutions and prunes them if they cannot produce a better solution than the best one found so far.
- Backtracking follows a depth-first search strategy, while branch and bound can follow either a breadth-first or a depth-first search strategy, depending on whether it uses a queue or a stack to store the candidates.
- Backtracking does not use any bounding function to guide the search, while branch and bound uses a heuristic function to estimate the upper and lower bounds on the optimal solution and select the most promising candidate for further exploration.
