算法设计与分析课件第5章 节 回溯法.ppt

第5章 回溯法;学习要点 理解回溯法的深度优先搜索策略。 掌握用回溯法解题的算法框架 （1）递归回溯 （2）迭代回溯 （3）子集树算法框架 （4）排列树算法框架 ;通过应用范例学习回溯法的设计策略。 （1）装载问题； （2）批处理作业调度； （3）符号三角形问题 （4）n后问题； （5）0-1背包问题； （6）旅行售货员问题 ;有许多问题，当需要找出它的解集或者要求回答什么解是满足某些约束条件的最佳解时，往往要使用回溯法。 回溯法的基本做法是搜索，或是一种组织得井井有条的，能避免不必要搜索的穷举式搜索法。;回溯法的直观印象;回溯法：任务描述;回溯法：任务描述;剪枝函数和回溯法 ;使用剪枝函数的深度优先生成状态空间树中结点的求解方法称为回溯法（backtracking）； 广度优先生成结点，并使用剪枝函数的方法称为分支限界法（branch-and-bound）。 ;问题的解空间;问题的解空间;生成问题状态的基本方法;生成问题状态的基本方法;生成问题状态的基本方法;有限离散问题总可以用穷举法求得问题的全部解.;设问题解可表为n元组(x1, x2,… xn), xi?si , si为有限集, n元组的子组(x1, x2,… xi) , in ,满足一定约束条件D. 设已有满足D的部分解(x1, x2,… xi), 添加xi+1 ?si+1,若(x1, x2,… xi ,xi+1 )满足D, 则继续添加xi+2 ; 若所有可能的xi+1 ?si+1均不满足D,去掉xi , 回溯到(x1, x2,… xi-1), 添加未考虑过的xi , 反复进行,直到(x1, .., xk) , k?n ,满足所有约束或证明无解. ;问题的解空间：E={ (x1, x2,… xn), xi ?si , si为有限集 };1.子集树:当解向量为不定长n元组时 , 树中从根至每一点的路径集合构成解空间.树的每个结点称为一个解状态,有儿子的结点称为可扩展结点,叶结点称为终止结点, 若结点v对应解状态(x1, x2,… xi),则其儿子对应扩展的解状态(x1, x2,… xi, xi+1 ). 2.排列树:当解向量为定长n元组时, 树中从根至叶结点的路径的集合构成解空间.树的每个叶结点称为一个解状态.;搜索按深度优先策略从根开始, 当搜索到任一结点时,判断该点是否满足约束条件D(剪枝函数),满足则继续向下深度优先搜索,否则跳过该结点以下的子树(剪枝), 向上逐级回溯.;回溯法的复杂性;回溯法的解题步骤;递归回溯;迭代回溯;???集树与排列树;例1 0-1背包问题;例1 0-1背包问题;例1 0-1背包问题;例1 0-1背包问题;例2 旅行售货员问题;装载问题;装载问题;装载问题;装载问题;用排序树表示解空间,则解为n元向量{x1, ... ,xn }, xi?{0, 1} ;cw + r ≤ bestw;例如 n=4, c1=12, w=[8, 6, 2, 3]. bestw初值=0;;template class Type Type Maxloading(type w[], type c, int n,) //返回最优装载量 { loading Type X； //初始化X X. w=w; //集装箱重量数组 X. c=c; //第一艘船载重量 X. n=n；//集装箱数 X. bestw=0; //当前最优载重 X. cw=0;//当前载重量 X. r=0; //剩余集装箱重量 for (int i=1; i=n; i++) X. r +=w[i] //计算最优载重量 X.backtrack(1)； return X.bestw； };装载问题;装载问题的运行实例;批处理作业调度;批处理作业调度;批处理作业调度;批处理作业调度;批处理作业调度;批处理作业调度的运行实例;+ + - + - + + + - - - - + - + + + - - + + - - + - - - +;在一般情况下，符号三角形的第一行有n个符号。符号三角形问题要求对于给定的n，计算有多少个不同的符号三角形，使其所含的“+”和“-”的个数相同。;void Triangle::Backtrack(int t) { if ((counthalf)||(t*(t-1)/2-counthalf)) return; if (tn) sum++; else for (