数据结构与算法剖析

会计学1数据结构与算法剖析本章介绍了算法 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 策略和应用实例，主要目的有两个:首先，让读者知道每种算法的适用条件，即何时可以使用和何时不能使用某种算法设计策略；其次，让读者学习基本的算法设计策略，即掌握如何描述自己的问题和高效、快速地解决问题。本章将进一步介绍五种常用算法设计策略的基本思想和实现方法，这些策略包括分治策略、贪心策略、动态规划策略、回溯策略和分支限界策略，以及它们的具体应用实例。第1页/共67页10.1分治策略10.1.1概述10.1.2算法设计步骤和程序模式10.1.3分治策略应用实例第2页/共67页分治策略是一类算法设计策略，它将原问题分解成若干部分，从而产生若干子问题，这些子问题互相独立且与原问题类型相同，然后解决这些子问题，最后把这些子问题的解合并成原问题的解。分治策略所能解决的问题，一般具有以下三个特征：原问题可以分解成规模较小、相互独立和类型相同的子问题；子问题的规模缩小到一定的程度，就不需要再分解，可以很容易地求解；所有子问题的解能够合并成原问题的解。10.1分治策略10.1.1概述第3页/共67页如图10-1所示，采用分治策略的算法设计都包括分解、求解和合并三个步骤：（1）分解：将原问题分解为若干个规模较小、相互独立、与原问题类型相同或相似的子问题；（2）求解：若子问题缩小到容易解决的规模，则直接求解，否则递归地求解子问题；（3）合并：将各个子问题的解合并为原问题的解。10.1分治策略10.1.2算法设计步骤和程序模式图10-1分治策略示意图第4页/共67页【例10-1】矩阵乘积问题。因为矩阵可以方便地 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 示两个集合中元素之间的关系，所以被用于通信网络和交通运输系统等模型，在这些模型中经常用到矩阵的乘法。根据矩阵乘积的定义，两个n阶矩阵乘积的时间复杂度为O(n3)。Strassen根据分治策略设计矩阵乘积的算法，降低时间复杂度。假设n为2的整数幂，A、B、C都是n阶的矩阵，每个矩阵可以分解成4个n/2阶的矩阵。Strassen计算如下7个矩阵。10.1分治策略10.1.3分治策略应用实例第5页/共67页Strassen计算如下7个矩阵。最后，矩阵乘积的结果由7个矩阵得出。10.1分治策略10.1.3分治策略应用实例第6页/共67页 分析 定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析 ：按照矩阵的定义，两个n阶矩阵乘积中有n2个元素，计算每个元素需要n次乘法和(n-1)次加法，所以需要n3次乘法和n2(n-1)次加法，其时间复杂度为O(n3)，而通过分治策略设计的矩阵乘积算法可以降低时间复杂度为O(n2.81)。10.1分治策略10.1.3分治策略应用实例第7页/共67页【例10-2】计算一个数列的逆序数量。例如，已知一个数列3、1、2、5、4，则其中存在三个逆序：（3，1），（3，2），（5，4），如图10-2所示。穷举法的用时为O(n2)，而采用分治策略设计的算法时间复杂度为O(nlogn)。采用分治策略计算逆序数量的基本思想：假设数列保存在数组a中，将数组a中的元素划分成大致相等的前后两部分a1和a2，然后分别计算a1和a2中逆序的数量，最后计算逆序对（ai,aj）的数量，其中ai是a1中的元素，aj是a2中的元素。10.1分治策略10.1.3分治策略应用实例第8页/共67页10.2贪心策略贪心策略是比较容易的算法设计策略，虽然它看上去既直观又简单，但是它却可以广泛地应用于很多问题的求解，如最短路径问题、最小生成树、Huffman编码、作业调度问题等。本节主要介绍贪心策略的基本知识，然后给出了贪心策略应用实例。第9页/共67页10.2贪心策略10.2.1最优化问题与最优化原理10.2.3　算法设计步骤及程序模式10.2.2　贪心策略概述10.2.4　贪心策略应用实例第10页/共67页1.最优化问题最优化问题是在满足一定的限制条件下，对于一个给定的优化函数，寻找一组参数值，使得函数值最大或最小。每个最优化问题都包含一组限制条件和一个优化函数，符合限制条件的求解方案称为可行解，使优化函数取得最大（小）值的可行解称为最优解。10.2贪心策略10.2.1最优化问题与最优化原理第11页/共67页建运动场的问题可以抽象为最优化问题：（1）限制条件是建筑材料为300米。设x和y分别是矩形的长和宽，限制条件为：x+2y<=300，x>0，y>0。（2）代表问题解的优劣是矩形面积，即优化函数表示：f(x,y)=xy。任何一组满足限制条件“x+2y<=300”的x和y都是可行解，而使“xy”最大的是最优解。10.2贪心策略10.2.1最优化问题与最优化原理图10-3拟建运动场示意图第12页/共67页2.最优化原理1951年，美国数学家R.E.Bellman等人根据多阶段决策问题的特点，提出了解决这类问题的最优化原理(Principleofoptimality)。最优化原理的数学语言描述为：假设为了解决某一优化问题，需要依次作出n个决策D1、D2、…、Dn。如果这个决策序列是最优的，那么对于任何一个整数k（1<k<n），则Dk+1、Dk+2、…、Dn也是最优的，因为不论前面k个决策是怎样的，以后的最优决策只取决于前面决策所确定的当前状态。10.2贪心策略10.2.1最优化问题与最优化原理第13页/共67页贪心策略通过一系列步骤来构造问题的解，每一步都做出当前来看最好的选择，扩展已知的部分解，直到获得问题的完整解。这种“当前来看最好的选择”的策略就是该策略名称的来源。贪心策略求解的问题一般具有以下两个重要的性质最优子结构性当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质，也称此问题满足最优化原理。问题的最优子结构性质是该问题可以用贪心策略或者动态规划策略求解的关键特征。贪心选择性若一个问题的全局最优解可以通过一系列局部最优的选择，即贪心选择来获得，则称该问题具有贪心选择性。10.2贪心策略10.2.2　贪心策略概述第14页/共67页贪心选择性可从如下三个方面来理解：可行性，即贪心选择必须满足问题的约束;局部最优性，即贪心选择是当前步骤中所有可行选择中最佳的局部选择;不变性，即一旦做出选择，在算法的后面步骤中就无法改变。10.2贪心策略10.2.2　贪心策略概述第15页/共67页总结贪心策略求解的问题需要具备两个性质：第一，最优子结构性质；第二，贪心选择性质。第一条性质是应用贪心策略的基础，而第二条性质是决定使用贪心策略的关键。具备第一条性质的问题，如果不具备贪心选择性，而是具备子问题重叠性，则考虑用动态规划策略设计算法。10.2贪心策略10.2.2　贪心策略概述第16页/共67页10.2贪心策略贪心策略的算法设计步骤一般分为四步：建立数学模型来描述问题;把求解的问题分成若干个子问题;求解子问题，得到子问题的局部最优解;通过贪心选择，扩展子问题的局部最优解，直到构成问题的完整解。10.2.3　算法设计步骤及程序模式第17页/共67页10.2贪心策略贪心策略的程序模式一般为：Greedy(C)//C是问题的输入集合，即候选集合{S={};//初始解集合为空集while(notSolution(S))//集合S没有构成问题的一个解{x=Select(C);//在候选集合C中做贪心选择ifFeasible(S,x)//判断集合S中加入x后的解是否可行{S=S+{x};C=C-{x};}}returnS;}10.2.3　算法设计步骤及程序模式第18页/共67页10.2贪心策略【例10-3】用贪心策略求解活动安排问题。设有n个活动的集合E={1,2,…,n}，其中每个活动都要求使用同一资源，而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的起始时间si和结束时间fi且si<fi。如果选择了活动i，则它在半开时间区间[si,fi)内占用资源。若区间[si,fi)与区间[sj,fj)不相交，则称活动i与活动j是相容的。也就是说，当si≥fj或sj≥fi时，活动i与活动j相容。活动安排问题就是要在所给的活动集合中选出数量最多的相容活动子集合。10.2.4　贪心策略应用实例第19页/共67页10.2贪心策略由于输入的活动是以其完成时间的非递减序排列，所以贪心算法每次总是选择具有最早完成时间的相容活动加入A中。直观上，按这种方法选择相容活动就为未安排的活动留下尽可能多的时间。也就是说，该算法的贪心选择是使剩余的可安排时间极大化，以便安排尽可能多的相容活动。贪心策略求解活动安排问题的时间复杂度为O(n)。在GreedySelector算法中，集合A用来存储所选择的活动。活动i在集合A中，当且仅当A[i]的值为true。变量j用以记录最近一次加入到A中的活动。10.2.4　贪心策略应用实例第20页/共67页10.2贪心策略【例10-5】任务调度问题。每项任务需要一个单位的工作时间，并且每项任务都有一个截止时间和奖励。如果任务在截止时间之前开始，就可以获得奖励，否则就不能获得奖励。问题是如何安排任务以获得最多的奖励。注意不需要完成所有任务。10.2.4　贪心策略应用实例第21页/共67页10.2贪心策略例如，表10-1所示的任务调度问题实例，任务1的截止时间为2指的是任务1要在时间1或者时间2开始，否则就超过截止时间。任务2的截止时间为1意味着任务2只能在时间1开始。因此，可能的任务调度有[1,3]、[2,1]、[2,3]、[3,1]、[4,1]、[4,3]。通过观察发现，一种合理的贪心选择策略如下：先按照任务的奖励从高到低排序，根据这个顺序检查每个任务，如果满足截止时间的约束就加入该任务。10.2.4　贪心策略应用实例表10-1任务调度问题实例任务截止时间奖励1230213532254140第22页/共67页10.3动态规划策略动态规划是一种求多阶段决策问题最优解的算法设计策略，是美国数学家RichardBellman在20世纪50年代发明的。动态规划策略建立在最优化原理的基础上，可以高效地解决许多用分治算法或贪心算法无法解决的问题。本节主要介绍动态规划策略的基本知识，并给出了动态规划策略应用实例。第23页/共67页10.3动态规划策略10.3.1概述10.3.3　算法设计步骤及程序模式10.3.2　动态规划策略的相关概念10.3.4　动态规划策略应用实例第24页/共67页10.3动态规划策略动态规划的基本思想把将待求解问题分解成一系列子问题，然后求解每个子问题仅一次，并将其结果保存在一个表中，以后用到时直接存取，避免重复计算。动态规划求解的问题要具有如下性质：最优子结构性:动态规划策略与贪心策略一样，要求问题具有最优子结构性，即问题的最优解包含其子问题的最优解。子问题重叠性:如果问题在求解过程中，很多子问题的解被多次使用，就称该问题具有子问题重叠性。10.3.1概述第25页/共67页10.3动态规划策略子问题重叠性10.3.1概述第26页/共67页10.3动态规划策略动态规划策略和贪心策略动态规划策略和贪心策略都是一种递推算法，即由局部最优解来推导全局最优解。贪心算法中做出的每步贪心决策都无法改变，因为贪心策略是由上一步的最优解推导下一步的最优解，而上一步之前的最优解则不作保留。贪心策略要求每一步的最优解一定包含上一步的最优解。动态规划策略全局最优解中一定包含某个局部最优解，但不一定包含前一个局部最优解，因此需要记录之前的所有最优解。10.3.1概述第27页/共67页10.3动态规划策略【0-1背包问题】：给定n种物品和一个背包。物品i的重量是wi，其价值为vi，背包的容量为c。问应如何选择装入背包中的物品，使其总价值最大？注意：在选择装入背包的物品时，对每种物品i只有两种选择，即装入背包或不装入背包。不能将物品i装入背包多次，也不能只装入物品i的一部分。【背包问题】：与0-1背包问题类似，所不同的是在选择物品装入背包时，可以选择物品的一部分，而不一定要全部装入背包。两个问题相似，但背包问题可以用贪心算法求解，而0-1背包问题却不能。10.3.1概述第28页/共67页10.3动态规划策略【最短路径问题】:假设寻找图10-5中从A到D的最短路径，因为从A到D的最短路径一定会经过B和C，而A到B的最短距离是1，B到C的最短距离是2，C到D的最短距离是1，所以从A到D的最短距离是1+2+1=4。此时，贪心策略可以解决该问题。10.3.1概述图10-5适用贪心策略的最短路径问题第29页/共67页10.3动态规划策略如果使用贪心策略寻找图10-6中从A到D的最短路径，从A出发后选择B1，因为从A到B1的距离比到B2短，在选择B1之后，接着选择C3，最后选择D。此条路径的长度是12+11+17=40，这不是最短路径，最短路径应是A->B1->C1->D，其距离是12+13+11=36。此时，贪心策略就不能解决该问题了。10.3.1概述图10-6贪心策略不适用的问题第30页/共67页10.3动态规划策略多阶段决策问题如果一类活动过程可以分为若干个互相联系的阶段，在每一个阶段都需做出决策(采取措施)，一个阶段的决策确定以后，常常影响到下一个阶段的决策，从而就完全确定了一个过程的活动路线，则称它为多阶段决策问题。最优策略对于多阶段决策问题，各个阶段的决策构成一个决策序列，称为一个策略。策略不同，效果也不同，多阶段决策问题，就是要在可以选择的那些策略中间，选取一个最优策略，使其在预定的 标准 excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载 下达到最好的效果。动态规划的本质动态规划本质上是多阶段决策过程。将问题的过程分成几个相互联系的阶段，从而把一个大问题转化成一组同类型的子问题，然后逐个求解。10.3.2　动态规划策略的相关概念第31页/共67页10.3动态规划策略动态规划的基本术语阶段与阶段变量：把一个问题的过程恰当地分为若干个相互联系的阶段，以便按一定的次序去求解。阶段是按问题的时间或空间的自然特征来划分的，把描述阶段的变量称为阶段变量（使用字母k表示），阶段变量可以是年、月、日、路段等。用动态规划方法解题，原问题必须能划分为若干阶段。状态、状态变量与状态允许集合：状态表示每个阶段开始所处的自然状况或客观条件，通常一个阶段有若干个状态，描述过程状态的变量称为状态变量，常用sk表示第k阶段的状态变量，状态变量sk的取值集合称为允许状态集合，用Sk表示。在动态规划问题中，状态是划分阶段的依据，状态的变化就意味着阶段的推移。因此，解题时首先应明确每一阶段开始时的一切可能状态。决策、决策变量和决策允许集合：表示当过程处于某一阶段的某个状态时，可以作出不同的决定，从而确定下一阶段的状态，这种决定称为决策。描述决策的变量，称为决策变量，使用uk(sk)表示第k阶段当状态为sk时的决策变量。在实际问题中，决策变量的取值往往限制在一定范围内，此范围称为允许决策集合。使用Dk(sk)表示第k阶段从状态sk出发的允许决策集合，则有uk(sk)Dk(sk)。10.3.2　动态规划策略的相关概念第32页/共67页10.3动态规划策略动态规划的基本术语状态转移方程：是确定过程由一个状态到另一个状态的演变过程，描述了状态转移规律。给定k阶段状态变量的值后，如果这一阶段的决策变量一经确定，第k+1阶段的状态变量也就完全确定。指标函数和最优值函数：用于衡量所选定策略优劣的数量指标称为指标函数，最优指标函数记为fk(sk)，它表示从第k段状态sk采用最优策略到过程终止时的最佳效益。10.3.2　动态规划策略的相关概念第33页/共67页10.3动态规划策略动态规划策略的算法设计步骤一般分为五步建立数学模型描述问题划分阶段，选择状态，注意阶段一定要是有序的确定决策，并写出状态转移方程根据指标函数和最优值函数，写出递推方程，包括边界条件计算最优值的信息。如果需要，构造问题的最优解10.3.3　算法设计步骤及程序模式第34页/共67页10.3动态规划策略【例10-7】使用动态规划策略求解图10-6的最短路径问题。10.3.4　动态规划策略应用实例第35页/共67页10.3动态规划策略把从A到D的全过程分成3个阶段，用k表示阶段变量，表10-4是各阶段的初始状态和可供选择的道路。其中，可供选择的道路描述了状态转移情况。10.3.4　动态规划策略应用实例表10-4阶段划分阶段k初始状态可选择道路k=1AAB1、AB2k=2B1B1C1、B1C2、B1C3B2B2C1、B2C2、B2C3k=3C1C1DC2C2DC3C3D第36页/共67页10.3动态规划策略用dk(xk，xk+1)表示在第k阶段由初始状态xk到下阶段的初始状态xk+1的路径距离。fk(xk)表示从第k阶段的xk到终点D的最短距离。则最优指标函数为：10.3.4　动态规划策略应用实例第37页/共67页10.3动态规划策略10.3.4　动态规划策略应用实例第38页/共67页10.3动态规划策略【例10-8】0-1背包问题：已知有n个物品和一个背包，物品i的重量是wi，价值为vi，背包的容量为c。物品i只能放入包中，或者留在包外，不能部分和多次放入包中。问题是在选择的物品总重量不超过c的条件下，获得最大的价值。把对每件物品的取舍作为一个阶段，那么选择物品的过程分成n个阶段。决策变量uk表示第k个物品是否被选择。如果物品i被选择，uk=1，否则uk=0。如果物品1被选择（u1=1），那么原问题变成有n-1个物品、背包容量为c-w1的背包问题。在做出u1、u2、…、ui个决策后，问题简化为只需n-i次决策、背包容量为的问题。因此，无论决策变量u1、u2、…、ui是多少，剩余的决策一定是简化后的背包问题的最优解，故0-1背包问题具有最优子结构性质。10.3.4　动态规划策略应用实例第39页/共67页10.3动态规划策略如果考虑只能选择前i个物品（）、背包容量为j（）的简化背包问题，设m(i,j)为该简化问题的最优解，即能够放进容量为j背包中，前i个物品的最大价值子集。放进容量为j背包中前i个物品的子集可以根据是否包括第i个物品分成两种情况：第一、子集中不包括第i个物品；第二、子集中包括第i个物品。分情况得到如下结论：如果子集不包括第i个物品，则最优子集的价值为m(i-1,j)。如果子集中包括第i个物品，则最优子集的价值为vi+m(i-1,j-wi)，即最优子集是由第i个物品和前i-1个能够放进容量为j-wi的背包最优子集构成。因此，前i个物品中最优子集的总价值等于两种情况下子集价值中的较大者。10.3.4　动态规划策略应用实例第40页/共67页10.3动态规划策略0-1背包问题的递归方程10.3.4　动态规划策略应用实例第41页/共67页10.4回溯策略本节和下一节将介绍两种算法设计策略：回溯策略和分支界限策略。这两种策略都可以看作是对穷举法的改进，用于求解某些组合问题。“回溯”这个术语最早由D.H.Lehmer在20世纪50年代提出。R.J.Walker是回溯策略的早期研究者之一，在1960年给出了回溯算法的描述。后来，S.Golomb和L.Baumert给出回溯策略的基本描述以及各种应用。本节主要介绍回溯策略的基本知识，并给出了回溯策略的应用实例。第42页/共67页10.4回溯策略10.4.1概述10.4.2　回溯策略算法设计步骤及程序模式10.4.3　回溯策略应用实例第43页/共67页10.4回溯策略通过搜索问题的所有候选解以找到问题的解的方法称为搜索法，也称为枚举法。当一个问题的所有候选解数量有限，或只需要检查部分候选解就可以找到问题的解时，搜索法是可行的。但由于实际问题候选解的数量往往很大，计算机搜索候选解的时间会很长，所以，搜索法在实际应用中很少使用。回溯策略是一种选优搜索法，通过对候选解进行系统的搜索，使问题的求解时间大大减少，同时保证在算法运行结束时能够找到所需要的解。10.4.1概述第44页/共67页10.4回溯策略回溯法的基本思想是在搜索过程中，当探索到某一步时，发现原先的选择不是最优或达不到目标，就退回到上一步重新选择。回溯法主要用来解决一些要经过许多步骤才能完成、并且每一步都有若干种可能的分支的问题。若问题的解需要穷举搜索大量、有限的可能解空间才能获取，那么该问题被称为组合问题。回溯策略求解的问题一般是困难的组合问题，这些问题可能存在精确解，但是无法用高效的算法求解。另外，组合问题的解空间一般可以组织成一个树，即问题的搜索树。如果一个问题的解空间可以用树表示，则可以使用回溯策略求解。10.4.1概述第45页/共67页10.4回溯策略回溯策略的算法设计步骤一般分为五步：建立数学模型描述问题；定义问题的解空间，它包含问题的所有可能解；把问题的解空间组织成树结构；以深度优先的方式搜索树结构的解空间，并在搜索的过程中判断是否满足约束条件；输出问题的解。如果需要，构造问题的解。10.4.2　回溯策略算法设计步骤及程序模式第46页/共67页10.4回溯策略回溯策略的程序根据实现方法可以分成递归和迭代两种。递归回溯策略的程序模式如下：10.4.2　回溯策略算法设计步骤及程序模式第47页/共67页10.4回溯策略迭代回溯策略的程序模式如下：10.4.2　回溯策略算法设计步骤及程序模式第48页/共67页10.4回溯策略【例10-10】使用回溯策略求解n皇后问题。已知一个的棋盘，寻找所有能够使得n个皇后没有冲突的方案，即不能将两个皇后置于同一行、列或者斜线上。假设n=4时，就是一个的棋盘，每一行中有4个位置，每行只能有一个皇后，这样就有44种布局。每种布局可以用向量<x1,x2,x3,x4>表示，其中xi表示第i行放置皇后的列号。当第i行中还没有放置皇后，则xi=0。例如，向量<1,3,2,4>对应的布局如图10-7所示。实际上，由于两个皇后不能在同一列，所以任何一个没有冲突的布局方案都对应于1、2、3、4的一个排列。10.4.3　回溯策略应用实例图10-7四皇后问题的一个布局第49页/共67页10.4回溯策略为了使用回溯策略解决n皇后问题，将问题的解空间组织成一棵完全n叉树，然后以深度优先方式搜索。根节点表示没有放置皇后，因为第一行皇后有4个位置可以放置，所以根节点下有四个分支，分别对应x1=1，2，3，4，即把皇后放置在第一行的第1，2，3，4列中，如图10-8所示。每放置完一个皇后，由于约束条件的限制，以后的搜索空间大幅缩减。回溯策略会找出n皇后问题的所有可行解。10.4.3　回溯策略应用实例图10-8四皇后问题的解空间树结构第50页/共67页10.5分支限界策略分支限界策略是一个用途十分广泛的算法设计策略，由RichardManningKarp在20世纪60年代发明，成功求解含有65个城市的旅行商问题。分支限界法被用于解决各种各样的优化问题。比如，作业调度问题、分配问题、网络问题、背包问题、旅行商问题。本节主要介绍分支限界策略的基本知识，并给出了分支限界策略的应用实例。第51页/共67页10.5分支限界策略10.5.1堆10.5.3　算法设计步骤及程序模式10.5.4　分支限界策略应用实例10.5.2概述第52页/共67页10.5分支限界策略因为分支限界策略经常使用堆，所有这里先简单回顾一下7.3.2节中堆的一些概念。堆分为大根堆和小根堆。对于大根堆，每个结点的键值都要大于或者等于其孩子结点的值，而对于小根堆，每个结点的键值都小于或者等于其孩子结点的值。10.5.1堆大根堆小根堆第53页/共67页10.5分支限界策略在回溯策略中，若无法从解空间树的某个分支得到解，就不会搜索这个分支。这个思想在分支限界策略中得到强化。分支限界法包括两个基本操作：分支：把全部可行的解空间不断分割为越来越小的子集；限界：为每个子集内的解的值计算一个下界或上界。10.5.2概述第54页/共67页10.5分支限界策略分支限界策略与回溯策略的共同点是需要把问题表示成解空间树，然后在树中搜索问题的解。分支限界策略与回溯策略的不同点有两个：第一，分支限界策略没有限制树的搜索方法，可以是广度优先搜索，也可以是最小成本搜索，而回溯策略采用的是深度优先搜索第二，分支限界策略只能用于优化问题，而回溯策略可以用于非优化问题，例如求问题的可行解10.5.2概述第55页/共67页10.5分支限界策略分支限界策略在设计算法时需要两个额外的条件第一，为解空间树中的每个结点提供一种计算其边界的方法；第二，求出目前最优解的值。如果一个结点的边界值不满足当前最优解值的范围，就停止搜索这个结点。因为从这个结点得到的解，没有一个比目前得到的最优解更好。分支限界策略通过限界的方法避免搜索更多的分支。分支限界策略求解的问题也是组合优化问题。如果一个问题的解空间可以用树表示，并且可以求出结点的边界值和目前最优解的值，则可以使用分支限界策略求解。10.5.2概述第56页/共67页10.5分支限界策略分支限界策略的算法设计步骤一般以下几步建立数学模型描述问题；定义问题的解空间，它包含问题的所有可能解；把问题的解空间组织成树结构；以广度优先或最小成本的方式搜索树结构的解空间，并在搜索的过程中计算当前最优解的值和每个分支出来的结点的边界值；输出问题的解。如果需要，构造问题的解。10.5.3　算法设计步骤及程序模式第57页/共67页10.5分支限界策略【例10-12】使用分支限界策略求解任务分配问题。任务分配问题是把n项任务分配给n个人，每个人完成每项任务的所需要的时间不同，一般用n阶矩阵表示。要求分配给每个人一项任务，使完成n项任务的总时间最少。把不同的任务分配给不同的人，就出现了很多不同的组合，求完成所有任务总时间最少的任务分配，这是一个组合优化问题。10.5.4　分支限界策略应用实例第58页/共67页10.5分支限界策略如何构造任务分配问题的解空间树？方法是把树中的每一层对应着一项任务的分配，该层的每个结点对应一项任务被分配给不同的人员，如图10-12所示例如，图10-12中的矩阵C是四位人员完成四项任务所用的时间表，当任务都没有分配时，四项任务的总完成时间不会小于矩阵C每一列中最小元素的和，即5+2+1+4=12。10.5.4　分支限界策略应用实例第59页/共67页10.5分支限界策略10.5.4　分支限界策略应用实例第60页/共67页10.5分支限界策略【例10-13】使用分支限界策略求解0-1背包问题。已知有n个物品和一个背包，物品i的重量是wi，价值为pi，背包的容量为W。物品i只能放入包中，或者留在包外，不能部分和多次放入包中。问题是在选择的物品总重量不超过W的条件下，获得最大的价值。10.5.4　分支限界策略应用实例第61页/共67页10.5分支限界策略在10.3节，使用动态规划策略求解过该问题。现在，使用分支限界策略求解该问题。可以使用一棵二叉树来构造0-1背包问题的解空间树，树中每层对应一件物品的选择，左边的结点表示包括该物品，右边的结点表示不包括该物品。0-1背包问题的边界函数定义为已经选择物品的总价值，加上背包剩余容量与剩下物品的最大单位价值的乘积。10.5.4　分支限界策略应用实例第62页/共67页10.5分支限界策略例如，对于表10-5的背包问题实例，背包的容量为10，那么使用分支限界法求解背包问题实例的解空间树如图10-14所示，根据边界函数可以计算每个结点的上限值。10.5.4　分支限界策略应用实例表10-5一个背包问题实例的物品重量和价值，按照单位重量的价值降序排列物品编号重量价值价值/重量144010274263525543124第63页/共67页10.5分支限界策略10.5.4　分支限界策略应用实例图10-12使用分支限界法求解0-1背包问题实例的解空间树第64页/共67页本章小结本章介绍五种算法设计策略和其应用实例，这些策略包括分治策略、贪心策略、动态规划策略、回溯策略和分支限界策略。通过对每种算法设计策略的基本设计步骤和设计模式的说明，使读者对算法设计策略的知识和应用有了直观的认识和全面的理解。通过本章的学习，读者应熟悉每种算法设计策略的适用条件，并能使用各种算法设计策略，根据实际问题设计程序解决问题。第65页/共67页ThankYou!第66页/共67页