CMP.4:1 - Problem frame

Use this when an answer must be constructed by choosing among alternatives, direct enumeration is too costly, and information about a partial choice can eliminate some of its completions. You need a search procedure that saves work while retaining the answers its recipient needs.

Examples include finding an assignment satisfying constraints, selecting a best combination, constructing a counterexample and exploring possible program states. The general difficulty is deciding which alternatives may be omitted. A promising search order can find an answer quickly while providing no reason to exclude the alternatives visited later.

The gain is a search with explicit coverage, useful exclusion rules and a result that remains interpretable if computation is interrupted. The reader needs finite sets, logical conditions and inequalities; MATH.20 supplies a more developed bound argument. C.29.2 supplies the wanted computational answer.

Use direct construction or enumeration when it already solves the problem at acceptable cost. Heuristic search is also useful when a good candidate is enough. Apply the exclusion method to the conclusions that must be retained, without requiring proof of global optimality for every candidate search.