算法设计-5.ppt

《算法设计-5.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、0-1背包问题(0-1KnapsackProblem)设有n个物体和一个背包,物体i的重量为wi价值为pi背包的载荷为M,若将物体i(1in,)装入背包,则有价值为pi.目标是找到一个方案,使得能放入背包的物体总价值最高算法设计与分析>回溯法若取W=(20,15,15),P=(40,25,25),C=30例题有限离散问题总可以用穷举法求得问题的全部.例如取N=3,问题所有可能的解为(解空间):(0,0,0),(0,0,1),(0,1,0),(0,1,1),(1,0,0),(1,0,1),(1,1,0),(1,1

2、,1)可表示为一棵3层的完全正则二叉树时间复杂性:O(2n)求解过程相当于在树中搜索满足条件的叶结点.第五章.回溯法(Backtraiking)算法设计与分析>回溯法学习要点:理解回溯法的深度优先搜索策略。掌握用回溯法解题的算法框架（1）递归回溯最优子结构性质（2）迭代回溯贪心选择性质（3）子集树算法框架（4）排列树算法框架第五章.回溯法(Backtraiking)算法设计与分析>回溯法通过应用范例学习回溯法的设计策略:（1）装载问题；（2）批处理作业调度；（3）符号三角形问题（4）n后问题；（5）0-1背包问题；

3、（6）最大团问题；（7）图的m着色问题（8）旅行售货员问题（9）圆排列问题（10）电路板排列问题（11）连续邮资问题第五章.回溯法(Backtraiking)设问题的解可表示为n元组(x1,x2,…xn),xisi,si为有限集,n元组的子组(x1,x2,…xi)i

4、xi-1),添加尚未考虑过的xi,如此反复进行,直到(x1,x2,…xk)kn满足所有的约束条件或证明无解.5.1基本思想算法设计与分析>回溯法E={(x1,x2,…xn),xisi,si为有限集}称为问题的解空间.约束条件隐约束:元组的分量间满足函数关系f(x1,...xn)显约束:每个xi的范围都给定的约束.满足显约束的全体向量构成解空间.显示约束条件是限定每个x只从一个给定的集合上取值。显式约束条件常见的例子是：Xi=0或Xi=1即Si=｛0，1｝子集树li≤xi≤ui即Si={a：li≤a≤ui}排列树

5、这些显式约束条件可以与所求解的问题的实例I有关，也可以无关。满足显式约束的所有元组确定I的一个可能的解空间。隐式约束条件则规定I的解空间中那些实际上满足规范函数的元组。因此，隐式约束描述了xi必须彼此相关的情况。示例：8皇后问题可以表示成8-元组（x1，…，x8），其中xi是放置皇后i所在的列号。使用这种表示的显式约束条件是Si=｛1，2，3，4，5，6，7，8｝，1≤i≤8。于是，解空间由88个8-元组所组成。这个问题的隐式约束条件是，没有两个xi可以相同（即，所有皇后都必须在不同的列上）而且没有两个皇后可以在同

6、一条斜角线上。例题算法设计与分析>回溯法1.子集树:当解向量为不定长n元组时,树中从根至每一结点的路径集合构成解空间.树的每个结点称为一个解状态,有儿子的结点称为可扩展结点,叶结点称为终止结点,若结点v对应解状态(x1,x2,…xi),则其儿子对应扩展的解状态(x1,x2,…xi,xi+1).满足所有约束条件的解状态结点称为回答结点.2.排序树:当解向量为定长n元组时,树中从根至叶结点的路径的集合构成解空间.树的每个叶结点称为一个解状态.解空间树构造:搜索按深度优先策略从根开始,当搜索到任一结点时,判断该点是否满足

7、约束条件D(剪枝函数),满足则继续向下深度优先搜索,否则跳过该结点以下的子树(剪枝),向上逐级回溯.搜索过程:求解过程可表示为在一棵解空间树作深度优先搜索.0-1背包问题(0-1KnapsackProblem)例题n=3,C=30,w={16,15,15},v={45,25,25}开始时，Cr=C=30，V=0，A为唯一活结点，也是当前扩展结点扩展A，先到达B结点Cr=Cr-w1=14，V=V+v1=45此时A、B为活结点，B成为当前扩展结点扩展B，先到达DCr

8、1背包问题(0-1KnapsackProblem)例题n=3,C=30,w={16,15,15},v={45,25,25}扩展A，先到达B结点再扩展B到达EE可行，此时A、B、E是活结点，E成为新的扩展结点扩展E，先到达JCr