资源描述：
《算法设计与分析第08章》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、算法设计与分析DeSignandAnalysisofAlgorithmsInC++“十一五”国家级规划教材陈慧南编著电子工业出版社第2部分算法设计策略第8章回溯法8.1一般方法8.2n-皇后8.3子集和数8.4图的着色8.5哈密顿环8.60/1背包8.7批处理作业调度最优化问题：满足一定的约束条件解称为可行解。使目标函数最优的（最大或最小）可行解称为最优解。问题的解向量：表示成一个n元式(x0,x1,…,xn-1)的形式贪心算法：最优子结构特性和最优量度标准动态规划法：最优子结构特性和重叠子问题8.1一般方法回溯法的基本做法是搜索，或是一种组织得井井有条
2、的，能避免不必要搜索的穷举式搜索法。这种方法适用于解一些组合数相当大的问题。回溯法的基本思想一般的搜索算法（暴力算法），对所有可能的解逐一的试验，看是否是问题的解。任何问题都可以用暴力搜索算法解决，因为它遍历了全部可能解，但是显然会很慢。搜索过程，要保证每个可能情况都要试到，不漏不重，所以就有了各种各样的搜索算法，比如深度优先搜索，广度优先搜索。他们的区别只在于构造可能解的方式不同，本质是一样的，都是试解，回溯算法是一种采用深度优先方式来构造可能解的搜索算法。n=3时的0-1背包问题用完全二叉树表示的解空间M=30（w0,w1,w2）=(18,15,10
3、)，（p0,p1,p2）=(25,24,15)。搜索算法如果不做任何优化那么执行效率是一样的。因为一定要搜索全部可能解。但是如果我们在搜索过程（可能解的构造）中已经和问题不符合，我们就没必要继续构造下去，这就是所谓搜索算法里面的剪枝，不同的搜索算法就是为了尽可能地舍弃那些不可能的解，来达到提高搜索算法效率的目的。n=3时的0-1背包问题用完全二叉树表示的解空间M=30（w0,w1,w2）=(18,15,10)，（p0,p1,p2）=(25,24,15)。回溯法在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树。算法搜索至解空间树的任意一点时，先
4、判断该结点是否包含问题的解。如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先策略搜索。n=3时的0-1背包问题用完全二叉树表示的解空间8.1.1基本概念问题的解向量：回溯法希望一个问题的解能够表示成一个n元式(x0,x1,…,xn-1)的形式。规定每个xi取值的约束条件称为显式约束。对给定的一个问题实例，显式约束规定了所有可能的元组，它们组成问题的候选解集，被称为该问题实例的解空间。隐式约束给出了判定一个候选解是否为可行解的条件。目标函数也称代价函数，用来衡量每个可行解的优劣。使目标函数取最大（或最小
5、）值的可行解为问题的最优解。状态空间树（statespace）是描述问题解空间的树形结构。树中每个结点称为一个问题状态（problemstate）。如果从根到树中某个状态的路径代表一个作为候选解的元组，则称该状态为解状态（solutionstate）。如果从根到某个解状态的路径代表一个作为可行解的元组，则称该解状态为答案状态(answerstate)。M=30（w0,w1,w2）=(18,15,10)，（p0,p1,p2）=(25,24,15)。8.1.2剪枝函数和回溯法为了提高搜索效率，在搜索过程中使用约束函数（constraintfunction），
6、可以避免无谓地搜索那些已知不含答案状态的子树。如果是最优化问题，还可使用限界函数（boundfunction）剪去那些不可能包含最优答案结点的子树。约束函数和限界函数的目的是相同的，都为了剪去不必要搜索的子树，减少问题求解所需实际生成的状态结点数，它们统称为剪枝函数（pruningfunction）。使用剪枝函数的深度优先生成状态空间树中结点的求解方法称为回溯法（backtracking）；广度优先生成结点，并使用剪枝函数的方法称为分枝限界法（branch-and-bound）。剪枝函数：约束函数在扩展结点处剪去不满足约束的子树；限界函数剪去得不到最优解
7、的子树。对n个元素（a0,a1,…,an-1)排序，本质是求元素下标（0，1,…,n-1)的一种排列X(x0,x1,…,xn-1)，使得axi≤axi+1例如：n=3,（a0,a1,a2)=(13,24,9)设(x0,x1,…,xk-1)是从根到某个问题状态Y的一条路径，令T(x0,x1,…,xk-1)是xk可取值的集合，对于xk的每个取值(x0,x1,…,xk-1，xk)，是一条从根到Y再到Y的某个孩子Z的路径。如果约束函数Bk(x0,x1,…,xk)为真，则继续检测以Z为根的子树，否则将不再考虑以Z为根的子树。如果(x0,x1,…,xk-1)到达叶子
8、结点，T(x0,x1,…,xk-1)应为空集。【程序8－1】递归回溯法VoidR
