pruning

Abandoning a branch of a search as soon as a check shows it cannot lead to a valid or better solution.

In more detail

A cut near the root removes a whole subtree of possibilities, so the earlier and stronger the check, the bigger the saving. The course counts nodes visited with and without pruning to measure the gain. Without pruning, backtracking is just exhaustive search.

Related terms

Taught in

References