计算机算法第5教学提纲.ppt

计算机算法第5;有许多问题当需要找出它的解集或者要求回答什么解是满足某些约束条件的最佳解时往往要使用回溯法 回溯法的基本做法是搜索或是一种组织得井井有条的能避免不必要搜索的穷举式搜索法这种方法适用于解一些组合数相当大的问题 回溯法在问题的解空间树中按深度优先策略从根结点出发搜索解空间树算法搜索至解空间树的任意一点时先判断该结点是否包含问题的解如果肯定不包含则跳过对该结点为根的子树的搜索逐层向其祖先