算法8_回溯法教学提纲.ppt

《算法8_回溯法教学提纲.ppt》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、第8章回溯法学习要点：理解回溯法的深度优先搜索策略理解剪枝函数（约束函数和限界函数）的作用掌握回溯法解题的算法框架（1）递归回溯的算法框架（2）迭代回溯的算法框架（3）蒙特卡罗方法进行效率分析通过应用范例学习回溯法的设计策略。（1）n-皇后问题（2）子集和数问题（3）图的着色（4）哈密顿环（5）0/1背包章节内容：8.1一般方法8.2n-皇后8.3子集和数8.4图的着色8.5哈密顿环8.60/1背包8.1回溯法的一般方法回溯法是比贪心法和动态规划法更一般的方法。解为n-元组(x0,x1,...,xn-1)形式。通过搜索状态

2、空间树来求问题的可行解（满足约束条件）或最优解（使目标函数取最大或最小值）。使用约束函数和限界函数来压缩需要实际生成的状态空间树的结点数。通常情况下，回溯法是为了找出满足约束条件的所有可行解。问题的解空间回溯法要求问题的解向量具有n-元组(x0,x1,…,xn-1)的形式，每个解分量xi从一个给定的集合Si取值。显式约束：规定每个xi取值的约束条件。（显式约束规定了问题的候选解集——解空间）对于问题的一个实例，解向量满足显式约束条件的所有多元组，构成了该实例的一个解空间。通常情况下,回溯法的求解目标是在状态空间树上找出满足

3、约束条件的所有可行解.隐式约束：给出了判定一个候选解是否为可行解的条件。为满足问题的解而对不同分量之间施加的约束。目标函数（代价函数）：衡量每个可行解的优劣，使目标函数取最大（或最小）值的可行解为问题的最优解。例如（例8-1）：对n个元素(a0,a1,……,an-1)进行排序，求元素下标(0,1,……n-1)的一种排列X=(x0,x1,……,xn-1)。使(0≤i

4、方法：显式约束：xiSi，Si={0,1,......,n-1}且xi≠xj(i≠j)。此时解空间大小为n!。隐式约束：(0≤i

5、0-1背包问题。若n=3则状态空间树为一个完全二叉树：有2n个解状态10110101236457011110109101381214015当所给的问题是从n个元素的集合中找出满足某种性质的子集时，相应的状态空间树为子集树，通常有2n个叶节点。状态空间树状态空间树：描述问题解空间的树形结构。树中每个结点称为一个问题状态；若从根到树中某个状态的路径代表一个候选解元组，则该状态为解状态；若从根到某个解状态的路径代表一个可行解元组，则该解状态为答案状态；如果求解的是最优化问题，还要用目标函数衡量每个答案结点，找出其中目标函数取最优

6、值的最优答案结点。穷举法的一般方法使用深度优先或广度优先搜索方法，检查状态空间树中每个问题状态；如果是解状态则用判定函数判定它是否是答案结点；对于最优化问题，搜索过程中还需对每个答案结点计算其目标函数值，记录下其中最优者。——这种遍历状态空间树的求解方法是问题求解的穷举法。回溯法与穷举搜索不同：回溯法使用约束函数，剪去那些可以断定不含答案状态的子树，从而提高算法效率。回溯法适用于解一些组合数相当大的问题。事实上，状态空间树并不需要事先生成，而只需在求解的过程中，随着搜索算法的进展，逐个生成状态空间树的问题状态结点。回溯法的

7、一般方法采用深度优先产生状态空间树的结点，并使用剪枝函数的方法称为——回溯法。回溯法：在求解的过程中，以深度优先方式逐个生成状态空间树中结点，求问题的可行解或最优解。为提高搜索效率，在搜索过程中用约束函数和限界函数（统称剪枝函数）来剪去不必要搜索的子树，减少问题求解所需实际生成的状态空间树结点数，从而避免无效搜索。常用的剪枝函数：用约束函数剪去已知不含答案状态（可行解）的子树；用限界函数剪去得不到最优答案结点（最优解）的子树。在搜索过程中动态产生问题的解空间。算法搜索至任一结点时，先判断以该结点为根的子树是否包含问题的解。

8、如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先策略搜索。递归回溯回溯法对解空间作深度优先搜索，因此，在一般情况下用递归方法实现回溯法。程序8-1递归回溯算法框架voidRBacktrack(intk){for(每个x[k],使得x[k]T(x[0