《算法设计与分析课件》由会员分享，可在线阅读，更多相关《算法设计与分析课件（171页珍藏版）》请在金锄头文库上搜索。
1、算法设计与分析8/6/20241内容n计算模型和计算复杂性的测度n数据结构与递归技术n分治与平衡n排序n动态规划n贪心法n回溯法n分枝限界法8/6/20242第一章计算模型和计算复杂性的测度8/6/202431.1引言 1.算法的概念n基本上几乎所有的程序都是为了实现某种算法，简言之算法就是处理问题的步骤与逻辑，它是它是有穷规则的有序集合有穷规则的有序集合。算法分为数值算法与非数值算法。n数值算法有：概率统计计算、线性代数计算、数值逼近、数值微分、数值积分、数学规划等。n数值算法是通用的，一般可用解析式表示：而非数值算法只是思想或思路，要根据具体问题按这种思想或思路进行设计。8/6/20244
2、1.1引言2 算法的特征n(1)有穷性：算法应该是有穷规则，在有穷步骤后终止。n(2)确定性：算法的任何一步都应该有且仅有一个解释。n(3)能行性：算法应该符合问题的要求，应该在有限时间内完成。n(4)输入与输出：有零个或多个外部量作为算法的输入，算法产生至少一个量作为输出。8/6/202451.1引言n程序与算法不同，程序是算法用某种程序设计语言的具体实现。程序可以不满足算法的有限性。例如操作系统，它是在无限循环中执行的程序，因而它并不是算法。然而可以将它的各种任务看成一些单独的问题。每一个问题由操作系统的一个子程序通过特定的算法实现。该子程序在得出输出结果后便终止。 8/6/202461.
3、1引言3 算法设计与分析的步骤n(1)问题的描述：明确输入与输出。n(2)建立模型：将核心内容模型化，逻辑化。n(3)算法设计与正确性证明：对所有正确的输入都能得到正确的输出（一般需要用谓词逻辑来证明）。n(4)程序实现：用某种程序设计语言来实现。n(5)算法分析：在程序实现之前进行。8/6/202471.2计算复杂性的测度n算法的计算复杂性(computational complexity)是衡量算法计算难度的尺度，使用最普遍的标准是一个算法需要耗费算法需要耗费的时间和空间的时间和空间。算法所需要的时间或空间，通常是问题规模的函数，这个函数就叫做算法的时间或空间复杂度。在实际中用算法主操作的
4、重复次数来表示算法的时间复杂度。8/6/202481.2计算复杂性的测度n问题的规模：也就是该问题所谓的体积，或者说是大小。一个问题的体积可以用一个整数来表示，它是对问题的输入数据或初始数据的多少的一种量度。n定义：如果一个问题的体积是n，解决这一问题的某一算法所需要的时间为T(n)，它是n的某一函数，T(n)称作这一算法的“时间复杂性”。当输入量n逐渐增大时，T(n)的极限情形就称作算法的“渐近时间复杂性”，类似可定义算法的空间复杂性。但实际上人们主要是研究算法的时间复杂性而很少讨论它们的空间耗费。8/6/202491.2计算复杂性的测度n一个算法的复杂性函数的量级是反映算法效能的重要标准。
5、当输入量急剧地增大时，如果设有高效能的算法，单纯依靠提高计算机的速度，有时是很不理想的。n设有五个算法A1，A2，A3，A4，A5，它们的时间复杂性函数如下表所示：表中，一个算法的时间复杂性是它处理完一个大小为n的输入所需要的的单位时间数。 8/6/202410例例1. 39个景点的全排列 39！=2.041046 用每秒处理1亿次（108）逻辑的计算机，需耗时6.51022亿年例2. 下围棋 3361=1.7410172=5.5210146亿年例3. 电梯从1楼到10楼，有多少种可能的方式？ 8/6/202411算法时间复杂性函数A1T1(n)=nA2T2(n)=nlog2n(nlogn)A
6、3T3(n)=nA4T4(n)= nA5T5(n) =21.2计算复杂性的测度8/6/202412算法时间复杂性一秒钟内所能处理的最大输入量一分钟内所能处理的最大输入量一小时内所能处理的最大输入量A1A2A3A4A5nn2nnn21000140311096104489324439153.61062.01051897153211.2计算复杂性的测度8/6/202413算法时间复杂性速度提高前单位时间里所能处理的数据量速度提高十倍后单位时间里所能处理的数据量速度提高一万倍后单位时间里所能处理的数据量A1A2A3A4A5nn2nnn2S1S2S3S4S510S1(S2很大)10S23.16S32.1
7、5S4S5+3.3210000S1(2S29 29000)9000S2100S321.54S4S5+13.321.2计算复杂性的测度8/6/2024141.2计算复杂性的测度现有问题可以分为以下三类：n无法写出算法的问题；n有以多项式为界的算法存在的问题，即类问题；n介于前两类问题之间的问题，“完全”问题。8/6/2024151.3随机存取模型自学8/6/202416第二章数据结构和递归技术8/6/202417表、树、图n表：a1,a2,a3,ai,ai+1,an是一个数据元素，ai-1为ai的前驱，ai+1为其后继。第一个元素没有前驱，最后一个数据元素没有后继。n顺序存储：数组n链式存储：链
8、表8/6/2024182.1图和图的表示n邻接矩阵n邻接表n邻接向量n关联矩阵一般有以上几种图的常用表示法8/6/2024192.2树n仅有一个没有边进入的顶点，这个顶点称为这棵树的根；n除根以外的其它任何顶点，有且只有一条边进入该顶点；n从根到每一个顶点都有一条唯一的道路。8/6/2024202.2树n二叉树：根最多有两个孩子，若有左子，左孩子为二叉树；若有右孩子，右孩子为二叉树。n完全二叉树：结点深度最多差1，除没有孩子的结点所在层为满二叉树，没有孩子的结点集中在左边。n满二叉树：所有叶片的深度都相等的完全二叉树。8/6/2024212.2树树的遍历n先序遍历n中序遍历n后序遍历8/6/2
9、024222.3递归技术n一个直接或间接地调用自身的过程称为递归过程(recursive procedure)；一个直接或间接地调用自身的算法称为递归算法。一个使用函数自身给出定义的函数叫做递归函数(recursive function)。在算法设计与分析中，使用递归技术往往使函数的定义和算法的描述简洁且易于理解。有些数据结构如二叉树等，由于其本身固有的递归特性，特别适合用递归的形式来描述。还有一些问题，虽然其本身并没有明显的递归结构，但用递归技术来求解使设计出的算法简洁易懂且易于分析。 8/6/2024232.3递归技术n例2.5阶乘函数n阶乘函数可以递归地定义为：8/6/2024242.3
10、递归技术n定义式的左右两边都引用了阶乘记号，是一个递归定义式，可递归地计算如下：int Factorial(int n)if(n = 0)return 1;elsereturn n * Factorial(n-1);8/6/2024252.3递归技术n例2.6 Fibonacci数列n无穷数列1,1,2,3,5,8,13,21,34,55,.，称为Fibonacci数列或级数。它可以递归地定义为：8/6/2024262.3递归技术n第n个Fibonacci数可以递归地计算如下：int Fibonacci(int n)if(n 1)return 1;elsereturn Fibonacci(n-
11、1) + Fibonacci(n-2);8/6/2024272.3递归技术n上述两例中的函数也可以用如下的非递归方式定义：8/6/2024282.3递归技术n并非一切递归函数都能用非递归方式定义。为了对递归函数的复杂性有更多的了解，我们再介绍一个双递归函数Achkerman函数。当一个函数及它的一个变量是由函数自身定义时，称这个函数是双递归函数。 8/6/2024292.3递归技术nAcheman函数A(n,m)有两个独立的整变量m0 和 n0，其定义如下：n 8/6/2024302.3递归技术nA(n,m)的自变量m的每一个值都定义了一个单变量函数。由递归式的第三式可知m = 0定义了函数“
12、加2”。n当m = 1时，由于A(1,1) = A(A(0,1),0) = A(1,0) = 2以及A(n,1) = A(A(n-1,1),0) = A(n-1,1) + 2 (n 1)，则A(n,1) = 2n (n 1)，即A(n,1)是函数“乘2”n当m = 2时 由于A(n,2) = A(A(n-1,2),1) = 2A(n-1,2)以及A(1,2) = A(A(0,2),1) = A(1,1) = 2，则有A(n,2) = 2的n次方8/6/2024312.3递归技术n大家可以试着算一下A(2,10)和A(3,4)答案分别是：222210个22222 65536个28/6/20243
13、22.3递归技术n2.3.1整数划分n把一个正整数n表示成如下形式的一系列正整数的和，叫做n的一个划分。8/6/2024332.3递归技术n正整数n的不同划分个数称为正整数n的划分数，记作P(n)，P(n)是一个数论函数。例如：正整数6有如下11种不同的划分，所以P(6) = 11。这11个划分分别是：6;5+1;4+2, 4+1+1;3+3, 3+2+1, 3+1+1+1;2+2+2, 2+2+1+1, 2+1+1+1+1;1+1+1+1+1+1。8/6/2024342.3递归技术将最大加数n1不大于m的划分个数记作Q(m,n)。我们可以建立如下的递归关系。1.Q(n,1) = 1, n 1
14、;当最大加数n1不大于1时，任何正整数n只是有种切分形式，即n = 1+1+.+1，n个1相加。2.Q(n,m) = Q(n,n), m n;最大加数n1实际上不能大于n。因此，Q(1,m) = 1。3.Q(n,n) = 1 + Q(n,n-1);正整数n的划分由n1 = n的划分和n1 n-1的划分组成。4.Q(n,m) = Q(n,m-1) + Q(n-m,m), n m 1;正整数n的最大加数n1不大于m的划分由n1 = m 的划分和n1 m-1 的划分组成。8/6/2024352.3递归技术n以上的关系实际上给出了计算Q(n,m)的递归式如下：8/6/2024362.3递归技术可以设计
15、出计算Q(n,m)的递归算法如下：int Q(int n, int m)if(n 1) | (m 1)return 0;if(n = 1) | (m = 1)return 1;if(n b-c-a构成顺时针循环。在移动圆盘的过程中，若是奇数次移动，则将最小的圆盘移到顺时针方的下一塔座上；若是偶数次移动，则保持最小的圆盘不动。而在其他两个塔座这间较小的圆盘移到另一塔座上去。 8/6/2024402.3递归技术n当n = 1 时，问题比较简单，只要将编号为1的圆盘从塔座a直接移至b上即可。当n 1 时，需要利用塔座c作为辅助塔座。此时若能设法将 n-1 个较小的圆盘按规则从塔座a移至塔座c，然后将
16、剩下的最大圆盘从塔座a移至塔座b，最后再设法将 n-1 个较小的圆盘按规则从塔座c移至塔座b。由此可见，n个圆盘的移动问题可以分为两次 n-1 个圆盘的移动问题。 8/6/2024412.3递归技术n可以设计出解Hanoi塔问题的递归算法如下：void Hanoi(int n, int a, int b, int c)if(n 0)Hanoi(n-1,a,c,b);move(a,b);Hanoi(n-1,c,b,a);8/6/2024422.3递归技术n二叉树中序遍历递归算法Void MidOrder(root)if(root != null)MidOrder(root-lchild);tre
17、at(root);MidOrder(root-rchild);8/6/2024432.3递归技术n算法Hanoi以递归形式给出，每个圆盘的具体移动方式不清楚，因此很难用手工移动来模拟这个算法。但该算法易于理解，也容易证明其正确性，而且易于掌握它的设计思想。由昆可见，用递归技术来设计算法很方便，而且设计出的算法往往比通常的算法有效。8/6/2024442.3递归技术n2.3.3递归过程的实现n像Hanoi这们的递归算法，在执行时需要多次调用自身。实现这种递归调用的关键是为算法建立递归调用工作栈。8/6/2024452.3递归技术n通常，在一个算法中调用另一个算法时，系统需要在运行被调用算法之前先
18、完成3件事：1.将所有实参指针，返回地址等信息传递给被调用算法；2.为被调用算法的局部变量分配存储区；3.将控制转移到被调用算法的入口8/6/2024462.3递归技术n在从被调用算法返回调用算法时，系统也相应地完成3件事：1.保存被调用算法的计算结果；2.释放根本给被调用算法的数据区；3.依照被调用算法保存的返回地址将控制转移到调用算法。 8/6/2024472.3递归技术n当有多个算法构成嵌套调用时，按照后调用先返回的原则进行。递归算法之间的信息传递和控制转移必须通过栈来实现，即系统闺怨整个程序运行时所需要的数据空间安排在一个栈中，每调用一个算法，就为它在栈顶分配一个存储区，每退出一个算法
19、，就释放它在栈顶的存储区。当前正在运行的算法的数据一定在栈顶。8/6/2024482.3递归技术8/6/2024492.4解递归方程n对于k阶齐次方程F(n)=a1F(n-1)+a2F(n-2)+akF(n-k)，已知：F(0),F(1),F(k-1)共k个初值n特征方程为：xk - a1xk-1 - a2xk-2 - ak-1x ak = 0；有k个根q1 , , qk8/6/2024502.4解递归方程nqi(i=1k)互不相同，通解如下：F(n) = C1q1n + C2q2n + Ckqknn若有重根q1 q2 qi= qi+r-1 qi+r qk ，通解为：F(n) = C1q1n
20、+ C2q2n + Ci-1qi-1n+(Ci+Ci+1n+Ci+r-1nr-1) qin+ Ci+rqi+rn + Ckqkn8/6/2024512.4解递归方程n对于k阶非齐次方程F(n)=a1F(n-1)+a2F(n-2)+akF(n-k)+f(n)n通解为：F(n) = F,(n) + F*(n)。其中F(n)为无f(n)时的通解，即k阶齐次方程的通解， F*(n)为特解 8/6/2024522.4解递归方程n先写出特征方程n然后根据k个初值求出待定参数Cin最后验证8/6/2024532.4解递归方程练习1nF(n)= 7F(n-1) 12F(n-2); F(0) = 4, F(1)
21、 = 0n解：特征方程为x2 - 7x + 12 = 0；解得：x1=3，x2=4；F(n) = C13n + C24n F(0) = 4, F(1) = 0C1=16，C2=-12F(n) = 163n - 124n8/6/2024542.4解递归方程练习2nF(n)= 6F(n-1) 9F(n-2) + 3F(0) = 0, F(1) = 1n解：特征方程为x2 - 6x + 9 = 0；解得：x1=x2=3；F(n) = (C1 + nC2)3n + C33 F(0) = 0, F(1) = 1,F(2)= 6 , F(1)-9F(0)+3=9C1= -3/4，C2=5/6， C3=1/
22、4F(n) = -3/4 3n + 5/63n + 3/48/6/2024552.4解递归方程练习3nF(n)= 7F(n-1) 10F(n-2) + 3nF(0) = 0, F(1) = 1n解：特征方程为x2 - 7x + 10 = 0；解得：x1=2，x2=5；F(n) = C12n + C25n + C33n F(0) = 0, F(1) = 1,F(2)= 7F(1)-10F(0)+32=16C1 = 8/3，C2 = 11/6， C3 = -9/2F(n) = 8/3 2n + 11/6 5n - 9/2 3n8/6/202456第三章分治与平衡杨素勤（）8/6/202457分治与
23、平衡的思想把一个问题分成k个同类子问题处理的分治思想和子问题规模大体相等的平衡思想（balancing）相结合,即为分治与平衡算法.8/6/202458两个非递减序列的合并下面将介绍两个有序非递减序列如何合并为一个有序序列： 给定两个非递减有序数列 和 把这两个序列按非递减有序合并入 。分别取出两个序列中的第一个元素，对这两个元素进行比较。如果a1不大于b1,则将a1存入c1，取出a2与b1进行比较。如果a1大于b1则将b1存入c1取出b2与a1进行比较。重复上述步骤，直到两个序列完全合并。8/6/202459两个非递减序列合并的算法将： 和 合并存入Procedure MERGEI i=1;
24、 j=1; k=1; While (i=m) and (j=n) do If Aim then 将bj、bj+1、bn 依次赋值给CkElse将 ai、ai+1、am 依次赋值给Ck算法中，最大的比较次数为m+n-1.8/6/202461合并排序思想n设给定集合S=x1,x2,xn,且n=2k。n当n2时，把S分成两个不相交的子集合S1=x1,x2,xn/2和集合S2=xn/2+1,xn/2+2,xn。 直到集合S分解到每个子集合的元素不超过2时为止。n比较1次即可将只有两个元素的子集排序.n调用前面的MERGEI算法将各个子集合合并。8/6/202462合并排序算法procedure MER
25、GESORTinteger: n;array: A1:n of integer;procedure SORT(A, i, j);integer: i, j, m;array: Ai:j of integer;begin if j-i=1 then if AiAj8/6/202463合并排序算法else begin m=(i+j-1)/2;SORT (A, i, m);SORT(A, m+1, j);MERGEI(Ai:m，Am+1:j) end;end;beginread(n,A);SORT(A, 1, n);write(A);end8/6/202464用二叉树来表示排序a=bb=ca=ca=
26、cb=ca, b ,ca, c, bc, a, bb, c, ac, b, ab, a, cYNYNYNYNYN8/6/202465用二叉树来表示排序n左图为一棵平衡二叉树，平均比较次数 (时间复杂度)为n(22+34) 6=2.67。n原始数据的状态会影响排序的效率。8/6/202466用二叉树来表示排序N个数排序，有n！种结果，对应的二叉树有n！片树叶。如果算法对应一棵平衡二叉树一定存在一个k使 K对应平衡二叉树中深度小的结点，而k+1则对应二叉树中深度大的结点。 若 ， 任何需要比较进行的排序算法， 已经是最好的算法数量级。8/6/202467快速排序将集合S=a1,a2,an分成小于a
27、，等于a，大于a的三个子集合S1，S2，S3。分别将S1与S3排序，最后将S1，S2和S3连接起来。优点：（1）划分以后就减少了待排序元素的数量。（2）子集合排序后采用连接而不用比较就可以归并。缺点：a难以确定恰当地确定，因此平衡的思想就难以体现。8/6/202468快速排序算法先要解决如何在同一数组中划分子集合：a1，a2，a3，an-1，anwhile ij do begin while aia do i=i+1; while aja do j=j-1; 交换ai和aj end;8/6/202469快速排序算法procedure QUICKSORT(S);if |S|=a2i , ai=a
28、2i+1 把所有要排序的元素建成一个堆，然后删去根节点上的元素。将最大深度的最右边的叶元素移至根结点，将这棵树再建成一个堆。重复上述过程，直到这棵树只剩一个顶点为止。从这个堆的根节点上删去的元素序列（按删去的先后顺序排列起来）就是一个排序好的非递增序列8/6/2024 8/6/2024824.4 堆选排序n堆排序的过程是，把初始数据“堆化”后，重复执行如下两个步骤：1. 删除根节点的元素；2. 将最深最右的叶元素移到根节点并删去这个叶，重新堆化。n在实际处理时，只需将根节点元素和待删叶元素互换，就能达到删除根节点元素和把最深最右的叶元素移至根节点上的双重目的，然后对剩下的元素重新堆化。n例 对
29、50，24，30，20，21，18，3，12，5，6进行堆排序。8/6/2024 8/6/2024834.4 堆选排序例 对50，24，30，20，21，18，3，12，5，6进行堆排序。下列的图表示删去根元素和重新堆化的过程。50242012530211836(i)624201253021183(ii) 删去50，将6移至根部8/6/2024 8/6/2024844.4 堆选排序如果用数组记录上述过程，数组元素的变化如下：(i) 50，24，30，20，21，18，3，12，5，6(ii) 6， 24，30，20，21，18，3，12，5， 50(iii) 30， 24，6，20，21，18
30、，3，12，5， 50(iv) 6， 24，18，20，21，6，3，12，5， 50302420125621183(iii) 将6与它的最大儿子30交换302420125182163(iv) 将6与它的最大儿子18交换8/6/2024 8/6/2024854.4 堆选排序n算法4.3 构造一个堆 输入 数组Ai，1in。 输出 把A的元素变成一个堆，即使得对于1in， AiA i/2 。 方法 见过程BUILDHEAP。8/6/2024 8/6/2024864.4 堆选排序n构造一个堆（算法4.3） procedure BUILDHEAP begin procedure HEAPIFY (
31、i , j ) begin if 2ij then if A2i A2i+1 且 Ai A2i+1 then begin 交换Ai和A2i+1； HEAPIFY( 2i+1 , j ); end if 2i = j then if Ai Aj then 交换Ai和Aj end begin read (A1， A2， An); for i n/2 step -1 until 1 do HEAPIFY ( i , n ) end8/6/2024 8/6/2024874.4 堆选排序n算法算法4.4 堆选排序算法。 输入 数组A1:n。 输出 按非递减序排列的结果。 方法 见过程HEAPSORT p
32、rocedure HEAPSORT: begin BUILDHEAP; for i n step -1 until 2 do begin 交换A1和Ai； HEAPIFY (1, i-1); end end 8/6/2024 8/6/2024884.4 堆选排序n定理定理4.5 算法HEAPSORT对n个元素排序所需的时间是O(n log2n)。8/6/2024 8/6/2024894.5 插入法n分段逆序插入法 设A=a1，a2，am是一个非递减序列。B=b1，b2，bm+是序列A的伴随序列，即对一切1im，有biai，其中的值是0或1。将B中的元素插入到序列A中，使A、B合并为一个大的非递
33、减的序列。因为已知biai，所以对任何bi，只要能把它插入到a1，a2，ai-1的合适位置即可。如果在bi插入前，已有某个bj(ji) 已插入到a1，a2，ai-1中， bi同样可以插入到ai左部的部分序列中。8/6/2024 8/6/2024904.5 插入法nbi插入的方法就是所谓的分段逆序插入法。n对较小的m，序列B中元素的插入顺序和所需比较的次数见下表。Aa1a2a3a4a5a6a7a8a9a10a11a12a13a21a22a23a43a44Bb1b2b3b4b5b6b7b8b9b10b11b12b13b21b22b23b43b44bi插入顺序13254111098762120124
34、3422285最大的比较次数022334444445556667Bi插入的顺序和所需的比较次数8/6/2024 8/6/2024914.5 插入法nbi的插入顺序和所需比较次数是这样得到的。因为b1a1，直接把b1置于a1的前面。当m+3时，先将b3按折半查找插入序列b1a1a2中，需要两次比较。插入的结果，即使b3小于a2，再插入b2时，也不过是将它插入b1a1和b3构成的长度为三的序列中，仍然只要两次比较。至此，a4以前一共有6个元素。如果m+则先插b5，后查b4，它们最多时插入一个7元序列中，各需三次比较等等。n为严格描述分段逆序折半插序，定义了一个递归函数f(n)（称做分段函数）。它是
35、f (n) =1, 当n=1时2n+f(n-1), 当n=1时8/6/2024 8/6/2024924.5 插入法n算法算法4.5 分段逆序插入法 输入 非递减序列A= =a1，a2，am和它的伴随序列B=b1， b2，bm+，对一切1im，有biai，其中的值是0或1。 输出 由A和B的全体元素组成的一个非递减序列。 方法 见过程BYFINSERT procedure BYFINSERT (B, A, B) begin 将b1插到a1的前面； 找到一个整数k2，使得 f(k-1) 4，做127574，560708，得 S1=574，708 S2=127，560，20 对S1排序。因为 S1=
36、 24，用“”比较“直接排序，得排序的S1为 574，7088/6/2024 8/6/2024954.5 插入法 由S1 和S2的关系，有 574 708 127 560 20 按分段逆序插入法，用两次比较（20574，20127）先将20插入序列 127574708 之中，然后将560插入序列 20127574708 之中，也只需两次比较（560127，560574），得到S1的排序结果为 201275605747088/6/2024 8/6/2024964.5 插入法第三步：用逆序插入法将S2插入S1。根据S1和S2的元素对应关系，有 20 127 560 574 708 9 11 5 4
37、3 700 31按分段逆序插入法，插入顺序依次是5，11，700，43，31。各插入结果是： 5920127560574708 11 43 700 318/6/2024 8/6/2024974.5 插入法 591120127560574708 43 700 31 591120127560574700708 43 31 59112043127560574700708 31 59112031431275605747000，Wi0，Pi0，1in，使之满足：使：达到最大。满足0xi1的任何向量（x1,x2,xn）都是一个可能解。这样的解显然有无穷多个。而最佳解必需是使式（6.2）的值达到最大的一个可
38、能解。（6.1）（6.2）8/6/20241176.1 背包问题n例：给定n=3，M=40， （W1,W2,W3）=（28,15,24）,(p1,p2,p3)=(35,25,24)。以下是此例的五个可能解： 8/6/20241186.1 背包问题n对于这个简单的实例，因为它的可能解有无穷多个，所以用组合的方法求最佳解是行不通的。n考虑，如果成立，最佳解将取xi=1。因此，不妨假定成立。这就不可能取一切xi=1。在此前提下，任何最佳解都必须将背包装满。同时，由于pi0，使利润增加。这样得到的解比原来的解要好。8/6/20241196.1 背包问题n人们可能会想到的贪心的策略：（1）按pi递减顺序
39、装包（效益增长最快） 每次选择利润Pi最大的物品装包，使得目标函数增加最快。当放不下时，才选择一个适当的xi1，使物品装满，可求出每一种货物装入背包的比例X (x1, x2, x3) x1=1，CU=M-28=40-28=12， x2=CU/W2=12/15=4/5，CU=0， x3=0 所以，X=(1,4/5,0)，8/6/20241206.1 背包问题（2）按Wi非递减顺序装包（背包容量消耗最慢） x2=1，CU=M-15=40-15=25， x3=1，CU=25-24=1 x1=1/28 所以，X=(1/28,1,1)。（3）按Pi/Wi（单位重量效益）递减顺序装包 每次选择利润与重量比
40、最大的物品先装包。 先算出每种货物的单位重量效益：(35/28,25/15,24/24) x2=1，CU=25 x1=25/28 8/6/20241216.1 背包问题n总结：n由上面的结果可看出，策略(1)显然不是最佳解，因为这种选择方法虽然每一步都使目标函数得到最大的增量，但由于背包也很快背装满了，加入目标函数的Pi的个数少了，不一定能使目标函数达到最大。n策略(2)也不是最佳解，虽然背包的重量上升很慢，却没有兼顾利润的增长速度，不能保证得到最佳解。n策略(3)考虑到利润增长和容量消耗二者的综合效果，因此可以得到一个相对的最佳解。 8/6/2024122n背包问题的贪心算法：Input:
41、P(1,2n),W(1,2n),MOutput: x1,x2xnVoid Greedy()float P, W, X, M, CU; int i,n; 输入P1,2n, W1,2n, M; /按pi/wi从大到小的顺序输入 for(i=1;i=n;i+) xi=0; CU=M /CU是背包的剩余容量 int I=1； while(WI=CU) /背包未满 xI=1; CU=CU-WI; I=I+1; xI=CU/WI;8/6/20241236.2 多处理机调度n设有n台相同的处理机P1,P2,Pn，处理m个独立的作业J1,J2,Jm，以互不相关的工作方式工作。n规定：任何作业可以在任何一台处理
42、机上运行，但未完工前不允许中断作业；作业也不能折分成更小的子作业。n多处理机调度：多处理机调度：已知作业Ji需要的处理机时间为ti，i=1,2,m。我们的任务是给出一种作业调度方案，使m个作业在尽可能短的时间内，由n台处理机完成。8/6/20241246.2 多处理机调度n例：设有三台处理机和九个作业，这些作业需要的运行时间分别是81，40，26，4，65，98，53，71，15。按上述调度法则，各处理机分配的作业表将如下图所示。总完工时间是166。 P1P2P3J181J753J44J240J698J871J326J565J915（a）一种简单的多处理机调度方案）一种简单的多处理机调度方案8
43、/6/20241256.2 多处理机调度P1P2P3J698J240J44J181J753J326J271J565J915（a）先长后短调度）先长后短调度方案（a）是按作业花费时间的长短进行调度的，把需时较长的作业优先安排，先将作业按运行时间的长短从大到小排成非递增序，然后给空闲的处理机依次分配作业。总完工时间是160。8/6/20241266.2 多处理机调度P1P2P3J698J753J181J240J326J44J871J565J915（b）最佳调度）最佳调度方案（b）是本例的一个最佳调度方案。它们的完工时间是151。由此可见贪心算法得到的不一定是最佳方案。8/6/2024127第七章
44、回溯法n问题描述n算法思想n状态空间树n皇后问题n算法复杂度分析8/6/20241287.1 问题分析n求一个n元向量（x1,x2,xn）,使之满足对 问题的某个判定函数B（ x1,x2,xn ）规定的条件。若Xi i, | Si |= Mi,则所有可能的选择有 mi种,对Xi的取值有明确要求，称为显约束。判断函数规定的约束成为隐约束。8/6/20241297.2 算法思想 从部分分量（x1,x2,xi）出发（i=1，2，n-1), 选择xi+1, 如果（x1,x2,xi+1）满足判定函数规定的条件，且i+1=n，则得到一个解；若（x1,x2,xi+1）满足判定函数，但i+1n,继续选择xi+
45、2，若（x1, x2 , ,xi）不满足判定函数，则另选xi+1，如果可供选择的xi+1均不满足判定条件，则重新选择xi（回溯）.8/6/20241307.2 算法思想n注意：判定函数的设计应使其部分向量 可计算！8/6/20241317.3 状态空间树n为了我们叙述的方便，我们在这里先介绍一些相关的概念，回溯法是采用体统地搜索给定问题的解空间的方法来确定问题的解。使用一种所谓解空间的树形结构将使这种搜索容易实现。对于一个解空间，可能有很多树形结构与之相对应。相关的例子请参照课本。我们现在来定义解空间树形结构的一些术语。8/6/20241327.3 状态空间树n树上的每一个节点定义了一个“问题
46、状态问题状态”；n从根到每个节点的所有路径定义了这一问题的“状态空间状态空间“；n“问题状态”集的子集S组成了问题的“解状态集解状态集”；n可以生孩子的节点成为“活节点活节点”，存储活节点的表成为活节点表；活节点表；8/6/20241337.3 状态空间树n正在生孩子的节点称为扩展节点；扩展节点；n不能生孩子的节点称为死节点。死节点。8/6/20241347.4 皇后问题n介绍完相关的概念后，我们将介绍一个关于回溯法的例子，当然，这个例子具有广泛的代表性，这就是皇后问题。8/6/20241357.4 皇后问题问题： n个皇后，置于n*n的方格内，如果任何两个皇后处于同一行，同一列，或处于与边线
47、成45角的斜线上，都会遭到对方攻击，求一种互不遭到攻击的状态。8/6/20241367.4 皇后问题n我们规定第i个皇后位于第i行，n个皇后所在的列构成一个n元向量（x1,x2,xi） ，xi1，2，n.8/6/20241377.4皇后问题皇后甲（i,j） 皇后乙（k,l） |(i-k)/(j-l)|1 B= (i-k)/(j-l)8/6/20241387.4 皇后问题下面我们已四皇后问题为例：首先：i=1（放置第1个皇后） （18/6/20241397.4皇后问题ni=2 （1，2 （因（1-2）/（1-2）=1） 故 （1，38/6/20241407.4 皇后问题ni=3（1，3，2 （1
48、，3，4 我们发现第三个皇后已经没有合适的位置，此时需要重新放置第（i-1）个（即第2个皇后），此时，我们就说，我们需要进行回溯；8/6/20241417.4 皇后问题ni=i-1=2（1，48/6/20241427.4 皇后问题ni=3（1，4，28/6/20241437.4 皇后问题ni=4（1，4，2 ，3 此时，再次回溯。8/6/20241447.4 皇后问题ni=i-1=3（1，4，3 又一次回溯8/6/20241457.4 皇后问题n由于第2个皇后已经没有合适的位置，所以一直回到i=1，我们的工作又回到了起点！8/6/20241467.4 皇后问题n按照以上的方法，最终可以得到一种
49、4皇后互不攻击的序列（2（2，1 （2，3 （2，4 （2，4，1（2，4，1，3)8/6/20241477.4 皇后问题 当然，照此方法，我们还可以得到其它互不攻击的序列。实际上，根据对称关系，即可得到另一个解为： （3，1，4，2) 8/6/20241487.5 算法复杂度分析一个回溯过程的效率在很大程度上依赖于四个方面的因素：n产生显约束函数X(k)的时间；n满足显约束的值X(k)的个数；n计算约束函数Bi (x1,x2,xi)的时间 ；n满足约束函数Bi (x1,x2,xi)的X(k)的个数.8/6/20241497.5 算法复杂度分析n若从节点数目考虑，能显著地减少生成节点数目的约束
50、函数就是良好的约束函数；n如果从计算Bi (x1,x2,xi)的角度考虑，约束函数越容易计算越好；n然而，我们在选择约束函数时，即要考虑使生成的结点少又要使Bi (x1,x2,xi)容易计算是比较困难的。8/6/20241507.5 算法复杂度分析n在研究效率时，一般要应用到“重排原重排原理理”,对许多问题而言，集合Si可以取任意的顺序，因此，我们可以考虑在其它条件等价的情况下，从具有最小元素个数集合中进行下一步抉择将更为有效。根据这一原则，我们将能够得到效果较好的状态空间树。8/6/20241517.5 算法复杂度分析n状态空间树选定以后，影响回溯效率的前三个因素就可以确定，只有生成节点的数
51、目是可变的，它将随问题的性质内容及节点的不同生成方式而变动。n如果解空间的节点数是2或2！，在最坏情况下，回溯法的时间耗费一般为O(p(n) 2)或O(q(n)n!)。其中O(p(n) 2)和O(q(n)n!)均为n的多项式。8/6/2024152 作业n设计16皇后的程序，输出其中的一个解，并输出其总共有多少个解，要有计时器，计算并显示运行时间。8/6/2024153第第 8 章章 分支限界法分支限界法8.1 分支限界法与回溯法的不同8.2 分支限界法的基本思想8.3 15迷问题(15-puzzle) 8.4 课后阅读和作业8/6/20241548.1 分支限界法与回溯法的不同n回溯法只能淘
52、汰不能达到解的分支，而不能选择最有利于达到解的分支。n而分支限界法一般要设计一种判定函数，对每个活结点，均可计算判定函数的值，比较这些值即可选择扩展结点，使之能更好地朝着状态空间树上有最佳解的分支推进，以便尽快找出一个最佳解。n活结点表一定是栈(回溯法),不一定是栈(分支限界法)8/6/20241558.2 分支限界法的基本思想（1）n代价函数：达到回答状态所需的工作量。n估值函数：代价函数的估价值。n判断函数：或者是代价函数，或者是估值函数。总之，它是选择扩展结点的依据。8/6/2024156分支限界法的基本思想（2）n一个结点一旦作为扩展结点，就要生完所有孩子，而这些孩子都进入活结点表，计
53、算判断函数是针对活结点表中的所有结点，这样才能根据这些结点的判断函数值去选择最有利于达到回答状态的结点作为扩展结点。8/6/2024157分支限界法的基本思想（3）n在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。n此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。此过程一直持续到找到所需的解或活结点表为空时为止。 8/6/20241588.3 15迷问题（1）n问题描述：所谓15迷(15-puzzle)问题是在一个 4X4的
54、方格棋盘上,将数字1，2，3，14，15以任意顺序置入棋盘的各个方格中，空出一格。问题是希望通过有限次的移动，把一个给定的初态（下页图a）变成目标状态（下页图b） 。移动规则是：每次只能在空格相临的数字中任选一个移入空格。8/6/202415915迷问题（2）1234515127611 148910 1312345678910 11121314 15 15 15迷问题的一些排列迷问题的一些排列图a图b图c8/6/202416015迷问题（3）n定理定理8.1 对一个给定的初态，如果空格位于（j，k），如果 是偶数，则这个初态可以变换成目标状态，否则，其它任何初态都不可能变换成目标状态。其中LE
55、SS(i)是棋盘上第i+1格到第16格中，较i格中的棋子号码小的棋子个数。（空格为16号）。n在初始状态下，如果空格在上页图图c的阴影位置中的某一格处，则令x=1；否则令x0，定理简化为判断 是否为偶数。 =+161)(ij+kiLESS8/6/202416115迷问题（4）n给出一个便于计算成本估计值的函数c(x)f(x)+g(x)，其中f(x)是由根到结点x路径的长度，g(x)是以x为根的子树中由x到目标状态的一条最短路径长度的估计值。具体搜索过程见下页图。 8/6/202416215迷问题（5）12345689107 1113 14 15 1212345689107 1113 14 15
56、 1212345689107 1113 14 15 12123456891071113 14 15 1212345689107 1113 14 15 1212345689107 1113 14 15 1212345689107 1113 14 15 1212345689107 1113 14 15 12123456891071113 14 15 12123456891071113 14 15 12123456891071113 14 15 12123456891071113 14151212345689107 1113 14 15 1212345689107 1113 14 15 121234
57、5689107 1113 14 15 1212345689107 1113 14 15 1212345689107 1113 14 15 1212345689107 1113 14 15 12123456891071113 14 15 12123456891071113 14 1512123456891071113 14 15 12123456891071113 14 1512123456891071113 14 15 12有判定函数的搜索法上右下左右左上下下右左下左上下下左左左下上下12345678910111213141516171819202122238/6/20241638.4 八皇后
58、问题(1)n问题描述：这是高斯1850年提出的一个著名问题：国际象棋中的“皇后”在横向、直向、和斜向都能走步和吃子，问在88=64格的棋盘上如何能摆上八个皇后而使她们都不能互相吃。n注：现已知此问题共有92种解，但只有12种是独立的，其余的都可以由这12种利用对称性或旋转而得到。8/6/2024164八皇后问题(2)n为简单起见，以四皇后问题为例。设棋盘有44=16格，每行所摆的皇后都有四种可能的位置，四个皇后共有4X4=256种摆法。如将这些摆法都列出来再选其中合乎条件的方案，就太费时间了。现构成一个树，根结点的四个子树表示第一行的皇后的四种可能的位置；再下一层表示第二行的位置；。设以F表示
59、失败，S表示成功。如果上面的行已经无法摆了，则下面的行表示失败，S表示成功。如果上面的行已经无法摆了，则下面的行即不必再试，返回上一层再试其它分支。8/6/2024165八皇后问题(3)n假设第一行的皇后先放在第一列，如图（a）所示，则第二行只有三、四列还可以摆。若暂先试第三列，第三行就完全无法再摆，只好回溯到上一层再试另一个分支，即第二行放第四列。这样第三行还剩第二列可以摆，但第四行又无法再摆了。此时只好返回到最上一层，改试第一行放第二列，。最后构成的树如下下页所示，共有两个可行方案，实际上这是两个对称的方案。8/6/2024166八皇后问题(4)8/6/2024167八皇后问题(5)8/6/2024168八皇后问题(6)n因为从所有失败的方案返回时该部分子树即不必保留，所以最终内存中只保留成功方案的几条单链分支，比图中所示之树还要简单。如果每试出一个成功方案就立即输出而不必存储，或只试出一个方案就可以了，则只需一个单链，更可以节约存储量。8/6/2024169八皇后问题(7)n在用这种方法解决优化问题时（以下以最小化问题来说明，最大化问题也与此类似），如果能事先估计出每个分支的下界值，当某分支的下界值比已试过的方案的值还要高时，这整个子树即不必再考虑，因此常常可以大大节约运算时间。8/6/20241708.5 课后阅读和作业n待定8/6/2024171
