Finding Optimal Solutions

Brute Force

By P. H. Winston

Heuristic Refinement

• A Best First approach to solving problems.
• Given a set of candidates, a search algorithm has to choose from.
• Each candidate is tagged with an estimated cost of the complete solution.

Branch and Bound in a refinement space

• The initial solution set contains all solutions.
• In each step, we partition a set into two smaller sets.
• Until we can pick a solution that is fully specified.
• Each solution set needs to have an estimated cost.
• B&B will refine the solution that has the least estimated cost.
• The process will continue until
  • we have a complete solution at hand, and
  • when no other candidate solution has a better-estimated cost.

<aside> 💡 An optimal solution can be guaranteed by ensuring that the estimated cost is a lower bound than the actual cost.

</aside>

Higher the estimate the better