State Space and Cuts

Pruning cuts off branches that can no longer reach a valid solution. Early conflict tests save exponential work.

Example: In the n-Queens problem, do not place a queen on the same diagonal before going deeper.

Where used

Pruning decides whether backtracking will end in practice. The same idea is used in branch-and-bound, SAT solvers, and query planners.

Depth

The state space contains all partial and complete configurations of a search problem. A representation is good if both the next decisions and the still vulnerable conditions can be derived efficiently from it. Different representations of the same problem can therefore create search trees of very different sizes.

A cut ends the examination of a subtree as soon as it is determined that no feasible or better solution can arise there. Feasibility cuts use hard constraints. Bounds compare the best possible result of a branch with the best complete solution found so far.

Difficulty levels

1. Distinguish the state, decision, and goal state of a problem.
2. Derive a safe feasibility cut from a constraint.
3. Justify an optimistic bound for an optimization problem.

Pitfalls

A bound must be optimistic when entire branches are pruned with it. If the achievable result is estimated too poorly, the algorithm may cut off the optimal branch.