算法设计与分析课件.ppt

算法设计与分析8/21/20241内容n计算模型和计算复杂性的测度n数据结构与递归技术n分治与平衡n排序n动态规划n贪心法n回溯法n分枝限界法8/21/20242第一章计算模型和计算复杂性的测度8/21/202431.1引言 1.算法的概念n基本上几乎所有的程序都是为了实现某种算法，简言之算法就是处理问题的步骤与逻辑，它是它是有穷规则的有序集合有穷规则的有序集合算法分为数值算法与非数值算法n数值算法有：概率统计计算、线性代数计算、数值逼近、数值微分、数值积分、数学规划等n数值算法是通用的，一般可用解析式表示：而非数值算法只是思想或思路，要根据具体问题按这种思想或思路进行设计8/21/202441.1引言2 算法的特征n(1)有穷性：算法应该是有穷规则，在有穷步骤后终止n(2)确定性：算法的任何一步都应该有且仅有一个解释n(3)能行性：算法应该符合问题的要求，应该在有限时间内完成n(4)输入与输出：有零个或多个外部量作为算法的输入，算法产生至少一个量作为输出8/21/202451.1引言n程序与算法不同，程序是算法用某种程序设计语言的具体实现程序可以不满足算法的有限性例如操作系统，它是在无限循环中执行的程序，因而它并不是算法。

然而可以将它的各种任务看成一些单独的问题每一个问题由操作系统的一个子程序通过特定的算法实现该子程序在得出输出结果后便终止 8/21/202461.1引言3 算法设计与分析的步骤n(1)问题的描述：明确输入与输出n(2)建立模型：将核心内容模型化，逻辑化n(3)算法设计与正确性证明：对所有正确的输入都能得到正确的输出（一般需要用谓词逻辑来证明）n(4)程序实现：用某种程序设计语言来实现n(5)算法分析：在程序实现之前进行8/21/202471.2计算复杂性的测度n算法的计算复杂性(computational complexity)是衡量算法计算难度的尺度，使用最普遍的标准是一个算法需要耗费算法需要耗费的时间和空间的时间和空间算法所需要的时间或空间，通常是问题规模的函数，这个函数就叫做算法的时间或空间复杂度在实际中用算法主操作的重复次数来表示算法的时间复杂度8/21/202481.2计算复杂性的测度n问题的规模：也就是该问题所谓的体积，或者说是大小一个问题的体积可以用一个整数来表示，它是对问题的输入数据或初始数据的多少的一种量度n定义：如果一个问题的体积是n，解决这一问题的某一算法所需要的时间为T(n)，它是n的某一函数，T(n)称作这一算法的“时间复杂性”。

当输入量n逐渐增大时，T(n)的极限情形就称作算法的“渐近时间复杂性”，类似可定义算法的空间复杂性但实际上人们主要是研究算法的时间复杂性而很少讨论它们的空间耗费8/21/202491.2计算复杂性的测度n一个算法的复杂性函数的量级是反映算法效能的重要标准当输入量急剧地增大时，如果设有高效能的算法，单纯依靠提高计算机的速度，有时是很不理想的n设有五个算法A1，A2，A3，A4，A5，它们的时间复杂性函数如下表所示：表中，一个算法的时间复杂性是它处理完一个大小为n的输入所需要的的单位时间数 8/21/202410例例1. 39个景点的全排列 39！=2.04×1046 用每秒处理1亿次（108）逻辑的计算机，需耗时6.5×1022亿年例2. 下围棋 3361=1.74×10172=5.52×10146亿年例3. 电梯从1楼到10楼，有多少种可能的方式？ 8/21/202411算法时间复杂性函数A1T1(n)=nA2T2(n)=nlog2n(nlogn)A3T3(n)=n²A4T4(n)= n³A5T5(n) =2ⁿ1.2计算复杂性的测度8/21/202412算法时间复杂性一秒钟内所能处理的最大输入量一分钟内所能处理的最大输入量一小时内所能处理的最大输入量A1A2A3A4A5nn㏒2nn²n³2ⁿ1000140311096×104489324439153.6×1062.0×1051897153211.2计算复杂性的测度8/21/202413算法时间复杂性速度提高前单位时间里所能处理的数据量速度提高十倍后单位时间里所能处理的数据量速度提高一万倍后单位时间里所能处理的数据量A1A2A3A4A5nn㏒2nn²n³2ⁿS1S2S3S4S510S1(S2很大)10S23.16S32.15S4S5+3.3210000S1(㏒2S2≥9 ㏒29000)>9000S2100S321.54S4S5+13.321.2计算复杂性的测度8/21/2024141.2计算复杂性的测度现有问题可以分为以下三类：n无法写出算法的问题；n有以多项式为界的算法存在的问题，即Ｐ类问题；n介于前两类问题之间的问题，“ＮＰ——完全”问题。

8/21/2024151.3随机存取模型自学8/21/202416第二章数据结构和递归技术8/21/202417表、树、图n表：a1,a2,a3,…,ai,ai+1,…an是一个数据元素，ai-1为ai的前驱，ai+1为其后继第一个元素没有前驱，最后一个数据元素没有后继n顺序存储：数组n链式存储：链表8/21/2024182.1图和图的表示n邻接矩阵n邻接表n邻接向量n关联矩阵一般有以上几种图的常用表示法8/21/2024192.2树n仅有一个没有边进入的顶点，这个顶点称为这棵树的根；n除根以外的其它任何顶点，有且只有一条边进入该顶点；n从根到每一个顶点都有一条唯一的道路8/21/2024202.2树n二叉树：根最多有两个孩子，若有左子，左孩子为二叉树；若有右孩子，右孩子为二叉树n完全二叉树：结点深度最多差1，除没有孩子的结点所在层为满二叉树，没有孩子的结点集中在左边n满二叉树：所有叶片的深度都相等的完全二叉树8/21/2024212.2树树的遍历n先序遍历n中序遍历n后序遍历8/21/2024222.3递归技术n一个直接或间接地调用自身的过程称为递归过程(recursive procedure)；一个直接或间接地调用自身的算法称为递归算法。

一个使用函数自身给出定义的函数叫做递归函数(recursive function)在算法设计与分析中，使用递归技术往往使函数的定义和算法的描述简洁且易于理解有些数据结构如二叉树等，由于其本身固有的递归特性，特别适合用递归的形式来描述还有一些问题，虽然其本身并没有明显的递归结构，但用递归技术来求解使设计出的算法简洁易懂且易于分析 8/21/2024232.3递归技术n例2.5阶乘函数n阶乘函数可以递归地定义为：8/21/2024242.3递归技术n定义式的左右两边都引用了阶乘记号，是一个递归定义式，可递归地计算如下：int Factorial(int n){if(n == 0)return 1;elsereturn n * Factorial(n-1);}8/21/2024252.3递归技术n例2.6 Fibonacci数列n无穷数列1,1,2,3,5,8,13,21,34,55,...，称为Fibonacci数列或级数它可以递归地定义为：8/21/2024262.3递归技术n第n个Fibonacci数可以递归地计算如下：int Fibonacci(int n){if(n ≤ 1)return 1;elsereturn Fibonacci(n-1) + Fibonacci(n-2);}8/21/2024272.3递归技术n上述两例中的函数也可以用如下的非递归方式定义：8/21/2024282.3递归技术n并非一切递归函数都能用非递归方式定义。

为了对递归函数的复杂性有更多的了解，我们再介绍一个双递归函数——Achkerman函数当一个函数及它的一个变量是由函数自身定义时，称这个函数是双递归函数 8/21/2024292.3递归技术nAcheman函数A(n,m)有两个独立的整变量m≥0 和 n≥0，其定义如下：n 8/21/2024302.3递归技术nA(n,m)的自变量m的每一个值都定义了一个单变量函数由递归式的第三式可知m = 0定义了函数“加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/21/2024312.3递归技术n大家可以试着算一下A(2,10)和A(3,4)答案分别是：222```2｝10个2222```2 ｝65536个28/21/2024322.3递归技术n2.3.1整数划分n把一个正整数n表示成如下形式的一系列正整数的和，叫做n的一个划分。

8/21/2024332.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+18/21/2024342.3递归技术将最大加数n1不大于m的划分个数记作Q(m,n)我们可以建立如下的递归关系1.Q(n,1) = 1, n ≥ 1;当最大加数n1不大于1时，任何正整数n只是有种切分形式，即n = 1+1+...+1，n个1相加2.Q(n,m) = Q(n,n), m ≥ n;最大加数n1实际上不能大于n因此，Q(1,m) = 13.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/21/2024352.3递归技术n以上的关系实际上给出了计算Q(n,m)的递归式如下：8/21/2024362.3递归技术可以设计出计算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 < m)return Q(n,n);if(n == m)return Q(n,m-1) + 1;elsereturn Q(n,m-1) + Q(n-m, m);}8/21/2024372.3递归技术nHanoi塔问题设a,b,c是3个塔座。

开始时，在塔座a上一叠共n个圆盘，这些圆盘自下而上，由大到小地叠在一起各圆盘从小到大编号为1,2,...,n 8/21/2024382.3递归技术n现在要求将塔座a上的这些圆盘移到b上，并仍按有序位置叠置在移到圆盘时应该遵守以下规则：1.每次只能移动一个圆盘；2.任何时刻都不允许将大盘压在小盘上；3.在满足规则1和规则2的前提下，可将圆盘移至a,b,c中任何一个塔座上8/21/2024392.3递归技术n这人问题有一个简单的解法假设塔座a,b,c排成一个三角形，a->b->c->a构成顺时针循环在移动圆盘的过程中，若是奇数次移动，则将最小的圆盘移到顺时针方的下一塔座上；若是偶数次移动，则保持最小的圆盘不动而在其他两个塔座这间较小的圆盘移到另一塔座上去 8/21/2024402.3递归技术n当n = 1 时，问题比较简单，只要将编号为1的圆盘从塔座a直接移至b上即可当n > 1 时，需要利用塔座c作为辅助塔座此时若能设法将 n-1 个较小的圆盘按规则从塔座a移至塔座c，然后将剩下的最大圆盘从塔座a移至塔座b，最后再设法将 n-1 个较小的圆盘按规则从塔座c移至塔座b由此可见，n个圆盘的移动问题可以分为两次 n-1 个圆盘的移动问题。

8/21/2024412.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/21/2024422.3递归技术n二叉树中序遍历递归算法Void MidOrder(root){if(root != null){MidOrder(root->lchild);treat(root);MidOrder(root->rchild);}}8/21/2024432.3递归技术n算法Hanoi以递归形式给出，每个圆盘的具体移动方式不清楚，因此很难用手工移动来模拟这个算法但该算法易于理解，也容易证明其正确性，而且易于掌握它的设计思想由昆可见，用递归技术来设计算法很方便，而且设计出的算法往往比通常的算法有效8/21/2024442.3递归技术n2.3.3递归过程的实现n像Hanoi这们的递归算法，在执行时需要多次调用自身实现这种递归调用的关键是为算法建立递归调用工作栈8/21/2024452.3递归技术n通常，在一个算法中调用另一个算法时，系统需要在运行被调用算法之前先完成3件事：1.将所有实参指针，返回地址等信息传递给被调用算法；2.为被调用算法的局部变量分配存储区；3.将控制转移到被调用算法的入口8/21/2024462.3递归技术n在从被调用算法返回调用算法时，系统也相应地完成3件事：1.保存被调用算法的计算结果；2.释放根本给被调用算法的数据区；3.依照被调用算法保存的返回地址将控制转移到调用算法。

8/21/2024472.3递归技术n当有多个算法构成嵌套调用时，按照后调用先返回的原则进行递归算法之间的信息传递和控制转移必须通过栈来实现，即系统闺怨整个程序运行时所需要的数据空间安排在一个栈中，每调用一个算法，就为它在栈顶分配一个存储区，每退出一个算法，就释放它在栈顶的存储区当前正在运行的算法的数据一定在栈顶8/21/2024482.3递归技术8/21/2024492.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/21/2024502.4解递归方程nqi(i=1…k)互不相同，通解如下：F(n) = C1q1n + C2q2n +…+ Ckqknn若有重根q1≠ q2≠…≠ qi=…= qi+r-1 ≠ qi+r ≠…≠ qk ，通解为：F(n) = C1q1n + C2q2n +…+ Ci-1qi-1n+(Ci+Ci+1n+…+Ci+r-1nr-1) qin+ Ci+rqi+rn +…+ Ckqkn8/21/2024512.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/21/2024522.4解递归方程n先写出特征方程n然后根据k个初值求出待定参数Cin最后验证8/21/2024532.4解递归方程练习1nF(n)= 7F(n-1) – 12F(n-2); F(0) = 4, F(1) = 0n解：特征方程为x2 - 7x + 12 = 0；解得：x1=3，x2=4；F(n) = C13n + C24n∵ F(0) = 4, F(1) = 0∴C1=16，C2=-12∴F(n) = 16×3n - 12×4n8/21/2024542.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 + C3×3 ∵ F(0) = 0, F(1) = 1,F(2)= 6 , F(1)-9F(0)+3=9∴C1= -3/4，C2=5/6， C3=1/4∴F(n) = -3/4 ×3n + 5/6×3n + 3/48/21/2024552.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=16∴C1 = 8/3，C2 = 11/6， C3 = -9/2∴F(n) = 8/3 ×2n + 11/6 ×5n - 9/2 × 3n8/21/202456第三章分治与平衡杨素勤（１２００６００９８５）8/21/202457分治与平衡的思想把一个问题分成k个同类子问题处理的分治思想和子问题规模大体相等的平衡思想（balancing）相结合,即为分治与平衡算法.8/21/202458两个非递减序列的合并下面将介绍两个有序非递减序列如何合并为一个有序序列： 给定两个非递减有序数列 和 把这两个序列按非递减有序合并入 。

分别取出两个序列中的第一个元素，对这两个元素进行比较如果a1不大于b1,则将a1存入c1，取出a2与b1进行比较如果a1大于b1则将b1存入c1取出b2与a1进行比较重复上述步骤，直到两个序列完全合并8/21/202459两个非递减序列合并的算法将： 和 合并存入Procedure MERGEI i=1; j=1; k=1; While (i<=m) and (j<=n) do If A[i]<=B[j] then begin C[k]=A[i]; i=i+1; k=k+1;end;8/21/202460两个非递减序列合并的算法else C[k]=B[j]; j=j+1; k=k+1;end;if i>m then {将bj、bj+1、…、bn 依次赋值给Ck}Else{将 ai、ai+1、…、am 依次赋值给Ck}算法中，最大的比较次数为m+n-1.8/21/202461合并排序思想n设给定集合S={x1,x2,……,xn},且n=2k。

n当n>2时，把S分成两个不相交的子集合S1={x1,x2,……xn/2}和集合S2={xn/2+1,xn/2+2,……,xn} 直到集合S分解到每个子集合的元素不超过2时为止n比较1次即可将只有两个元素的子集排序.n调用前面的MERGEI算法将各个子集合合并8/21/202462合并排序算法procedure MERGESORTinteger: n;array: A[1:n] of integer;procedure SORT(A, i, j);integer: i, j, m;array: A[i:j] of integer;begin if j-i=1 then if A[i]>A[j]8/21/202463合并排序算法else begin m=(i+j-1)/2;SORT (A, i, m);SORT(A, m+1, j);MERGEI(A[i:m]，A[m+1:j]) end;end;beginread(n,A);SORT(A, 1, n);write(A);end8/21/202464用二叉树来表示排序a>=bb>=ca>=ca>=cb>=ca, b ,ca, c, bc, a, bb, c, ac, b, ab, a, cYNYNYNYNYN8/21/202465用二叉树来表示排序n左图为一棵平衡二叉树，平均比较次数 (时间复杂度)为n(2×2+3×4) ÷6=2.67。

n原始数据的状态会影响排序的效率8/21/202466用二叉树来表示排序N个数排序，有n！种结果，对应的二叉树有n！片树叶如果算法对应一棵平衡二叉树一定存在一个k使 K对应平衡二叉树中深度小的结点，而k+1则对应二叉树中深度大的结点 若 ， 任何需要比较进行的排序算法， 已经是最好的算法数量级8/21/202467快速排序将集合S={a1,a2,……,an}分成小于a，等于a，大于a的三个子集合S1，S2，S3分别将S1与S3排序，最后将S1，S2和S3连接起来优点：（1）划分以后就减少了待排序元素的数量2）子集合排序后采用连接而不用比较就可以归并缺点：a难以确定恰当地确定，因此平衡的思想就难以体现8/21/202468快速排序算法先要解决如何在同一数组中划分子集合：a1，a2，a3，……，an-1，anwhile i

8/21/202471第四章第四章 排序排序8/21/202472目录n4.1 排序的定义n4.2 基数排序n4.3 比较排序的时间下界n4.4 堆选排序n4.5 插入法8/21/2024 8/21/2024734.1 排序的定义n半序的定义 定义定义 如果集合S上的一个关系R，对于S中的任何元素a，b，c，若 1. aRa为真 （自反性）； 2. 由aRb和bRc可得aRc （传递性）； 3. 由aRb和bRa可得a=b （反对称性）； 则称R为集合S上的一个半序半序 (partia order) 8/21/2024 8/21/2024744.1 排序的定义n排序的定义 给定一个从有线性序R的集合中抽出来的n个元素a1，a2，…，an所谓将这n个元素排序就是要找出1，2，…，n的一个特定排列 ∏(1)，∏(2) ，…，∏(n)，使得对于任何i， 1≤ i＜n，有a∏(i)Ra∏(i+1)当关系R是“≤”时，既有 a∏(i) ≤ a∏(i+1) ≤ …≤ a∏(n) 8/21/2024 8/21/2024754.2 基数排序n待排序元素a1，a2，…，an，将其置于一个桶（队列）Q中。

ak均为k元组，每一元由m个不同的符号而组成,另设m个不同的桶分别对应m个符号将Q中元素按元分装到m个桶中，再将m个桶中的元素归并到Q中，如此进行k次，即可使Q中的元素有序8/21/2024 8/21/2024764.2 基数排序n例 用桶排序法将以下6个数排序： 379，258，731，432，913，455 8/21/2024 8/21/2024774.2 基数排序n算法4.1 桶排序法 输入 一个序列A1，A2，…，An；这里每个元素Ai是一个K元组（ ai1ai2…aik），其中，对一切i,，j； 1≤i≤n， 1≤j≤k，有0≤aij≤m-1 输出 序列A∏(1) ≤ A∏(2) ≤ … ≤ A∏(n) ，它是A1，A2，…，An的一个排列 方法 使用队列QUEUE存放“当前的元素序列”，还有m个桶Q[0]，Q[1]，…，Q[m-1]，它们都是一个先进先出的对列用Q[i]来存放当前的分量是正数i的那些元素参见过程BUCKETSORT）8/21/2024 8/21/2024784.2 基数排序n基数排序算法（算法4.1） procedure BUCKETSORT begin 置A1，A2，…，An到队列QUEUE中； for i←j step -1 until 1 do begin for I←0 to m-1 do 置Q[I]为空； while QUEUE非空 do 把QUEUE中的第一个元素Ai置入桶Q[aij]中； for l←0 to m-1 do 依次置Q[l]中的元素到QUEUE中 end end 定理定理4.1 算法BUCKETSORT将n个元素排序所需的时间是O(k(m+n))，其中k是每个元素的长度，每个分量是介于0到m-1之间的整数。

8/21/2024 8/21/202479问题n能否用基数排序法对不超过k元的多元组进行排序?n若回答肯定,对元组分别为多数字和字符串时如何处理?8/21/2024804.3 比较排序的时间下界n引理引理4.1 一棵高为h的二叉树，最多有2h个叶n定理定理4.3 将n个不同元素排序的任一判定树的高不小于「log2n!」8/21/2024 8/21/2024814.4 堆选排序n堆选排序 堆是一棵完全二叉树且 ai>=a2i , ai>=a2i+1 把所有要排序的元素建成一个堆，然后删去根节点上的元素将最大深度的最右边的叶元素移至根结点，将这棵树再建成一个堆重复上述过程，直到这棵树只剩一个顶点为止从这个堆的根节点上删去的元素序列（按删去的先后顺序排列起来）就是一个排序好的非递增序列8/21/2024 8/21/2024824.4 堆选排序n堆排序的过程是，把初始数据“堆化”后，重复执行如下两个步骤：1. 删除根节点的元素；2. 将最深最右的叶元素移到根节点并删去这个叶，重新堆化n在实际处理时，只需将根节点元素和待删叶元素互换，就能达到删除根节点元素和把最深最右的叶元素移至根节点上的双重目的，然后对剩下的元素重新堆化。

n例 对50，24，30，20，21，18，3，12，5，6进行堆排序8/21/2024 8/21/2024834.4 堆选排序例 对50，24，30，20，21，18，3，12，5，6进行堆排序下列的图表示删去根元素和重新堆化的过程50242012530211836(i)624201253021183(ii) 删去50，将6移至根部8/21/2024 8/21/2024844.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，3，12，5， 50(iv) 6， 24，18，20，21，6，3，12，5， 50302420125621183(iii) 将6与它的最大儿子30交换302420125182163(iv) 将6与它的最大儿子18交换8/21/2024 8/21/2024854.4 堆选排序n算法4.3 构造一个堆 输入 数组A[i]，1≤i≤n 输出 把A的元素变成一个堆，即使得对于1＜i≤n， A[i]≤A[「 i/2 」]。

方法 见过程BUILDHEAP8/21/2024 8/21/2024864.4 堆选排序n构造一个堆（算法4.3） procedure BUILDHEAP begin procedure HEAPIFY ( i , j ) begin if 2i

输入 数组A[1:n] 输出 按非递减序排列的结果 方法 见过程HEAPSORT procedure HEAPSORT: begin BUILDHEAP; for i ← n step -1 until 2 do begin 交换A[1]和A[i]； HEAPIFY (1, i-1); end end 8/21/2024 8/21/2024884.4 堆选排序n定理定理4.5 算法HEAPSORT对n个元素排序所需的时间是O(n log2n)8/21/2024 8/21/2024894.5 插入法n分段逆序插入法 设A={a1，a2，…，am}是一个非递减序列B={b1，b2，…，bm+∈}是序列A的伴随序列，即对一切1≤i≤m，有bi≤ai，其中∈的值是0或1将B中的元素插入到序列A中，使A、B合并为一个大的非递减的序列因为已知bi≤ai，所以对任何bi，只要能把它插入到a1，a2，…，ai-1的合适位置即可如果在bi插入前，已有某个bj(j≠i) 已插入到a1，a2，…，ai-1中， bi同样可以插入到ai左部的部分序列中。

8/21/2024 8/21/2024904.5 插入法nbi插入的方法就是所谓的分段逆序插入法n对较小的m，序列B中元素的插入顺序和所需比较的次数见下表Aa1a2a3a4a5a6a7a8a9a10a11a12a13…a21a22a23…a43a44…Bb1b2b3b4b5b6b7b8b9b10b11b12b13…b21b22b23…b43b44…bi插入顺序13254111098762120…124342…2285…最大的比较次数0223344444455…566…67…Bi插入的顺序和所需的比较次数8/21/2024 8/21/2024914.5 插入法nbi的插入顺序和所需比较次数是这样得到的因为b1≤a1，直接把b1置于a1的前面当m+∈≥3时，先将b3按折半查找插入序列b1a1a2中，需要两次比较插入的结果，即使b3小于a2，再插入b2时，也不过是将它插入b1a1和b3构成的长度为三的序列中，仍然只要两次比较至此，a4以前一共有6个元素如果m+∈≥则先插b5，后查b4，它们最多时插入一个7元序列中，各需三次比较等等n为严格描述分段逆序折半插序，定义了一个递归函数f(n)（称做分段函数）。

它是f (n) =1, 当n=1时2n+f(n-1), 当n=1时8/21/2024 8/21/2024924.5 插入法n算法算法4.5 分段逆序插入法 输入 非递减序列A= ={a1，a2，…，am}和它的伴随序列B={b1， b2，…，bm+∈}，对一切1≤i≤m，有bi≤ai，其中∈的值是0或1 输出 由A和B的全体元素组成的一个非递减序列 方法 见过程BYFINSERT procedure BYFINSERT (‖B‖, A, B) begin 将b1插到a1的前面； 找到一个整数k≥2，使得 f(k-1) < m+∈≤ f(k); 按b3，b2；b5， b4；…；bf(k-2)，bf(k-1)-1，…，bf(k-2)+1；b m+∈，…，b f(k-1)+1的顺序将bi折半插入序列A中 end8/21/2024 8/21/2024934.5 插入法n插入排序法 把要排序的n个元素，分成两个一对分别比较，把各对中较大的元素记入子序列S1中，较小的序列记入子序列S2中，即S1和S2中的元素有一对一的大小关系。

当n为奇数时，S中的第n个元素记入S2的末尾然后，将S1中的元素排序（递归的应用插入法）最后，使用分段逆序插入法把S2中的元素插入已排序的S1中，就得到n个元素的有序序列（当元素个数较少时（n≤4），就直接排序）8/21/2024 8/21/2024944.5 插入法n例 用排序法将以下11个元素排序，它们是 11，127，43，574，5，560，700，708，9，20，31第一步：11~127，43~574，5~560，700~708，9~20，31，得 S1={127，574，560，708，20} S2={11，43，5，700，9，31}第二步：将S1的元素排序因为‖S1‖= 5>4，做127~574，560~708，得 S1′={574，708} S2′={127，560，20} 对S1′排序因为‖ S1′‖= 2<4，用“”比较“直接排序，得排序的S1′为 574，7088/21/2024 8/21/2024954.5 插入法 由S1′ 和S2′的关系，有 574 < 708 ↓ ↓ 127 560 20 按分段逆序插入法，用两次比较（20~574，20~127）先将20插入序列 127<574<708 之中，然后将560插入序列 20<127<574<708 之中，也只需两次比较（560~127，560~574），得到S1的排序结果为 20<127<560<574<7088/21/2024 8/21/2024964.5 插入法第三步：用逆序插入法将S2插入S1。

根据S1和S2的元素对应关系，有 20 < 127 < 560 < 574 < 708 ↓ ↓ ↓ ↓ ↓ 9 11 5 43 700 31按分段逆序插入法，插入顺序依次是5，11，700，43，31各插入结果是： 5<9<20<127<560<574<708 ↓ ↓ ↓ 11 43 700 318/21/2024 8/21/2024974.5 插入法 5<9<11<20<127<560<574<708 ↓ ↓ 43 700 31 5<9<11<20<127<560<574<700<708 ↓ 43 31 5<9<11<20<43<127<560<574<700<708 31 5<9<11<20<31<43<127<560<574<700<708累计总的比较次数，最多要26次。

8/21/2024 8/21/2024984.5 插入法n算法算法4.6 插入排序 输入 数组A= ={a1，a2，…，an} 输出 元素a1，a2，…，an的一个非递减序列 方法 见过程INSERT(S1i, i )在应用时，只要执行语句调用INSERT(S10, 0)这里S10=A 8/21/2024 8/21/2024994.5 插入法procedure INSERT ( S1i, i) if ‖ S1i ‖≥ 4 then begin 把S1i中的元素分成「 ‖ S1i ‖ / 2」对两两比较；各组中的较大元素依次记入S1i+1中；各组中的较小元素依次记入S2i+1中当‖ S1i ‖ 为奇数时，将S1i中最末的一个元素记入S2i+1的末尾； INSERT (S1i+1, i+1); return (BYFINSERT (「 ‖ S1i ‖ / 2」, S1i+1, S2i+1) end else begin 直接将S1i中的元素排序； return (S1i) end8/21/2024 8/21/2024100第五章动态规划8/21/2024101引言n所谓动态规划（Dynamic programming）常常能得到一个比穷举法有效的算法。

动态规划的指导思想是，在每种情况下，列出各种可能的局部解，然后按某些条件，从局部解（或中间结果）中挑选出那些有可能产生最佳解的结果而扬弃其余从而大大缩减了计算量动态规划遵循所谓“最佳原理”的原则即“不论前面的状态和策略如何，后面的最优策略只取决于由最初策略所确定的当前状态即“最优化从当前状态开始”.8/21/2024102引言n动态规划所适用的问题：n1）优化问题n2）分阶段处理的问题n3）状态之间有确定次序的问题不能跨越8/21/20241035.1单源最短路径问题 1.多级图 G={V,E} 其中V是顶点的集合,E是边(弧)的集合 Vi也是顶点的集合,Ei是边的集合,如果 V = ∪Vi ∩i Vi为空 当(vl,vt)属于Ei且vl属于Vi时,必有Vt属于Vi+1,则G为多级图8/21/20241045.1单源最短路径问题n最短路径：是按道路上的代价函数来判定的如果是两个城市，道路上的代价函数可能是城市间的里程，或者旅差费用等8/21/20241055.1单源最短路径问题 COST（i,j） 第i级顶点vj到汇点的最短路径长度C(i,j) 边(vi,vj)上的权值COST（i,j）=min{c(j,l)+COST（i+1，l）},其中l属于顶点集Vi+18/21/20241065.1单源最短路径问题8/21/20241075.1单源最短路径问题n对于图5.1，计算过程如下：nCOST（3,6）=min{6+ COST（4,9）, 5+ COST（4,10）}=min{6+4, 5+ 2}=7nCOST（3,7）=min{4+ COST（4,9）, 3+ COST（4,10）}=min{4+4, 3+ 2}=5nCOST（3,8） =78/21/20241085.1单源最短路径问题nCOST（2,2）=min{4+ COST（3,6）, 2+ COST（3,7）, 1+ COST（3,8）}=min{11, 7, 8}=7nCOST（2,3） =9nCOST（2,4）=11+ COST（3,8）=18nCOST（2,5） =15nCOST（1,1）=min{9+ COST（2,2）, 7+ COST（2,3）, 3+ COST（2,4）, 2+ COST（2,5）}=min{16, 16, 21, 17}=168/21/20241095.1单源最短路径问题n因此，从S到T的一条最短路径的代价是16。

只要我们每次记下使COST（i,j）达到最小的第j+1级的顶点号，这条路径也就找到了8/21/20241105.1单源最短路径问题算法：两点间的最短路算法(由后向前)_用cost(j)代替cost(i,j),即不记录顶点所在级,存储多级图时应如何处理?____________________________________nPROCEDURE FGRAPHnBegin nFor i←1 to n do COST[i] ←0;nFor j←n-1 to 1 do //计算COST[j] //8/21/20241115.1单源最短路径问题nBegin n设L是这样一个顶点，边（j, L）属于E且c(j, L）+ COST[L]最小；nCOST[j] ←c(j, L）+ COST[L];nD[j] ←L;nEnd8/21/20241125.1单源最短路径问题n//找最小代价的道路//nP[1] ←1，P[k] ←n;nFor j←2 to k-1 donP[j] ←D[P[j-1]]nEndn________________________________8/21/2024113第六章 贪心法n任何问题，通常都有n个输入和一些约束条件。

任何满足这些约束条件的子集可称为一个可能解最佳解是满足目标函数达到最大值或最小值的一个可能解，而目标函数是问题中给定的n贪心法是一个多步决策法，每一步的选择都使得能构成问题的一个可能解（即满足问题的全部约束条件），同时使目标函数的值增加最快或增加最小n贪心法的选择过程是以某些最优化量度为根据，而最优化量度有时可以是目标函数本身，有时也可能是别的量度最优化量度的选择是贪心法的关键8/21/20241146.1 背包问题n背包问题的来源：n设某港口有n种不同的货物送往某地，每种货物的总重量是已知的，各种不同货物的运价也是确定的某支船队承运部分货物，船队的总吨位是确定的每种货物允许分批发送考虑这支船队应装运哪些货物才能使它一次获得的运费最多？8/21/20241156.1 背包问题n背包问题的一般描述：n给定n种不同的物品和一个背包物品i的重量是Wi，背包容量为M假定物品i的一部分xi(0≤xi≤1)，被放进背包里，就会得到利润 Pixi因为背包的容量为M，要求被装进的物品的总重量不超过M（若只考虑物重而不考虑其形状和体积）问应怎样选择物品的种类和数量，使背包装满，而获得最大的利润8/21/20241166.1 背包问题n背包类问题还可形式化描述为： 给定M>0，Wi>0，Pi>0，1≤i≤n，使之满足：使：达到最大。

满足0≤xi≤1的任何向量（x1,x2,…xn）都是一个可能解这样的解显然有无穷多个而最佳解必需是使式（6.2）的值达到最大的一个可能解6.1）（6.2）8/21/20241176.1 背包问题n例：给定n=3，M=40， （W1,W2,W3）=（28,15,24）,(p1,p2,p3)=(35,25,24)以下是此例的五个可能解： 8/21/20241186.1 背包问题n对于这个简单的实例，因为它的可能解有无穷多个，所以用组合的方法求最佳解是行不通的n考虑，如果成立，最佳解将取xi=1因此，不妨假定成立这就不可能取一切xi=1在此前提下，任何最佳解都必须将背包装满同时，由于pi>0，使利润增加这样得到的解比原来的解要好8/21/20241196.1 背包问题n人们可能会想到的贪心的策略：（1）按pi递减顺序装包（效益增长最快） 每次选择利润Pi最大的物品装包，使得目标函数增加最快当放不下时，才选择一个适当的xi<1，使物品装满，可求出每一种货物装入背包的比例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/21/20241206.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（单位重量效益）递减顺序装包 每次选择利润与重量比最大的物品先装包 先算出每种货物的单位重量效益：(35/28,25/15,24/24) x2=1，CU=25 x1=25/28 8/21/20241216.1 背包问题n总结：n由上面的结果可看出，策略(1)显然不是最佳解，因为这种选择方法虽然每一步都使目标函数得到最大的增量，但由于背包也很快背装满了，加入目标函数的Pi的个数少了，不一定能使目标函数达到最大n策略(2)也不是最佳解，虽然背包的重量上升很慢，却没有兼顾利润的增长速度，不能保证得到最佳解n策略(3)考虑到利润增长和容量消耗二者的综合效果，因此可以得到一个相对的最佳解 8/21/2024122n背包问题的贪心算法：Input: P(1,2…n),W(1,2…n),MOutput: x1,x2…xnVoid Greedy(){float P[], W[], X[], M, CU; int i,n; 输入P[1,2…n], W[1,2…n], M; //按p[i]/w[i]从大到小的顺序输入 for(i=1;i<=n;i++){ x[i]=0; } CU=M //CU是背包的剩余容量 int I=1； while(W[I]<=CU){ //背包未满 x[I]=1; CU=CU-W[I]; I=I+1; } x[I]=CU/W[I];}8/21/20241236.2 多处理机调度n设有n台相同的处理机P1,P2,…,Pn，处理m个独立的作业J1,J2,…,Jm，以互不相关的工作方式工作。

n规定：任何作业可以在任何一台处理机上运行，但未完工前不允许中断作业；作业也不能折分成更小的子作业n多处理机调度：多处理机调度：已知作业Ji需要的处理机时间为ti，i=1,2,…,m我们的任务是给出一种作业调度方案，使m个作业在尽可能短的时间内，由n台处理机完成8/21/20241246.2 多处理机调度n例：设有三台处理机和九个作业，这些作业需要的运行时间分别是81，40，26，4，65，98，53，71，15按上述调度法则，各处理机分配的作业表将如下图所示总完工时间是166 P1P2P3J181J753J44J240J698J871J326J565J915（（a）一种简单的多处理机调度方案）一种简单的多处理机调度方案8/21/20241256.2 多处理机调度P1P2P3J698J240J44J181J753J326J271J565J915（（a）先长后短调度）先长后短调度方案（a）是按作业花费时间的长短进行调度的，把需时较长的作业优先安排，先将作业按运行时间的长短从大到小排成非递增序，然后给空闲的处理机依次分配作业总完工时间是1608/21/20241266.2 多处理机调度P1P2P3J698J753J181J240J326J44J871J565J915（（b）最佳调度）最佳调度方案（b）是本例的一个最佳调度方案。

它们的完工时间是151由此可见贪心算法得到的不一定是最佳方案8/21/2024127第七章 回溯法n问题描述n算法思想n状态空间树n皇后问题n算法复杂度分析8/21/20241287.1 问题分析n求一个n元向量（x1,x2,……,xn）,使之满足对 问题的某个判定函数B（ x1,x2,……,xn ）规定的条件若Xi∈ i, || Si ||= Mi,则所有可能的选择有 mi种,对Xi的取值有明确要求，称为显约束判断函数规定的约束成为隐约束8/21/20241297.2 算法思想 从部分分量（x1,x2,…,xi）出发（i=1，2，…，n-1), 选择xi+1, 如果（x1,x2,…,xi+1）满足判定函数规定的条件，且i+1=n，则得到一个解；若（x1,x2,…,xi+1）满足判定函数，但i+1

使用一种所谓解空间的树形结构将使这种搜索容易实现对于一个解空间，可能有很多树形结构与之相对应相关的例子请参照课本我们现在来定义解空间树形结构的一些术语8/21/20241327.3 状态空间树n树上的每一个节点定义了一个“问题状态问题状态”；n从根到每个节点的所有路径定义了这一问题的“状态空间状态空间“；n“问题状态”集的子集S组成了问题的“解状态集解状态集”；n可以生孩子的节点成为“活节点活节点”，存储活节点的表成为活节点表；活节点表；8/21/20241337.3 状态空间树n正在生孩子的节点称为扩展节点；扩展节点；n不能生孩子的节点称为死节点8/21/20241347.4 皇后问题n介绍完相关的概念后，我们将介绍一个关于回溯法的例子，当然，这个例子具有广泛的代表性，这就是皇后问题8/21/20241357.4 皇后问题问题： n个皇后，置于n*n的方格内，如果任何两个皇后处于同一行，同一列，或处于与边线成45°角的斜线上，都会遭到对方攻击，求一种互不遭到攻击的状态8/21/20241367.4 皇后问题n我们规定第i个皇后位于第i行，n个皇后所在的列构成一个n元向量（x1,x2,…,xi） ，xi∈{1，2，…，n}.8/21/20241377.4皇后问题皇后甲（i,j） 皇后乙（k,l） |(i-k)/(j-l)|≠1 B= (i-k)/(j-l)8/21/20241387.4 皇后问题下面我们已四皇后问题为例：首先：i=1（放置第1个皇后） （18/21/20241397.4皇后问题ni=2 （1，2 ×（因（1-2）/（1-2）=1） 故 （1，38/21/20241407.4 皇后问题ni=3（1，3，2 ×（1，3，4 × 我们发现第三个皇后已经没有合适的位置，此时需要重新放置第（i-1）个（即第2个皇后），此时，我们就说，我们需要进行回溯；8/21/20241417.4 皇后问题ni=i-1=2（1，48/21/20241427.4 皇后问题ni=3（1，4，28/21/20241437.4 皇后问题ni=4（1，4，2 ，3 × 此时，再次回溯。

8/21/20241447.4 皇后问题ni=i-1=3（1，4，3 × 又一次回溯8/21/20241457.4 皇后问题n由于第2个皇后已经没有合适的位置，所以一直回到i=1，我们的工作又回到了起点！8/21/20241467.4 皇后问题n按照以上的方法，最终可以得到一种4皇后互不攻击的序列（2（2，1 ×（2，3 ×（2，4 （2，4，1（2，4，1，3)8/21/20241477.4 皇后问题 当然，照此方法，我们还可以得到其它互不攻击的序列实际上，根据对称关系，即可得到另一个解为： （3，1，4，2) 8/21/20241487.5 算法复杂度分析一个回溯过程的效率在很大程度上依赖于四个方面的因素：n产生显约束函数X(k)的时间；n满足显约束的值X(k)的个数；n计算约束函数Bi (x1,x2,…,xi)的时间 ；n满足约束函数Bi (x1,x2,…,xi)的X(k)的个数.8/21/20241497.5 算法复杂度分析n若从节点数目考虑，能显著地减少生成节点数目的约束函数就是良好的约束函数；n如果从计算Bi (x1,x2,…,xi)的角度考虑，约束函数越容易计算越好；n然而，我们在选择约束函数时，即要考虑使生成的结点少又要使Bi (x1,x2,…,xi)容易计算是比较困难的。

8/21/20241507.5 算法复杂度分析n在研究效率时，一般要应用到“重排原重排原理理”,对许多问题而言，集合Si可以取任意的顺序，因此，我们可以考虑在其它条件等价的情况下，从具有最小元素个数集合中进行下一步抉择将更为有效根据这一原则，我们将能够得到效果较好的状态空间树8/21/20241517.5 算法复杂度分析n状态空间树选定以后，影响回溯效率的前三个因素就可以确定，只有生成节点的数目是可变的，它将随问题的性质内容及节点的不同生成方式而变动n如果解空间的节点数是2ⁿ或2！，在最坏情况下，回溯法的时间耗费一般为O(p(n) 2ⁿ)或O(q(n)n!)其中O(p(n) 2ⁿ)和O(q(n)n!)均为n的多项式8/21/2024152 作业n设计16皇后的程序，输出其中的一个解，并输出其总共有多少个解，要有计时器，计算并显示运行时间8/21/2024153第第 8 章章 分支限界法分支限界法8.1 分支限界法与回溯法的不同8.2 分支限界法的基本思想8.3 15迷问题(15-puzzle) 8.4 课后阅读和作业8/21/20241548.1 分支限界法与回溯法的不同n回溯法只能淘汰不能达到解的分支，而不能选择最有利于达到解的分支。

n而分支限界法一般要设计一种判定函数，对每个活结点，均可计算判定函数的值，比较这些值即可选择扩展结点，使之能更好地朝着状态空间树上有最佳解的分支推进，以便尽快找出一个最佳解n活结点表一定是栈(回溯法),不一定是栈(分支限界法)8/21/20241558.2 分支限界法的基本思想（1）n代价函数：达到回答状态所需的工作量n估值函数：代价函数的估价值n判断函数：或者是代价函数，或者是估值函数总之，它是选择扩展结点的依据8/21/2024156分支限界法的基本思想（2）n一个结点一旦作为扩展结点，就要生完所有孩子，而这些孩子都进入活结点表，计算判断函数是针对活结点表中的所有结点，这样才能根据这些结点的判断函数值去选择最有利于达到回答状态的结点作为扩展结点8/21/2024157分支限界法的基本思想（3）n在分支限界法中，每一个活结点只有一次机会成为扩展结点活结点一旦成为扩展结点，就一次性产生其所有儿子结点在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中n此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程此过程一直持续到找到所需的解或活结点表为空时为止。

8/21/20241588.3 15迷问题（1）n问题描述：所谓15迷(15-puzzle)问题是在一个 4X4的方格棋盘上,将数字1，2，3，…，14，15以任意顺序置入棋盘的各个方格中，空出一格问题是希望通过有限次的移动，把一个给定的初态（下页图a）变成目标状态（下页图b） 移动规则是：每次只能在空格相临的数字中任选一个移入空格8/21/202415915迷问题（2）1234515127611 148910 1312345678910 11121314 15 15 15迷问题的一些排列迷问题的一些排列图a图b图c8/21/202416015迷问题（3）n定理定理8.1 对一个给定的初态，如果空格位于（j，k），如果 是偶数，则这个初态可以变换成目标状态，否则，其它任何初态都不可能变换成目标状态其中LESS(i)是棋盘上第i+1格到第16格中，较i格中的棋子号码小的棋子个数空格为16号）n在初始状态下，如果空格在上页图图c的阴影位置中的某一格处，则令x=1；否则令x＝0，定理简化为判断 是否为偶数 å=+161)(ij+kiLESS8/21/202416115迷问题（4）n给出一个便于计算成本估计值的函数c(x)＝f(x)+g(x)，其中f(x)是由根到结点x路径的长度，g(x)是以x为根的子树中由x到目标状态的一条最短路径长度的估计值。

具体搜索过程见下页图 8/21/202416215迷问题（5）12345689107 1113 14 15 1212345689107 1113 14 15 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 1212345689107 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/21/20241638.4 八皇后问题(1)n问题描述：这是高斯1850年提出的一个著名问题：国际象棋中的“皇后”在横向、直向、和斜向都能走步和吃子，问在8×8=64格的棋盘上如何能摆上八个皇后而使她们都不能互相吃。

n注：现已知此问题共有92种解，但只有12种是独立的，其余的都可以由这12种利用对称性或旋转而得到8/21/2024164八皇后问题(2)n为简单起见，以四皇后问题为例设棋盘有4×4=16格，每行所摆的皇后都有四种可能的位置，四个皇后共有4X4=256种摆法如将这些摆法都列出来再选其中合乎条件的方案，就太费时间了现构成一个树，根结点的四个子树表示第一行的皇后的四种可能的位置；再下一层表示第二行的位置；……设以F表示失败，S表示成功如果上面的行已经无法摆了，则下面的行表示失败，S表示成功如果上面的行已经无法摆了，则下面的行即不必再试，返回上一层再试其它分支8/21/2024165八皇后问题(3)n假设第一行的皇后先放在第一列，如图（a）所示，则第二行只有三、四列还可以摆若暂先试第三列，第三行就完全无法再摆，只好回溯到上一层再试另一个分支，即第二行放第四列这样第三行还剩第二列可以摆，但第四行又无法再摆了此时只好返回到最上一层，改试第一行放第二列，……最后构成的树如下下页所示，共有两个可行方案，实际上这是两个对称的方案8/21/2024166八皇后问题(4)8/21/2024167八皇后问题(5)8/21/2024168八皇后问题(6)n因为从所有失败的方案返回时该部分子树即不必保留，所以最终内存中只保留成功方案的几条单链分支，比图中所示之树还要简单。

如果每试出一个成功方案就立即输出而不必存储，或只试出一个方案就可以了，则只需一个单链，更可以节约存储量8/21/2024169八皇后问题(7)n在用这种方法解决优化问题时（以下以最小化问题来说明，最大化问题也与此类似），如果能事先估计出每个分支的下界值，当某分支的下界值比已试过的方案的值还要高时，这整个子树即不必再考虑，因此常常可以大大节约运算时间8/21/20241708.5 课后阅读和作业n待定8/21/2024171。