《数据结构与算法10剖析优秀PPT.ppt》由会员分享，可在线阅读，更多相关《数据结构与算法10剖析优秀PPT.ppt（67页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第10章 算法设计策略及应用实例（4课时）本章介绍了算法设计策略和应用实例，主要目的有两个:首先，让读者知道每种算法的适用条件，即何时可以使用和何时不能使用某种算法设计策略；其次，让读者学习基本的算法设计策略，即掌握如何描述自己的问题和高效、快速地解决问题。本章将进一步介绍五种常用算法设计策略的基本思想和实现方法，这些策略包括分治策略、贪心策略、动态规划策略、回溯策略和分支限界策略，以及它们的具体应用实例。10.1 分治策略分治策略10.1.1 概述概述10.1.2 算法设计步骤和程序模式算法设计步骤和程序模式10.1.3 分治策略应用实例分治策略应用实例 分治策略是一类算法设计策略，它将原问
2、题分解成若干部分，从而产生若干子问题，这些子问题相互独立且与原问题类型相同，然后解决这些子问题，最终把这些子问题的解合并成原问题的解。分治策略所能解决的问题，一般具有以下三个特征：原问题可以分解成规模较小、相互独立和类型相同的子问题；子问题的规模缩小到确定的程度，就不须要再分解，可以很简洁地求解；全部子问题的解能够合并成原问题的解。10.1 10.1 分治策略分治策略分治策略分治策略10.1.1 概述概述如图10-1所示，接受分治策略的算法设计都包括分解、求解和合并三个步骤：（1）分解：将原问题分解为若干个规模较小、相互独立、与原问题类型相同或相像的子问题；（2）求解：若子问题缩小到简洁解决的
3、规模，则干脆求解，否则递归地求解子问题；（3）合并：将各个子问题的解合并为原问题的解。10.1 分治策略分治策略10.1.2 算法设计步骤和程序模式算法设计步骤和程序模式图10-1 分治策略示意图【例10-1】矩阵乘积问题。因为矩阵可以便利地表示两个集合中元素之间的关系，所以被用于通信网络和交通运输系统等模型，在这些模型中常常用到矩阵的乘法。依据矩阵乘积的定义，两个n阶矩阵乘积的时间困难度为O(n3)。Strassen依据分治策略设计矩阵乘积的算法，降低时间困难度。假设n为2的整数幂，A、B、C都是n阶的矩阵，每个矩阵可以分解成4个n/2阶的矩阵。Strassen计算如下7个矩阵。10.1 分
4、治策略分治策略10.1.3 分治策略应用实例分治策略应用实例Strassen计算如下7个矩阵。最终，矩阵乘积的结果由7个矩阵得出。10.1 分治策略分治策略10.1.3 分治策略应用实例分治策略应用实例分析：依据矩阵的定义，两个n阶矩阵乘积中有n2个元素，计算每个元素须要n次乘法和(n-1)次加法，所以须要n3次乘法和n2(n-1)次加法，其时间困难度为O(n3)，而通过分治策略设计的矩阵乘积算法可以降低时间困难度为O(n2.81)。10.1 分治策略分治策略10.1.3 分治策略应用实例分治策略应用实例【例10-2】计算一个数列的逆序数量。例如，已知一个数列3、1、2、5、4，则其中存在三个
5、逆序：（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 分治策略应用实例分治策略应用实例10.2 贪心策略贪心策略贪心策略是比较容易的算法设计策略，虽然它看上去既直观又简单，但是它却可以广泛地应用于很多问题的求解，如最短路径问题、最小生成树、Hu
6、ffman编码、作业调度问题等。本节主要介绍贪心策略的基本知识，然后给出了贪心策略应用实例。10.2 贪心策略贪心策略10.2.1 最优化问题与最优化原理最优化问题与最优化原理10.2.3算法设计步骤及程序模式算法设计步骤及程序模式10.2.2贪心策略概述贪心策略概述10.2.4贪心策略应用实例贪心策略应用实例1.最优化问题最优化问题最优化问题是在满足确定的限制条件下，对于一个给定的优最优化问题是在满足确定的限制条件下，对于一个给定的优化函数，找寻一组参数值，使得函数值最大或最小。每个最优化问化函数，找寻一组参数值，使得函数值最大或最小。每个最优化问题都包含一组限制条件和一个优化函数，符合限制
7、条件的求解方案题都包含一组限制条件和一个优化函数，符合限制条件的求解方案称为可行解，使优化函数取得最大（小）值的可行解称为最优解。称为可行解，使优化函数取得最大（小）值的可行解称为最优解。10.2 10.2 贪心策略贪心策略贪心策略贪心策略10.2.1 最优化问题与最优化原理最优化问题与最优化原理 建运动场的问题可以抽象为最优化问题：（1）限制条件是建筑材料为300米。设x和y分别是矩形的长和宽，限制条件为：x+2y0，y0。（2）代表问题解的优劣是矩形面积，即优化函数表示：f(x,y)=xy。任何一组满足限制条件“x+2y=300”的x和y都是可行解，而使“xy”最大的是最优解。10.2 1
8、0.2 贪心策略贪心策略贪心策略贪心策略10.2.1 最优化问题与最优化原理最优化问题与最优化原理n图10-3 拟建运动场示意图 2.2.最优化原理最优化原理 1951 1951年，美国数学家年，美国数学家R.E.BellmanR.E.Bellman等人依据多阶段决策问题的特点，提出等人依据多阶段决策问题的特点，提出了解决这类问题的最优化原理了解决这类问题的最优化原理(Principle of optimality)(Principle of optimality)。最优化原理的数学语言描述为：假设为了解决某一优化问题，须要依次作最优化原理的数学语言描述为：假设为了解决某一优化问题，须要依次作
9、出出n n个决策个决策D1D1、D2D2、DnDn。假如这个决策序列是最优的，那么对于任何一个。假如这个决策序列是最优的，那么对于任何一个整数整数k k（1 k n1 k n），则），则Dk+1Dk+1、Dk+2Dk+2、DnDn也是最优的，因为不论前面也是最优的，因为不论前面k k个个决策是怎样的，以后的最优决策只取决于前面决策所确定的当前状态。决策是怎样的，以后的最优决策只取决于前面决策所确定的当前状态。10.2 10.2 贪心策略贪心策略贪心策略贪心策略10.2.1 最优化问题与最优化原理最优化问题与最优化原理 贪心策略通过一系列步骤来构造问题的解，每一步都做出当前来看最好的选择，扩展已
10、知的部分解，直到获得问题的完整解。这种“当前来看最好的选择”的策略就是该策略名称的来源。贪心策略求解的问题一般具有以下两个重要的性质最优子结构性当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质，也称此问题满足最优化原理。问题的最优子结构性质是该问题可以用贪心策略或者动态规划策略求解的关键特征。贪心选择性若一个问题的全局最优解可以通过一系列局部最优的选择，即贪心选择来获得，则称该问题具有贪心选择性。10.2 贪心策略贪心策略10.2.2贪心策略概述贪心策略概述 贪心选择性可从如下三个方面来理解：可行性，即贪心选择必需满足问题的约束;局部最优性，即贪心选择是当前步骤中全部可行选
11、择中最佳的局部选择;不变性，即一旦做出选择，在算法的后面步骤中就无法变更。10.2 贪心策略贪心策略10.2.2贪心策略概述贪心策略概述n总结n 贪心策略求解的问题须要具备两特性质：n 第一，最优子结构性质；n 其次，贪心选择性质。n 第一条性质是应用贪心策略的基础，而其次条性质是确定运用贪心策略的关键。具备第一条性质的问题，假如不具备贪心选择性，而是具备子问题重叠性，则考虑用动态规划策略设计算法。10.2 贪心策略贪心策略10.2.2贪心策略概述贪心策略概述10.2 贪心策略贪心策略n贪心策略的算法设计步骤一般分为四步：n建立数学模型来描述问题;n把求解的问题分成若干个子问题;n求解子问题，
12、得到子问题的局部最优解;n通过贪心选择，扩展子问题的局部最优解，直到构成问题的完整解。10.2.3算法设计步骤及程序模式算法设计步骤及程序模式10.2 贪心策略贪心策略贪心策略的程序模式一般为：贪心策略的程序模式一般为：Greedy(C)/CGreedy(C)/C是问题的输入集合，即候选集合是问题的输入集合，即候选集合 S=;S=;/初始解集合为空集初始解集合为空集while(not Solution(S)while(not Solution(S)/集合集合S S没有构成问题的一个解没有构成问题的一个解 x=Select(C);/x=Select(C);/在候选集合在候选集合C C中做贪心选择
13、中做贪心选择if Feasible(S,x)/if Feasible(S,x)/推断集合推断集合S S中加入中加入x x后的解是否可行后的解是否可行 S=S+x;S=S+x;C=C-x;C=C-x;return S;return S;10.2.3算法设计步骤及程序模式算法设计步骤及程序模式10.2 贪心策略贪心策略 【例10-3】用贪心策略求解活动支配问题。设有n个活动的集合E=1,2,n，其中每个活动都要求运用同一资源，而在同一时间内只有一个活动能运用这一资源。每个活动i都有一个要求运用该资源的起始时间si 和结束时间fi 且si B1-C1-D，其距离是12+13+11=36。此时，贪心策
14、略就不能解决该问题了。10.3.1 概述概述图10-6 贪心策略不适用的问题10.3 10.3 动态规划策略动态规划策略动态规划策略动态规划策略n多阶段决策问题多阶段决策问题n假如一类活动过程可以分为若干个相互联系的阶段，在每一个阶段都需做出决策假如一类活动过程可以分为若干个相互联系的阶段，在每一个阶段都需做出决策(实实行措施行措施)，一个阶段的决策确定以后，常常影响到下一个阶段的决策，从而就完全确定，一个阶段的决策确定以后，常常影响到下一个阶段的决策，从而就完全确定了一个过程的活动路途，则称它为多阶段决策问题。了一个过程的活动路途，则称它为多阶段决策问题。n最优策略最优策略n对于多阶段决策问
15、题，各个阶段的决策构成一个决策序列，称为一个策略。策略不同，对于多阶段决策问题，各个阶段的决策构成一个决策序列，称为一个策略。策略不同，效果也不同，多阶段决策问题，就是要在可以选择的那些策略中间，选取一个最优策略，效果也不同，多阶段决策问题，就是要在可以选择的那些策略中间，选取一个最优策略，使其在预定的标准下达到最好的效果。使其在预定的标准下达到最好的效果。n动态规划的本质动态规划的本质n动态规划本质上是多阶段决策过程。将问题的过程分成几个相互联系的阶段，从而把动态规划本质上是多阶段决策过程。将问题的过程分成几个相互联系的阶段，从而把一个大问题转化成一组同类型的子问题，然后逐个求解。一个大问题
16、转化成一组同类型的子问题，然后逐个求解。10.3.2动态规划策略的相关概念动态规划策略的相关概念10.3 10.3 动态规划策略动态规划策略动态规划策略动态规划策略n动态规划的基本术语动态规划的基本术语n阶段与阶段变量：把一个问题的过程恰当地分为若干个相互联系的阶段，以便按确定的阶段与阶段变量：把一个问题的过程恰当地分为若干个相互联系的阶段，以便按确定的次序去求解。阶段是按问题的时间或空间的自然特征来划分的，把描述阶段的变量称为阶次序去求解。阶段是按问题的时间或空间的自然特征来划分的，把描述阶段的变量称为阶段变量（运用字母段变量（运用字母k表示），阶段变量可以是年、月、日、路段等。用动态规划方
17、法解题，表示），阶段变量可以是年、月、日、路段等。用动态规划方法解题，原问题必需能划分为若干阶段。原问题必需能划分为若干阶段。n状态、状态变量与状态允许集合：状态表示每个阶段起先所处的自然状况或客观条件，状态、状态变量与状态允许集合：状态表示每个阶段起先所处的自然状况或客观条件，通常一个阶段有若干个状态，描述过程状态的变量称为状态变量，常用通常一个阶段有若干个状态，描述过程状态的变量称为状态变量，常用sk表示第表示第k阶段的状阶段的状态变量，状态变量态变量，状态变量sk的取值集合称为允许状态集合，用的取值集合称为允许状态集合，用Sk表示。在动态规划问题中，状态表示。在动态规划问题中，状态是划分
18、阶段的依据，状态的变更就意味着阶段的推移。因此，解题时首先应明确每一阶段是划分阶段的依据，状态的变更就意味着阶段的推移。因此，解题时首先应明确每一阶段起先时的一切可能状态。起先时的一切可能状态。n决策、决策变量和决策允许集合：表示当过程处于某一阶段的某个状态时，可以作出不决策、决策变量和决策允许集合：表示当过程处于某一阶段的某个状态时，可以作出不同的确定，从而确定下一阶段的状态，这种确定称为决策。描述决策的变量，称为决策变同的确定，从而确定下一阶段的状态，这种确定称为决策。描述决策的变量，称为决策变量，运用量，运用uk(sk)表示第表示第k阶段当状态为阶段当状态为sk时的决策变量。在实际问题中
19、，决策变量的取值往时的决策变量。在实际问题中，决策变量的取值往往限制在确定范围内，此范围称为允许决策集合。运用往限制在确定范围内，此范围称为允许决策集合。运用Dk(sk)表示第表示第k阶段从状态阶段从状态sk动身的动身的允许决策集合，则有允许决策集合，则有uk(sk)Dk(sk)。10.3.2动态规划策略的相关概念动态规划策略的相关概念10.3 10.3 动态规划策略动态规划策略动态规划策略动态规划策略n动态规划的基本术语动态规划的基本术语n状态转移方程：是确定过程由一个状态到另一个状态的演化过程，描述了状态状态转移方程：是确定过程由一个状态到另一个状态的演化过程，描述了状态转移规律。给定转移
20、规律。给定k阶段状态变量的值后，假如这一阶段的决策变量一经确定，第阶段状态变量的值后，假如这一阶段的决策变量一经确定，第k+1阶段的状态变量也就完全确定。阶段的状态变量也就完全确定。n指标函数和最优值函数：用于衡量所选定策略优劣的数量指标称为指标函数，指标函数和最优值函数：用于衡量所选定策略优劣的数量指标称为指标函数，最优指标函数记为最优指标函数记为fk(sk)，它表示从第，它表示从第k段状态段状态sk接受最优策略到过程终止时的接受最优策略到过程终止时的最佳效益。最佳效益。10.3.2动态规划策略的相关概念动态规划策略的相关概念10.3 10.3 动态规划策略动态规划策略动态规划策略动态规划策
21、略n动态规划策略的算法设计步骤一般分为五步动态规划策略的算法设计步骤一般分为五步n建立数学模型描述问题建立数学模型描述问题n划分阶段，选择状态，留意阶段确定要是有序的划分阶段，选择状态，留意阶段确定要是有序的n确定决策，并写出状态转移方程确定决策，并写出状态转移方程n依据指标函数和最优值函数，写出递推方程，包括边界条件依据指标函数和最优值函数，写出递推方程，包括边界条件n计算最优值的信息。假如须要，构造问题的最优解计算最优值的信息。假如须要，构造问题的最优解10.3.3算法设计步骤及程序模式算法设计步骤及程序模式10.3 10.3 动态规划策略动态规划策略动态规划策略动态规划策略 【例10-7
22、】运用动态规划策略求解图10-6的最短路径问题。10.3.4动态规划策略应用实例动态规划策略应用实例10.3 10.3 动态规划策略动态规划策略动态规划策略动态规划策略 把从A到D的全过程分成3个阶段，用k表示阶段变量，表10-4是各阶段的初始状态和可供选择的道路。其中，可供选择的道路描述了状态转移状况。10.3.4动态规划策略应用实例动态规划策略应用实例表10-4 阶段划分阶段k初始状态可选择道路k=1AAB1、AB2k=2B1B1C1、B1C2、B1C3B2B2C1、B2C2、B2C3k=3C1C1DC2C2DC3C3D10.3 10.3 动态规划策略动态规划策略动态规划策略动态规划策略
23、用dk(xk，xk+1)表示在第k阶段由初始状态xk到下阶段的初始状态xk+1的路径距离。fk(xk)表示从第k阶段的xk到终点D的最短距离。则最优指标函数为：10.3.4动态规划策略应用实例动态规划策略应用实例10.3 10.3 动态规划策略动态规划策略动态规划策略动态规划策略10.3.4动态规划策略应用实例动态规划策略应用实例10.3 10.3 动态规划策略动态规划策略动态规划策略动态规划策略 【例10-8】0-1背包问题：已知有n个物品和一个背包，物品i的重量是wi，价值为vi，背包的容量为c。物品i只能放入包中，或者留在包外，不能部分和多次放入包中。问题是在选择的物品总重量不超过c的条
24、件下，获得最大的价值。把对每件物品的取舍作为一个阶段，那么选择物品的过程分成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动态规划策略应用实例动态规划策略应用实例10.3 10.3 动态规划策略动态规划策略动态规划策略动态规划策略 假如考虑只能选择前i个物
25、品（）、背包涵量为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动态规划策略应用实例动态规
26、划策略应用实例10.3 10.3 动态规划策略动态规划策略动态规划策略动态规划策略 0-1背包问题的递归方程背包问题的递归方程10.3.4动态规划策略应用实例动态规划策略应用实例10.4 回溯策略回溯策略 本节和下一节将介绍两种算法设计策略：回溯策略和分支界限策略。这两种策略都可以看作是对穷举法的改进，用于求解某些组合问题。“回溯”这个术语最早由D.H.Lehmer在20世纪50年代提出。R.J.Walker是回溯策略的早期研究者之一，在1960年给出了回溯算法的描述。后来，S.Golomb和L.Baumert给出回溯策略的基本描述以及各种应用。本节主要介绍回溯策略的基本知识，并给出了回溯策略
27、的应用实例。10.4 回溯策略回溯策略10.4.1 概述概述10.4.2回溯策略算法设计步骤及程序模式回溯策略算法设计步骤及程序模式10.4.3回溯策略应用实例回溯策略应用实例10.4 10.4 回溯策略回溯策略回溯策略回溯策略 通过搜寻问题的全部候选解以找到问题的解的方法称为搜寻法，也称为枚举法。当一个问题的全部候选解数量有限，或只须要检查部分候选解就可以找到问题的解时，搜寻法是可行的。但由于实际问题候选解的数量往往很大，计算机搜寻候选解的时间会很长，所以，搜寻法在实际应用中很少运用。回溯策略是一种选优搜寻法，通过对候选解进行系统的搜寻，使问题的求解时间大大削减，同时保证在算法运行结束时能够
28、找到所须要的解。10.4.1 概述概述10.4 10.4 回溯策略回溯策略回溯策略回溯策略n回溯法的基本思想是n在搜寻过程中，当探究到某一步时，发觉原先的选择不是最优或达不到目标，就退回到上一步重新选择。回溯法主要用来解决一些要经过很多步骤才能完成、并且每一步都有若干种可能的分支的问题。n若问题的解须要穷举搜寻大量、有限的可能解空间才能获得，那么该问题被称为组合问题。回溯策略求解的问题一般是困难的组合问题，这些问题可能存在精确解，但是无法用高效的算法求解。另外，组合问题的解空间一般可以组织成一个树，即问题的搜寻树。假如一个问题的解空间可以用树表示，则可以运用回溯策略求解。10.4.1 概述概述
29、10.4 10.4 回溯策略回溯策略回溯策略回溯策略n回溯策略的算法设计步骤一般分为五步：n建立数学模型描述问题；n定义问题的解空间，它包含问题的全部可能解；n把问题的解空间组织成树结构；n以深度优先的方式搜寻树结构的解空间，并在搜寻的过程中推断是否满足约束条件；n输出问题的解。假如须要，构造问题的解。10.4.2回溯策略算法设计步骤及程序模式回溯策略算法设计步骤及程序模式10.4 10.4 回溯策略回溯策略回溯策略回溯策略n回溯策略的程序依据实现方法可以分成递归和迭代两种。n递归回溯策略的程序模式如下：10.4.2回溯策略算法设计步骤及程序模式回溯策略算法设计步骤及程序模式10.4 10.4
30、 回溯策略回溯策略回溯策略回溯策略n迭代回溯策略的程序模式如下：10.4.2回溯策略算法设计步骤及程序模式回溯策略算法设计步骤及程序模式10.4 10.4 回溯策略回溯策略回溯策略回溯策略 【例10-10】运用回溯策略求解n皇后问题。已知一个的棋盘，找寻全部能够使得n个皇后没有冲突的方案，即不能将两个皇后置于同一行、列或者斜线上。假设n=4时，就是一个的棋盘，每一行中有4个位置，每行只能有一个皇后，这样就有44种布局。每种布局可以用向量表示，其中xi表示第i行放置皇后的列号。当第i行中还没有放置皇后，则xi=0。例如，向量对应的布局如图10-7所示。事实上，由于两个皇后不能在同一列，所以任何一
31、个没有冲突的布局方案都对应于1、2、3、4的一个排列。10.4.3回溯策略应用实例回溯策略应用实例图10-7 四皇后问题的一个布局10.4 10.4 回溯策略回溯策略回溯策略回溯策略 为了运用回溯策略解决n皇后问题，将问题的解空间组织成一棵完全n叉树，然后以深度优先方式搜寻。根节点表示没有放置皇后，因为第一行皇后有4个位置可以放置，所以根节点下有四个分支，分别对应x1=1，2，3，4，即把皇后放置在第一行的第1，2，3，4列中，如图10-8所示。每放置完一个皇后，由于约束条件的限制，以后的搜寻空间大幅缩减。回溯策略会找出n皇后问题的全部可行解。10.4.3回溯策略应用实例回溯策略应用实例图10
32、-8 四皇后问题的解空间树结构10.5 分支限界策略分支限界策略 分支限界策略是一个用途特别广泛的算法设计策略，由Richard Manning Karp在20世纪60年头独创，成功求解含有65个城市的旅行商问题。分支限界法被用于解决各种各样的优化问题。比如，作业调度问题、安排问题、网络问题、背包问题、旅行商问题。本节主要介绍分支限界策略的基本学问，并给出了分支限界策略的应用实例。10.5 分支限界策略分支限界策略10.5.1 堆堆10.5.3算法设计步骤及程序模式算法设计步骤及程序模式10.5.4分支限界策略应用实例分支限界策略应用实例10.5.2 概述概述10.5 分支限界策略分支限界策略
33、 因为分支限界策略常常运用堆，全部这里先简洁回顾一下7.3.2节中堆的一些概念。堆分为大根堆和小根堆。对于大根堆，每个结点的键值都要大于或者等于其孩子结点的值，而对于小根堆，每个结点的键值都小于或者等于其孩子结点的值。10.5.1 堆堆大根堆 小根堆 10.5 分支限界策略分支限界策略 在回溯策略中，若无法从解空间树的某个分支得到解，就不会搜寻这个分支。这个思想在分支限界策略中得到强化。分支限界法包括两个基本操作：分支：把全部可行的解空间不断分割为越来越小的子集；限界：为每个子集内的解的值计算一个下界或上界。10.5.2 概述概述10.5 分支限界策略分支限界策略 分支限界策略与回溯策略的共同
34、点是须要把问题表示成解空间树，然后在树中搜寻问题的解。分支限界策略与回溯策略的不同点有两个：第一，分支限界策略没有限制树的搜寻方法，可以是广度优先搜寻，也可以是最小成本搜寻，而回溯策略接受的是深度优先搜寻其次，分支限界策略只能用于优化问题，而回溯策略可以用于非优化问题，例如求问题的可行解10.5.2 概述概述10.5 分支限界策略分支限界策略 分支限界策略在设计算法时须要两个额外的条件第一，为解空间树中的每个结点供应一种计算其边界的方法；其次，求出目前最优解的值。假如一个结点的边界值不满足当前最优解值的范围，就停止搜寻这个结点。因为从这个结点得到的解，没有一个比目前得到的最优解更好。分支限界策
35、略通过限界的方法避开搜寻更多的分支。分支限界策略求解的问题也是组合优化问题。假如一个问题的解空间可以用树表示，并且可以求出结点的边界值和目前最优解的值，则可以运用分支限界策略求解。10.5.2 概述概述10.5 分支限界策略分支限界策略 分支限界策略的算法设计步骤一般以下几步建立数学模型描述问题；定义问题的解空间，它包含问题的全部可能解；把问题的解空间组织成树结构；以广度优先或最小成本的方式搜寻树结构的解空间，并在搜寻的过程中计算当前最优解的值和每个分支出来的结点的边界值；输出问题的解。假如须要，构造问题的解。10.5.3算法设计步骤及程序模式算法设计步骤及程序模式10.5 分支限界策略分支限
36、界策略 【例10-12】运用分支限界策略求解任务安排问题。任务安排问题是把n项任务安排给n个人，每个人完成每项任务的所须要的时间不同，一般用n阶矩阵表示。要求安排给每个人一项任务，使完成n项任务的总时间最少。把不同的任务安排给不同的人，就出现了很多不同的组合，求完成全部任务总时间最少的任务安排，这是一个组合优化问题。10.5.4分支限界策略应用实例分支限界策略应用实例10.5 分支限界策略分支限界策略 如何构造任务安排问题的解空间树？方法是把树中的每一层对应着一项任务的安排，该层的每个结点对应一项任务被安排给不同的人员，如图10-12所示 例如，图10-12中的矩阵C是四位人员完成四项任务所用
37、的时辰表，当任务都没有安排时，四项任务的总完成时间不会小于矩阵C每一列中最小元素的和，即5+2+1+4=12。10.5.4分支限界策略应用实例分支限界策略应用实例10.5 分支限界策略分支限界策略10.5.4分支限界策略应用实例分支限界策略应用实例10.5 分支限界策略分支限界策略 【例10-13】运用分支限界策略求解0-1背包问题。已知有n个物品和一个背包，物品i的重量是wi，价值为pi，背包的容量为W。物品i只能放入包中，或者留在包外，不能部分和多次放入包中。问题是在选择的物品总重量不超过W的条件下，获得最大的价值。10.5.4分支限界策略应用实例分支限界策略应用实例10.5 分支限界策略
38、分支限界策略 在10.3节，运用动态规划策略求解过该问题。现在，运用分支限界策略求解该问题。可以运用一棵二叉树来构造0-1背包问题的解空间树，树中每层对应一件物品的选择，左边的结点表示包括该物品，右边的结点表示不包括该物品。0-1背包问题的边界函数定义为已经选择物品的总价值，加上背包剩余容量与剩下物品的最大单位价值的乘积。10.5.4分支限界策略应用实例分支限界策略应用实例10.5 分支限界策略分支限界策略 例如，对于表10-5的背包问题实例，背包的容量为10，那么运用分支限界法求解背包问题实例的解空间树如图10-14所示，依据边界函数可以计算每个结点的上限值。10.5.4分支限界策略应用实例
39、分支限界策略应用实例表10-5 一个背包问题实例的物品重量和价值，依据单位重量的价值降序排列物品编号重量价值价值/重量14401027426352554312410.5 分支限界策略分支限界策略10.5.4分支限界策略应用实例分支限界策略应用实例图10-12运用分支限界法求解0-1背包问题实例的解空间树本章小结本章小结 本章介绍五种算法设计策略和其应用实例，这些策略包括分治策略、贪心策略、动态规划策略、回溯策略和分支限界策略。通过对每种算法设计策略的基本设计步骤和设计模式的说明，使读者对算法设计策略的学问和应用有了直观的相识和全面的理解。通过本章的学习，读者应熟悉每种算法设计策略的适用条件，并能运用各种算法设计策略，依据实际问题设计程序解决问题。