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
- backtracking — A search technique that builds a solution one choice at a time and undoes the latest choice as soon as it cannot lead to a valid solution.
- constraint propagation — Using one decision to rule out other options immediately, so a single choice narrows the rest of the search.
- exhaustive search — Trying every possible candidate solution and checking each one.
Taught in
- Divide And Conquer And The Recurrence — Algorithms & Data Structures for Working Engineers
- Backtracking: Search With Pruning — Algorithms & Data Structures for Working Engineers
- Recognising The Pattern — Algorithms & Data Structures for Working Engineers