Branch Pruning

This is an optimization technique often applied to limit recursion breadth when considering moves in a board game, for example. Ditch (prune) the branches of the game tree that don't look promising or interesting. This is named alpha-beta pruning when applied to a DepthFirst Minimax search.

It's a HeuristicRule.

It's not always a HeuristicRule. Ex: A simple solution to the Knapsack problem is to do a depth first search along the choice tree, keeping track of the best solution thus far. If the branch you're currently exploring is provably equal or worse to the best seen thus far, don't bother exploring the branch and try another branch, aka prune it.

I forget the official name for it, but I've needed reference to it a couple of times this week, now. -- MatthewAstley

I think that algorithm mentioned for the Knapsack problem is branch-and-bound. -- PeterWitjes?

CategoryOptimization CategoryGardeningMetaphor