Which of the following statements is true for Branch-and-Bound search ?
2015
Which of the following statements is true for Branch-and-Bound search ?
- A.
Underestimates of remaining distance may cause deviation from optimal path
- B.
Overestimates can't cause right path to be overlooked
- C.
Dynamic programming principle can be used to discard redundant partial paths
- D.
All of the above
Attempted by 83 students.
Show answer & explanation
Correct answer: C
Answer: Dynamic programming principle can be used to discard redundant partial paths
Explanation:
Underestimates of remaining distance: Lower-bound estimates are optimistic. They may change the order of node expansion and increase the number of nodes explored, but a correct lower bound does not cause the optimal solution to be discarded.
Overestimates: If a bound overestimates the remaining cost, it can lead to pruning or ignoring partial paths that actually lead to the optimal solution, so overestimates can cause the correct path to be overlooked.
Dynamic programming principle: When two partial paths reach the same state, keeping the one with lower cost and discarding the worse one is a safe dominance rule. This removes redundant partial paths without losing optimality.
Conclusion: Only the statement about using the dynamic programming principle to discard redundant partial paths is correct; the other statements are incorrect or misleading.
A video solution is available for this question — log in and enroll to watch it.