什么是剪枝函数？有何作用？为何要在分支限界法中使用

什么是剪枝函数？有何作用？为何要在分支限界法中使用

用约束函数在扩展结点处剪去不满足约束的子树；和用限界函数剪去得不到最优解的子树。这两类函数统称为剪枝函数。
采用剪枝函数，可避免无效搜索，提高回溯法的搜索效率。
在分支限界法中使用剪枝函数，可以加速搜索。该函数给出每一个可行结点相应的子树可能获得的最大价值的上界。如果这个上界不比当前最优值更大，则说明相应的子树中不含问题的最优解，因而可以剪去。
另一方面，也可以将上界函数确定的每个结点的上界值作为优先级，以该优先级的非增序抽取当前扩展结点。这种策略有时可以更迅速地找到最优解。

用约束函数在扩展结点处剪去不满足约束的子树； 和用限界函数剪去得不到最优解的子 树。这两类函数统称为剪枝函数。
采用剪枝函数，可避免无效搜索，提高回溯法的搜索效率。 在分支限界法中使用剪枝函数， 可以加速搜索。 该函数给出每一个可行结点相应的子树
可能获得的最大价值的上界。 如果这个上界不比当前最优值更大， 则说明相应的子树中不含
问题的最优解，因而可以剪去。另一方面，也可以将上界函数确定的每个结点的上界值作为
优先级，以该优先级的非增序抽取当前扩展结点。这种策略有时可以更迅速地找到最优解。