算法设计与分析课件_Algotiyhmsch05-回溯法 .ppt

《算法设计与分析课件_Algotiyhmsch05-回溯法 .ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第5章回溯法计算机算法设计与分析内容提要每一步都非常关键，走好每一步！1理解深度优先搜索策略2掌握回溯法的算法策略3学习应用范例归纳总结理解回溯法的深度优先搜索策略通用算法、万能算法？1它在问题的解空间树中，按深度优先策略，从根节点出发搜索解空间树。算法搜索至解空间树的任一结点时，先判断该节点是否包含问题的解。如果肯定不包含，则跳过对以该结点为根的子树的搜索，逐层向其祖先节点回溯；否则，进入该子树，继续按深度优先策略搜索回溯法—“通用解题法”—“万能算法”。回溯法可以系统的搜索一个问题的所有解或任一解。回溯法是一个即带有系统性又带有跳跃性的搜索算法。回溯

2、法回溯法生成问题状态的基本方法扩展结点:一个正在产生孩子的结点称为扩展结点活结点:一个自身已生成但其孩子还没有全部生成的节点称做活结点死结点:一个所有孩子已经产生的结点称做死结点深度优先的问题状态生成法：如果对一个扩展结点R，一旦产生了它的一个孩子C，就把C当做新的扩展结点。在完成对子树C（以C为根的子树）的穷尽搜索之后，将R重新变成扩展结点，继续生成R的下一个孩子（如果存在）宽度优先的问题状态生成法：在一个扩展结点变成死结点之前，它一直是扩展结点回溯法：为了避免生成那些不可能产生最佳解的问题状态，要不断地利用限界函数(boundingfunction)

3、来处死那些实际上不可能产生所需解的活结点，以减少问题的计算量。具有限界函数的深度优先生成法称为回溯法问题的解空间回溯法的基本思想递归回溯迭代回溯子集树与排列树5.1回溯法的算法框架1问题的解空间5.1回溯算法的基本框架问题的解空间问题的解空间举例回溯法的解空间为了用回溯法求解一个具有n个输入的问题，一般情况下，将其可能的解表示为满足某个约束条件的等长向量X=（x1,x2,…,xn)，其中分量xi（1<=i<=n)的取值范围是某个有限集合Si={ai1,ai2,…,ain},所以有可能的解向量构成了问题的解空间。回溯法的解空间回溯法的解空间的组织回溯法的解

4、空间—0/1背包回溯法的解空间—旅行售货员问题2回溯法的基本思想5.1回溯算法的基本框架回溯法的基本思想回溯法的基本思想距离—0/1背包旅行售货员问题某个售货员要到若干城市去推销商品，已知各城市之间的路程（或旅费）。他要选定一条从驻地城市出发，经过每个城市一遍，最后回到驻地的路线，使总的路程（或总旅费）最小。回溯法的基本思想回溯法的解题基本步骤(1)针对所给问题，定义问题的解空间；(2)确定易于搜索的解空间结构；(3)以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。用回溯法解题的一个显著特征是在搜索过程中动态产生问题的解空间。在任何时刻，

5、算法只保存从根结点到当前扩展结点的路径。如果解空间树中从根结点到叶结点的最长路径的长度为h(n)，则回溯法所需的计算空间通常为O(h(n))。而显式地存储整个解空间则需要O(2h(n))或O(h(n)!)内存空间。22回溯法的求解过程回溯法的求解过程3递归回溯5.1回溯算法的基本框架递归回溯4迭代回溯5.1回溯算法的基本框架迭代回溯5子集树与排列树5.1回溯算法的基本框架子集树：当所给的问题是从n个元素的集合S中找出满足某种性质的子集时，相应的解空间称为子集树。排列树：当所给的问题是确定n个元素满足某种性质的排列时，相应的解空间树成为排列树。回溯法：子集

6、树和排列树子集树与排列树遍历子集树需O(2n)计算时间遍历排列树需要O(n!)计算时间voidbacktrack(intt){if(t>n)output(x);elsefor(inti=0;i<=1;i++){x[t]=i;if(legal(t))backtrack(t+1);}}voidbacktrack(intt){if(t>n)output(x);elsefor(inti=t;i<=n;i++){swap(x[t],x[i]);if(legal(t))backtrack(t+1);swap(x[t],x[i]);}}2回溯法的应用例子装载问题、作业

7、调度和0/1背包问题装载问题有一批共n个集装箱要装上2艘载重量分别为c1和c2的轮船，其中集装箱i的重量为wi，且装载问题要求确定：是否有一个合理的装载方案可将这n个集装箱装上这2艘轮船。如果有，找出一种装载方案。33n=3，c1=c2=50w1=[10,40,40]，w2=[20,40,40]，装载例子有一批共n个集装箱要装上2艘载重量分别为c1和c2的轮船，其中集装箱i的重量为wi，且容易证明，如果一个给定装载问题有解，则采用下面的策略可得到最优装载方案。(1)首先将第一艘轮船尽可能装满；(2)将剩余的集装箱装上第二艘轮船。将第一艘轮船尽可能装满等价

8、于选取全体集装箱的一个子集，使该子集中集装箱重量之和最接近。由此可知，装载问题等