回溯法教案范文

回溯法教案范文 回溯法 一、学习目的和要求通过本章的学习，要求学生了解回溯法的基本思想，掌握回溯算法的设计步骤，并学会使用回溯算法分析和解决实际的问题，并对算法进行复杂性分析。 二、课程内容1回溯算法的基本框架和基本要素2使用回溯算法分析和解决具体问题 （1）最优装载问题 （2）批处理作业调度 （3）N皇后问题 （4）0-1背包问题 （5）图的M着色问题 （6）旅行售货员问题3回溯算法的效率分析 三、考核知识点1回溯算法的基本框架和基本要素2使用回溯算法分析和解决具体问题（最优装载问题、N皇后问题、0-1背包问题、图的M着色问题）3回溯算法的效率分析 四、考核要求1）识记回溯算法的基本概念2）领会回溯算法的基本框架和基本要素3）应用运用回溯算法解决具体问题 五、详细内容5.1回溯法的算法框架1问题的解空间n=3时，0-1背包问题的解空间可用一颗状态树表示2回溯法的基本思想问题状态树中的每一个结点确定所求解问题的一个问题状态。 代表问题状态的结点称为问题结点。 状态空间由根结点到其它结点的所有路径确定了这个问题的状态空间。 解状态是这样的一些问题状态S，对于这些问题状态，由根到S的那条路径确定了解空间的一个元组。 其对应的结点称为解结点。 答案状态是这样的一些问题状态S，对于这些问题状态，由根到S的那条路径确定了这问题的一个解（即它满足隐式约束条件）状态空间树的每个问题结点对应一个子解空间，同时也代表已经作出的一些选择。 状态空间树是在算法执行中产生的。 为此定义以下术语。 1活结点已生成一个以上子节点，但所有子结点尚未全部生成的结点。 死结点不在进一步扩展或已产生了所有子结点的结点。 E-结点当前正在生成子结点的结点。 深度优先生成方法一个E-结点展开一个子结点后，就让该子结点成为E-结点的状态生成方法（相当于对状态空间树做深度优先搜索），称为深度优先生成方法。 回溯法加限界的深度优先生成方法称为回溯法。 分枝限界法如果一个结点成为E-结点并保持为E-结点直到变成死结点为止，这样的状态生成方法称为分枝限界法。 在分枝限界法中要维持一个活结点表的结构，存放已生成但还未变为E结点的那些结点。 设(x1,x2,xi1)是状态空间树中由根到一问题结点A的路径；T(x1,x2,xi1)给出状态空间树上xi所有可能的取值，即(x1,x2,xi)是状态空间树上到A的子节点的一条路径。 所谓限界函数Bi是一谓词，如果路径(x1,x2,xi)不可能延伸到一个答案结点，则Bi(x1,x2,xi)取false。 限界即指停止产生该结点及以它为根的子树。 例如0/1背包问题考察如下背包问题n=3，w=20,15,15，p=40,25,25且c=30。 背包问题的状态空间树旅行商问题在这个问题中，给出一个n顶点网络（有向或无向），要求找出一个包含所有n个顶点的具有最小耗费的环路。 任何一个包含网络中所有n个顶点的环路被称作一个旅行（tour）。 在旅行商问题中，要设法找到一条最小耗费的旅行。 在用回溯法搜索解空间树时，通常采用两种策略来避免无效搜索，提高回溯法的搜索效率，2其一是用约束函数在扩展结点处剪去不满足约束的子树；其二，是用限界函数剪去不能得到最优解的子树。 这两类函数统称为剪枝函数。 运用回溯法解题通常包含以下三个步骤1）针对所给问题，定义问题的解空间2）确定易于搜索的解空间3）以深度优先的方式搜索解空间，并且在搜索过程中用剪枝函数避免无效搜索。 3递归回溯void backtrack(int t)if(tn)output(x);else for(int i=f(n,t);i0)if(f(n,t)=g(n,t)for(int i=f(n,t);i=g(n,t);i+)xt=h(i);if(constraint(t)&bound(t)if(solution(t)outp