4
$\begingroup$

I've been studying Branch and Bound's graph algorithm and I hear it always finds the optimal path because it uses previously found solutions to find others

However, I haven't been able to find a proof of why it finds the optimal path. (In fact, most sites kind of do a bad job generalizing the algorithm itself.)

What is the proof that this algorithm always finds the optimal path in the case of a graph with 1 or more goal nodes?

| improve this question | | | | |
$\endgroup$
  • $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$ – nbro 14 hours ago
0
$\begingroup$

Branch and Bound is similar to an exhaustive search, except it incorporates a method for computing lower bounds on branches. If the lower bound on a given branch is greater than the upper bound on the problem (i.e. the current best solution encountered), that branch can be discarded since it will never produce an optimal solution.

Hence, since you explore all options except those you know will produce values less optimal than your current best value, you are guaranteed to encounter the global optimum.

Note this is a generic algorithm, and you will need to reference a specific implementation if you want proof of why it satisfies these criteria.

| improve this answer | | | | |
$\endgroup$
-1
$\begingroup$

My attempt was proof by contradiction. We can assume B&B found a sub-optimal path, but that would create a contradiction, because the only way B&B would miss an optimal path is if it skipped it completely (this part I don't know how to prove) or the related part of the search space was pruned.

| improve this answer | | | | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.