1、第5章 算法思维与程序设计基础第5章 算法思维与程序设计基础 5.1 开启智慧的开启智慧的“苹果苹果”算法算法 5.2 亚当夏娃的诱惑亚当夏娃的诱惑算法与程序算法与程序 5.3 登上方舟的神器登上方舟的神器经典算法思想经典算法思想 第5章 算法思维与程序设计基础5.1 开启智慧的开启智慧的“苹果苹果”算法算法在20世纪50年代西方某些著名的词典中，还未曾收录过算法(Algorithm)一词。根据西方数学史家的考证，古代阿拉伯的一位学者写了一部名著Kitb al-jabr WalmuqbJla(复原和化简的规则)。这部著作流传到了西方，结果从作者署名中的al-Khwrizm派生出了Algorit
2、hm(算法)一词，从作品名字中的al-jabr派生出了Algebra(代数)一词。随着时间的推移，Algorithm(算法)这个词已经完全与它原来的含义不同了。第5章 算法思维与程序设计基础计算机系统中的任何软件，都是由大大小小的各种软件组成部分构成的，各自按照特定的算法来实现，算法的好坏直接决定所实现软件性能的优劣。用什么方法来设计算法，所设计的算法需要什么样的资源，需要多少运行时间、多少存储空间，如何判定一个算法的好坏，在开发一个软件时，都是必须予以解决的。计算机系统中的操作系统、语言编译系统、数据库管理系统以及各种各样的计算机应用系统中的软件，都必须用一个个具体的算法来实现。因此，算法设
3、计与分析是计算机科学与技术的一个核心问题。第5章 算法思维与程序设计基础5.1.1 算法的基本概念算法的基本概念欧几里德曾在他的著作中描述过求两个数的最大公因子的过程。20世纪50年代，欧几里德所描述的这个过程被称为欧几里德算法，算法这个术语在学术上便具有了现在的含义。下面是这个算法的例子及它的一种描述。第5章 算法思维与程序设计基础算法算法5.1.1 欧几里德算法。输入：正整数m，n输出：m，n的最大公因子1.int euclid(int m，int n)2.3.int r;4.do 5.r=m%n;6.m=n;7.n=r;8.while(r)9.return m;10.第5章 算法思维与程
4、序设计基础在此用一种类C语言来叙述最大公因子的求解过程。在算法的第5行，把m除以n的余数赋予r，第6行把n的值赋予m，第7行把r值赋予n，第8行判断r是否为0，若非0，继续转到第5行进行处理；若为0，就转到第9行处理，第9行返回m，算法结束。按照上面这组规则，给定任意两个正整数，总能返回它们的最大公因子。可以证明这个算法的正确性。第5章 算法思维与程序设计基础算法的历史可以追溯到9世纪的古波斯。最初它仅表示“阿拉伯数字的运算法则”。后来，它被赋予更一般的含义，即所谓的一组确定的、有效的、有限的解决问题的步骤。这是算法的最初定义。当代著名计算机科学家DEKnuth在他撰写的THE ART OF
5、COMPUTER PROGRAMMING一书中写到：“一个算法，就是一个有穷规则的集合，其中之规则规定了一个解决某一特定类型的问题的运算序列。”综上所述，可以给出算法的定义：算法是解某一特定问题的一组有穷规则的集合。第5章 算法思维与程序设计基础5.1.2 算法的基本特征算法的基本特征任何解决问题的过程都是由一定的步骤组成的，通常把解决问题的确定方法和有限步骤称为算法。对于计算机科学来说，算法指的是对特定问题求解步骤的一种描述，是若干条指令的有穷序列，并且它具有以下特性：(1)有穷性：算法在执行有限步骤之后结束。(2)确切性：算法的每一个步骤都有确切的定义。(3)输入：一个算法有0个或多个输入
6、，它是由外部提供的，作为算法开始执行前的初始值或初始状态。算法的输入是从特定的对象集合中抽取的。第5章 算法思维与程序设计基础(4)输出：一个算法有一个或多个输出，这些输出与输入有特定的关系，实际上是输入的某种函数。不同取值的输入，产生不同结果的输出。(5)可行性：在原则上算法能够精确地运行，进行有限次运算后即可完成一种运算。必须注意到，在实际应用中，有穷性的限制是不够的。一个实用的算法，不仅要求步骤有限，同时要求运行这些步骤所花费的时间是人们可以接受的。如果一个算法需要执行数十百亿计的运算步骤，则从理论上说，它是有限的，最终可以结束，但却是人们难以接受的。第5章 算法思维与程序设计基础算法设
7、计的整个过程，可以包含对问题需求的说明、数学模型的拟制、算法的详细设计、算法的正确性验证、算法的实现、算法分析、程序测试和文档资料的编制。第5章 算法思维与程序设计基础 5.2 亚当夏娃的诱惑亚当夏娃的诱惑算法与程序算法与程序5.2.1 算法思想的本质算法思想的本质数学模型数学模型简单地说，数学模型就是对实际问题的一种数学表达，是数学理论与实际问题相结合的一门科学。它将现实问题归结为相应的数学问题，并在此基础上利用数学概念、方法和理论进行深入分析与研究，从而可以从定性或定量的角度来刻画实际问题，并为解决现实问题提供精确数据和可靠指导。算法设计时，首先要根据问题的描述，建立符合要求的数学模型，并
8、设计相关的约束条件等。第5章 算法思维与程序设计基础建立数学模型的步骤如下：(1)模型准备。要了解问题的实际背景，明确建模目的，搜索必要的各种信息，尽量弄清对象的特征。(2)模型假设。根据对象的特征和建模目的，对问题进行必要的、合理的简化，用精确的语言做出假设，是建模至关重要的一步。高超的建模者能充分发挥想象力、洞察力和判断力，善于辨别问题所有因素的主次，而且为了使处理方法简单，应尽量使问题线性化、均匀化。(3)模型构成。根据所做的假设分析对象的因果关系，利用对象的内在规律和适当的数学工具，建立各个量之间的等式或不等式关系，列出表格、画出图形或确定其他数学结构，选择恰当的数学工具和构造模型的方
9、法对其进行表征，构造出刻画实际问题的数学模型。第5章 算法思维与程序设计基础(4)模型求解。构造数学模型之后，再根据已知条件和数据分析模型的特征及结构特点，设计或选择求解模型的数学方法和算法，这其中包括解方程、画图形、证明定理、进行逻辑运算及稳定性讨论，特别是编写计算机程序或运用与算法相适应的软件包，并借助计算机完成对模型的求解。(5)模型分析。根据建模的目的要求，对模型求解的数字结果，或进行变量之间的依赖关系分析，或进行稳定性分析，或进行系统参数的灵敏度分析，或进行误差分析等。通过分析，如果不符合要求，就修改或增减建模假设条件，重新建模，直到符合要求；如果符合要求，还可以对模型进行评价、预测
10、、优化等。第5章 算法思维与程序设计基础(6)模型检验模型分析符合要求之后，还必须回到客观实际中去对模型进行检验，用实际现象、数据等检验模型的合理性和适用性，看它是否符合客观实际，若不符合，就修改或增减假设条件，重新建模，循环往复，不断完善，直到获得满意的结果。目前计算机技术已为我们进行模型分析、模型检验提供了先进的手段，充分利用这一手段，可以节约大量的时间、人力和物力。(7)模型应用。模型应用是数学建模的宗旨，也是对模型最客观、最公正的检验。因此，一个成功的数学模型，必须根据建模的目的，将其用于分析、研究和解决实际问题，充分发挥数学模型在生产和科研中的特殊作用。第5章 算法思维与程序设计基础
11、5.2.2 算法思想的表达算法思想的表达算法设计算法设计人们希望计算机求解的问题是千差万别的，所设计的求解方法也千差万别。一般来说，算法设计没有固定的方法可循，所以，算法的设计是一个灵活且充满智慧的过程，要求设计者针对具体的问题设计出适合该问题的解决方案。在进行算法设计时，一般遵循以下步骤：(1)明确问题的性质，分析题意。这一步很关键。在设计算法的时候，一定要先搞清楚要求算法处理什么问题、实现哪些功能、预期获得的结果等。如果设计者没有充分理解所要解决的问题，那么设计出的算法肯定是漏洞百出的。这一步是算法的切入点，也是设计者必备的技能。第5章 算法思维与程序设计基础(2)建立问题的数学描述模型。
12、数学模型是对实际问题的一种数学表达，进行算法设计时，首先要根据问题的描述，建立符合要求的数学模型，并设计相关的约束条件等。(3)设计/验证算法。算法设计是把算法具体化，即设计出算法的详细规格说明。在这一阶段，要选择算法的设计策略，并确定合理的数据结构。显然，算法设计策略的选择关乎全局，同样，数据结构的选择对于算法的设计和分析也很重要，如果选择不当，它将影响算法的性能。做完上面的工作后，采用描述工具将算法的具体过程描述下来，通过对一系列与算法的工作对象有关的定理、引理和公式进行证明，来验证算法所选择的设计策略与思路是否正确。第5章 算法思维与程序设计基础(4)算法分析。算法分析是对算法的效率进行
13、分析，主要是时间效率和空间效率。其中，时间效率显示算法运行速度有多快，空间效率显示算法运行时需要的存储空间有多大。相对而言，人们更关注时间效率。(5)算法实现和测试。根据算法，采用一种编程语言编程实现，然后上机调试，得到程序的运行结果，分析运行结果是否符合预先的期望，如果不符合，则找出原因，并对算法或程序进行修正，直到得到正确的结果。第5章 算法思维与程序设计基础5.2.3 算法思想的实现算法思想的实现程序设计程序设计程序设计是给出解决特定问题程序的过程，是软件构造活动中的重要组成部分。程序设计往往以某种程序设计语言为工具，给出这种语言下的程序。程序设计过程应当包括分析、设计、编码、测试、排错
14、等不同阶段。任何设计活动都是在各种约束条件和相互矛盾的需求之间寻求一种平衡，程序设计也不例外。在计算机技术发展的早期，由于机器资源比较昂贵，程序的时间和空间代价往往是设计关心的主要因素；随着硬件技术的飞速发展和软件规模的日益庞大，程序的结构、可维护性、复用性、可扩展性等因素日益重要。第5章 算法思维与程序设计基础在程序设计时，一般遵循以下步骤：(1)分析问题。对于接受的任务要进行认真的分析，研究所给定的条件，分析最后应达到的目标，找出解决问题的规律，选择解题的方法，完成实际问题。(2)设计算法。即设计出解题的方法和具体步骤。(3)编写程序。将算法翻译成计算机程序设计语言，对源程序进行编辑、编译
15、和连接。(4)运行程序，分析结果。运行可执行程序，得到运行结果。能得到运行结果并不意味着程序正确，要对结果进行分析，看它是否合理。不合理要对程序进行调试，即通过上机发现和排除程序中的故障的过程。第5章 算法思维与程序设计基础(5)编写程序文档。许多程序是提供给别人使用的，如同正式的产品应当提供产品说明书一样，正式提供给用户使用的程序，必须向用户提供程序说明书。其内容应包括程序名称、程序功能、运行环境、程序的装入和启动、需要输入的数据，以及使用注意事项等。第5章 算法思维与程序设计基础5.2.4 检验真理的标准检验真理的标准算法分析算法分析解决一个问题，算法不必是唯一的。对表示问题的数据的不同组
16、织方式(数据结构)，解决问题的不同策略将导致不同的算法。解决同一问题的不同算法，消耗的时间和空间资源量有所不同。算法运行所需要的计算机资源的量称为算法的复杂性。一般来说，解决同一问题的算法，需要的资源量越少，我们认为越优秀。计算算法运行所需资源量的过程称为算法复杂性分析，简称算法分析。理论上，算法分析既要计算算法的时间复杂性，也要计算它的空间复杂性。然而，算法的运行时间都是消耗在数据处理上的，从这个意义上说，算法的空间复杂性不会超过时间复杂性。因此，人们多关注算法的时间复杂性。第5章 算法思维与程序设计基础1算法复杂性算法复杂性1)时间复杂性随着计算机硬件和软件的提升，一个算法的执行时间不便精
17、确计算，只能依据统计方法对算法进行估算。抛开硬件和软件的因素，算法的好坏将直接影响程序的运行时间。一个算法花费的时间与算法中语句的执行次数成正比，哪个算法中语句执行次数多，它花费的时间就多。一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，称为语句频度或时间频度，用T(n)表示，若有某个辅助函数f(n)，使得当n趋近于无穷大时，T(n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作T(n)=第5章 算法思维与程序设计基础O(f(n)，称O(f(n)为算法的渐进时间复杂度，简称时间复杂度。随着模块n的增大，算法执行的时间增长率f(n)的增长率成正比，
18、所以f(n)越小，算法的时间复杂度越低，算法的效率越高。例例5-1 分析下面程序的时间复杂度：int value=0;/执行了1次for(int i=0;i n;i+)/执行了n次value+=i;第5章 算法思维与程序设计基础这个算法执行了1+n次，如果n无限大，则可以把前边的1忽略，也就是说这个算法执行了n次，这个算法的时间复杂度就是O(n)。计算时间复杂度的步骤如下：(1)去掉运行时间中的所有加法常数。(2)只保留最高阶项。(3)如果最高阶项存在且不是1，则去掉与这个最高阶相乘的常数即可得到时间复杂度。第5章 算法思维与程序设计基础例例5-2 计算下面程序的时间复杂度：分析：当i=0时，
19、里面的for循环执行了n次，当i等于1时里面的for循环执行了n1次，当i等于2时里面的for执行了n2次，所以执行的次数是第5章 算法思维与程序设计基础根据上边计算时间复杂度的步骤，可得以下计算过程：(1)去掉运行时间中的所有加法常数：这里没有加法常数不用考虑。(2)只保留最高阶项：这里只保留。(3)去掉与这个最高阶相乘的常数：这里去掉 只剩下n2。最终这个算法的时间复杂度为O(n2)。例例5-3 计算下面程序的时间复杂度：for(int i=0;i b+a，就把a排在b的前面，反之则把a排在b的后面。贪婪算法所作的选择可以依赖于以往所作过的选择，但决不依赖于将来的选择，也不依赖于子问题的解
20、，因此贪婪算法与其他算法相比具有一定的速度优势。如果一个问题可以同时用几种方法解决，则贪婪算法应该是最好的选择之一。第5章 算法思维与程序设计基础5.3.3 成竹在胸成竹在胸动态规划法动态规划法动态规划(Dynamic Programming)法是 20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程(Multistep Decision Process)的优化问题时，把多阶段过程转化为一系列单阶段问题，利用各阶段之间的关系，逐个求解，所创立的解决这类过程优化问题的新方法。动态规划问世以来，在经济管理、生产调度、工程技术和最优控制等方面得到了广泛的应用。例如，最短路线、库
21、存管理、资源分配、设备更新、排序、装载等问题，用动态规划法比用其他方法求解更为方便。第5章 算法思维与程序设计基础动态规划程序设计是解决最优化问题的一种途径和方法，而不是一种特殊算法。不像搜索或数值计算那样，具有一个标准的数学表达式和明确清晰的解题方法。由于各种问题的性质不同，确定最优解的条件也互不相同，因而动态规划的设计方法对不同的问题，有各具特色的解题方法，而不存在一种万能的动态规划算法，可以解决各类最优化问题。因此读者在学习时，在正确理解基本概念和方法的基础上，必须具体问题具体分析处理，以丰富的想象力去建立模型，用创造性的技巧去求解。第5章 算法思维与程序设计基础1动态规划法所能解决的问
22、题特征动态规划法所能解决的问题特征(1)最优子结构性质：一个最优化策略具有这样的性质，不论过去状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。简而言之，一个最优化策略的子策略总是最优的。(2)无后效性：将各阶段按照一定的次序排列好之后，对于某个给定的阶段状态，它以前各阶段的状态无法直接影响它未来的决策，而只能通过当前的这个状态。换句话说，每个状态都是过去历史的一个完整总结。这就是无后效性，又称为无后向性。第5章 算法思维与程序设计基础(3)子问题的重叠性：即子问题之间是不独立的，一个子问题在下一阶段决策中可能被多次使用到。该性质并不是动态规划适用的必要条件，但是如果
23、没有这条性质，动态规划算法同其他算法相比就不具备优势。第5章 算法思维与程序设计基础2动态规划算法的基本思路动态规划算法的基本思路动态规划算法的基本思想与分治法类似，也是将待求解的问题分解为若干个子问题(阶段)，按顺序求解子阶段，前一子问题的解为后一子问题的求解提供了有用的信息。在求解任一子问题时，列出各种可能的局部解，通过决策保留那些有可能达到最优的局部解，丢弃其他局部解。依次解决各子问题，最后一个子问题就是初始问题的解。由于动态规划解决的问题多数有重叠子问题这个特点，为减少重复计算，对每一个子问题只解一次，将其不同阶段的不同状态保存在一个二维数组中。动态规划法与分治法最大的差别是：适合于用
24、动态规划法求解的问题，经分解后得到的子问题往往不是互相独立的(即下一个子阶段的求解是建立在上一个子阶段的解的基础上，进行进一步的求解)。第5章 算法思维与程序设计基础3.动态规划算法的求解步骤动态规划算法的求解步骤动态规划所处理的问题是一个多阶段决策问题，一般由初始状态开始，通过对中间阶段决策的选择，达到结束状态。动态规划的设计都有着一定的模式，一般要经历以下几个步骤。(1)划分阶段：按照问题的时间或空间特征，把问题分为若干个阶段。在划分阶段时，注意划分后的阶段一定要是有序的或者是可排序的，否则问题就无法求解。(2)确定状态和状态变量：将问题发展到各个阶段时所处于的各种客观情况用不同的状态表示
25、出来。当然，状态的选择要满足无后效性。第5章 算法思维与程序设计基础(3)确定决策并写出状态转移方程：因为决策和状态转移有着天然的联系，状态转移就是根据上一阶段的状态和决策来导出本阶段的状态。所以如果确定了决策，状态转移方程也就可写出。但事实上常常是反过来做，根据相邻两个阶段的状态之间的关系来确定决策方法和状态转移方程。(4)寻找边界条件：给出的状态转移方程是一个递推式，需要一个递推的终止条件或边界条件。实际应用中可以按以下简化的步骤进行设计：(1)分析最优解的性质，并刻画最优解的结构特征。(2)递归定义最优值。(3)自底向上计算出最优值，并记录相关信息。(4)根据计算最优值时得到的信息，构造
26、出最优解。第5章 算法思维与程序设计基础4动态规划算法设计模式动态规划算法设计模式根据上述动态规划设计的步骤，可得到大体解题框架如下:(1)初始化(边界条件)。(2)for i:=2 to n(顺推法)或for i:=n1 to 1(逆推法)，对i阶段的每一个决策点求局部最优。(3)确定和输出结束状态的值。例例5-6 一个有N个整数元素的一位数组(A0，A1，,An1，An)，这个数组当然有很多子数组，那么数组之和的最大值是什么呢？第5章 算法思维与程序设计基础明确一下题意：(1)子数组必须是连续的。(2)不需要返回子数组的具体位置。(3)数组中包含正整数、零和负整数。例如：数组1，2，3，5
27、，3，2的返回值为8；数组0，2，3，5，1，2的返回值为9；数组9，2，3，5，6的返回值为2，注意子数组不能为空。第5章 算法思维与程序设计基础根据题意，可以考虑数组的第一个元素，以及最大的一段数组(Ai，Aj)和A0的关系，有以下几种情况：(1)当0=i=j时，元素A0本身构成和最大的一段；(2)当0=i j时，和最大的一段以A0开始；(3)当0 i时，元素A0和最大的一段没有关系。从上面三种情况看出：可以将一个大问题(N个元素数组)转化为一个较小的问题(N1个元素的数组)。假设已经知道(A1，An1)中和最大的一段数组之和为All1，并且已经知道(A1，An1)中包含A1的和最大的一段
28、数组为Start1，那么不难看出(A0，An)中问题的解All0=maxA0，A0+start1，All1。通第5章 算法思维与程序设计基础过这样的分析，可以看出这个问题无后效性，可以用动态规划来解决，算法如下：第5章 算法思维与程序设计基础5.3.4 志在四方志在四方周游法周游法1遍历方案遍历方案从二叉树的递归定义可知，一棵非空的二叉树由根节点及左、右子树这三个基本部分组成，如图5.1所示，因此，在任一给定节点上，可以按某种次序执行三个操作：(1)访问节点本身(N)。(2)遍历该节点的左子树(L)。(3)遍历该节点的右子树(R)。以上三种操作有六种执行次序：NLR、LNR、LRN、NRL、R
29、NL、RLN。注意：前三种次序与后三种次序对称，故只讨论先左后右的前三种次序。第5章 算法思维与程序设计基础图5.1 遍历二叉树的搜索路线第5章 算法思维与程序设计基础2三种遍历的命名三种遍历的命名根据访问节点操作发生位置命名：(1)NLR：前序遍历(Preorder Traversal，亦称先序遍历)访问节点的操作发生在遍历其左右子树之前。(2)LNR：中序遍历(Inorder Traversal)访问节点的操作发生在遍历其左右子树之中(间)。(3)LRN：后序遍历(Postorder Traversal)访问节点的操作发生在遍历其左右子树之后。注意：由于被访问的节点必是某子树的根，所以N(
30、Node)、L(Left subtlee)和R(Right subtree)又可解释为根、根的左子树和根的右子树。NLR、LNR和LRN分别又称为先根遍历、中根遍历和后根遍历。第5章 算法思维与程序设计基础3遍历算法遍历算法1)中序遍历的递归算法若二叉树非空，则依次执行如下操作：(1)遍历左子树；(2)访问根节点；(3)遍历右子树。中序遍历图5.1所示的二叉树时，得到的中序序列为D B A E C F。第5章 算法思维与程序设计基础2)先序遍历的递归算法若二叉树非空，则依次执行如下操作：(1)访问根节点；(2)遍历左子树；(3)遍历右子树。先序遍历图5.1所示的二叉树时，得到的中序序列为A B
31、 D C E F。第5章 算法思维与程序设计基础3)后序遍历得递归算法定义若二叉树非空，则依次执行如下操作：(1)遍历左子树；(2)遍历右子树；(3)访问根节点。后序遍历图5.1所示的二叉树时，得到的中序序列为D B E F C A。第5章 算法思维与程序设计基础注意事项：(1)在搜索路线中，若访问节点均是第一次经过节点时进行的，则是前序遍历；若访问节点均是在第二次(或第三次)经过节点时进行的，则是中序遍历(或后序遍历)。只要将搜索路线上所有在第一次、第二次和第三次经过的节点分别列表，即可分别得到该二叉树的前序序列、中序序列和后序序列。(2)上述三种序列都是线性序列，有且仅有一个开始节点和一个
32、终端节点，其余节点都有且仅有一个前趋节点和一个后继节点。为了区别于树形结构中前趋(即双亲)节点和后继(即孩子)节点的概念，对上述三种线性序列，要在某节点的前趋和后继之前冠以其遍历次序名称。第5章 算法思维与程序设计基础例例5-7 图5.1所示的二叉树中节点C，其前序前趋节点是D，前序后继节点是E；中序前趋节点是E，中序后继节点是F；后序前趋节点是F，后序后继节点是A。但是就该树的逻辑结构而言，C的前趋节点是A，后继节点是E和F。4算法递归实现算法递归实现在这里，假设所有的二叉树都以数组的形式储存。(1)中序遍历。procedure mid(i:longint);beginif ai*20 th
33、en mid(i*2)；write(ai);if ai*2+10 then mid(i*2+1)；end;第5章 算法思维与程序设计基础(2)先序遍历。procedure first(i:longint);beginwrite(ai);ifai*20then first(i*2)；ifai*2+10then first(i*2+1)；end;第5章 算法思维与程序设计基础(3)后序遍历。procedure last(i:longint);beginif ai*20 then last(i*2)；if ai*2+10 then last(i*2+1)；write(ai);end;第5章 算法思维
34、与程序设计基础5.3.5 迷途知返迷途知返回溯法回溯法1回溯法所能解决的问题特征回溯法所能解决的问题特征可用回溯法求解的问题P，通常要能表达为：对于已知的由n元组(x1，x2，xn)组成的一个状态空间E=(x1，x2，xn)xiSi，i=1，2，n，给定关于n元组中的一个分量的一个约束集D，要求E中满足D的全部约束条件的所有n元组。其中Si是分量xi的定义域，且|Si|有限，i=1，2，n。我们称E中满足D的全部约束条件的任一n元组为问题P的一个解。第5章 算法思维与程序设计基础我们发现，对于许多问题，所给定的约束集D具有完备性，即i元组(x1，x2，xi)满足D中仅涉及x1，x2，xi的所有
35、约束意味着j(j=i)元组(x1，x2，xj)一定也满足d中仅涉及x1，x2，xj的所有约束，其中i=1，2，n。换句话说，只要存在0jn-1，使得(x1，x2，xj)违反d中仅涉及x1，x2，xj的约束之一，则以(x1，x2，xj)为前缀的任何n元组(x1，x2，xj，xj+1，xn)一定也违反d中仅涉及x1，x2，xi的一个约束(jin)。因此，对于约束集d具有完备性的问题P，一旦检测断定某个j元组(x1，x2，xj)违反d中仅涉及x1，x2，xj的一个约束，就可以肯定，以(x1，x2，xj)为前缀的任何n元组第5章 算法思维与程序设计基础(x1，x2，xj，xj+1，xn)都不会是问题P
36、的解，因而就不必去搜索、检测它们。回溯法正是针对这类问题，利用这类问题的上述性质而提出的比枚举法效率更高的算法。2回溯法的基本要素回溯法的基本要素(1)约束条件：包括隐性的和显性的，显约束指对问题的解的取值范围限定，隐约束指为满足问题的解而对不同分量之间施加的约束。(2)解空间：对于问题的一个实例，解向量满足显约束的所有n元组构成该实例的一个解空间。为了搜索方便，一般用树或图的形式将问题的解空间有效地组织起来，称为状态树，它是构造深度搜索过程的依据，整个搜索以此树展开。注意：同一个问题的显约束可能有多种，相应解空间的大小就会不同，通常情况下，解空间越小，算法的搜索效率越高。第5章 算法思维与程
37、序设计基础3回溯法算法的求解步骤回溯法算法的求解步骤(1)针对所给问题，确定问题的解空间。首先应明确问题的解空间，问题的解空间应至少包含问题的一个(最优)解。(2)确定节点的扩展搜索规则。搜索思想：从根节点开始，以深度优先搜索的方式进行搜索。在搜索过程中，当前的扩展节点延纵深方向移向一个新节点，判断新节点是否满足隐约束。如果满足，则新节点成为当前的扩展节点，继续深一层的搜索；如果不满足，则换到扩展节点的兄弟节点(其他分支)继续搜索。如果新节点没有兄弟节点，或兄弟节点已全部搜索完毕，则扩展节点成为死节点，搜索回溯到其父节点处继续进行。搜索过程直到找到问题的解或根节点变成死节点为止。第5章 算法思
38、维与程序设计基础(3)以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。在深度优先搜索的过程中，不满足隐约束的分支被剪掉，只沿着满足隐约束的分支搜索问题的解，从而避免了无效搜索，加快了速度。因此，隐约束又称为剪枝函数。剪枝函数一般有两种：一是判断是否能够得到可行解的隐约束，称为约束函数；二是判断是否有可能得到最优解的隐约束，称为限界函数。回溯法是一种具有约束函数或限界函数的深度优先搜索法。第5章 算法思维与程序设计基础4回溯算法设计模式回溯算法设计模式回溯算法通常采用递归技术，也可以选用非递归技术。在设计过程中，参数t代表当前扩展节点在解空间树中所处的层次；变量n代表问题的规模，
39、也是解空间的深度；s(n，t)代表当前扩展节点处未搜索的子树的起始编号，e(n，t)代表当前扩展节点处未搜索的子树的终止编号；d(i)代表当前扩展节点可选分支上的数据；X是用来记录问题当前解的数组；constraint(t)代表当前扩展节点处的约束函数；bound(t)代表当前扩展节点处的限界函数。满足约束和限界函数则继续深一层次的搜索，否则就剪掉相应的子树。Backtrack(t)代表从第t层开始搜索问题的解。第5章 算法思维与程序设计基础(1)递归回溯模式。第5章 算法思维与程序设计基础第5章 算法思维与程序设计基础第5章 算法思维与程序设计基础例例5-8 数的划分(noip2001tg)
40、。问题描述：将整数n分成k份，且每份不能为空，任意两份不能相同(不考虑顺序)。例如，n=7，k=3，下面三种分法被认为是相同的：1，1，5；1，5，1；5，1，1。有多少种不同的分法？输入：n，k(6n=200，2=k=6)；输出：一个整数，即不同的分法。例如：输入：7 3；输出：4 四种分法为：1，1，5；1，2，4；1，3，3；2，2，3。第5章 算法思维与程序设计基础算法分析：此题可以用回溯法求解，设自然数n拆分为a1，a2，ak，必须满足以下两个条件：(1)n=a1+a2+ak；(2)a1=a2=ak(避免重复计算)。现假设己求得的拆分数为a1，a2，ai，且都满足以上两个条件，设su
41、m=n-a1-a2-ai，可根据不同的情形进行处理：(1)如果i=k，则得到一个解，则计数器t加1，并回溯到上一步，改变ai-1的值；(2)如果i=ai，则添加下一个元素ai+1；(3)如果ik且sumai，则说明达不到目标，回溯到上一步，改变ai-1的值。第5章 算法思维与程序设计基础算法实现步骤如下：(1)输入自然数n，k并初始化：t:=0;i:=1;ai:=1;sum:=n-1;nk:=n div k。(2)如果a1=ai则继续搜索，若sumai则回溯。搜索时，inc(i);ai:=ai-1;sum:=sum-ai;；回溯时，dec(i);inc(ai);sum:=sum+ai+1-1。
42、(3)输出。第5章 算法思维与程序设计基础5.3.6 画地为牢画地为牢分枝限界法分枝限界法1分枝限界算法的基本思路分枝限界算法的基本思路分枝限界算法常以广度优先或以最小耗费(最大收益)优先的方式搜索问题的解空间树。问题的解空间树是表示解空间的一棵有序树。在搜索问题的解空间树时，分枝限界算法与回溯法对当前节点所采用的扩展方式不同：在分枝限界算法中，每一个活节点(一个自身已生成但其子节点还没有全部生成的节点)只有一次机会成为扩展节点，某节点成为扩展节点后，就一次性产生所有子节点。在这些子节点中，那些导致不可行解或导致非最优解的子节点被舍弃，其余子节点被加入活节点表中。此后，从活节点表中取下一节点成
43、为当前扩展节点，并重复上述节点扩展过程，直到找到所需的解或活节点表为空时为止。第5章 算法思维与程序设计基础2分枝节点的选择分枝节点的选择对搜索树上的某些点必须作出分枝决策，即凡是界限小于迄今为止所有可行解最小下界的任何子集(节点)，都有可能作为分枝的选择对象(对求最小值问题而言)。怎样选择搜索树上的节点作为下次分枝的节点呢？有两个原则：(1)从最小下界分枝(优先队列式分枝限界法)：每次算完界限后，把搜索树上当前所有叶节点的界限进行比较。找出限界最小的节点，此节点即为下次分枝的节点。优点：检查子问题较少，能较快地求得最佳解。缺点：要存储很多叶节点的界限及对应的耗费矩阵，会花费很多内存空间。第5
44、章 算法思维与程序设计基础(2)从最新产生的最小下界分枝(队列式(FIFO)分枝限界法)：从最新产生的各子集中按顺序选择各节点进行分枝，对于下界比上界还大的节点不进行分枝。优点：节省了空间。缺点：需要较多的分枝运算，耗费的时间较多。这两个原则更进一步说明了在算法设计中的时空转换概念。分枝定界法已经成功地应用于求解整数规划问题、生产进度表问题、货郎担问题、选址问题、背包问题以及可行解的数目为有限的许多其他问题。对于不同的问题，分枝与界限的步骤和内容可能不同，但基本原理是一样的。第5章 算法思维与程序设计基础3分枝限界算法与回溯法比较分枝限界算法与回溯法比较1)相同点(1)都需要先定义问题的解空间
45、，解空间一般用树或图来表示。(2)在问题的解空间树上搜索问题的解。搜索前确定判断条件，该条件用来判断扩展生成的节点是否为可行节点。(3)搜索过程中必须判断扩展生成的节点是否满足判断条件，从而决点该节定是否保留。第5章 算法思维与程序设计基础2)不同点(1)求解目标不同：回溯法的求解目标是找出解空间树中满足约束条件的所有解，而分枝限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解。(2)搜索方式不同：回溯法以深度优先的方式搜索解空间树，而分枝限界法则以广度优先或以最小耗费优先的方式搜索解空间树。第5章 算法思维与程序设计基础4分枝限界算法的求解步骤分枝
46、限界算法的求解步骤(1)定义问题的解空间。(2)确定问题的解空间组织结构。(3)搜索解空间。根据采用的搜索方法不同定义合适的约束条件和限界条件，然后开始搜索。初始时将根节点放入活节点表中。从活节点表中取出一个活节点作为当前的扩展节点，一次性生成扩展节点的所有子节点，判断是否满足约束条件和限界条件，如果满足，则将其插入活节点表中，反之舍弃。第5章 算法思维与程序设计基础5例题例题设有4个人，每人都可以完成4种不同的工作，但所需时间不同。如果只需1人去完成一项工作，则应如何分配4人去完成4项工作，并使所有工作的总时间最小。满足以下约束条件：分配1人且仅有1人去做每项工作 (1)的解称为分配问题的可
47、行解。表5-1给出了A、B、C、D 4个人分别完成工作1、2、3、4所需的时间。第5章 算法思维与程序设计基础表表5-1 分配问题的初始数据分配问题的初始数据第5章 算法思维与程序设计基础基本思想：从非可行解中逐步寻找可行解。求解步骤如下：(1)不考虑条件(1)，由表5-1中每列的最小时间的和，可得最小的总时间为2+4+9+7=22。数值22表示所有解的时间下界，但这个不是可行解，因为A不止做一件工作，这样得到根节点的下界，见表5-2。表表5-2 求根节点下界求根节点下界第5章 算法思维与程序设计基础(2)把24个可行解组成的解空间分成4个子集，每个子集包括6个可行解。划分的方法为：先分配一人
48、去做工作1，然后分配其余三人分别去做工作2、3、4，每个这样的解都是可行的。重复上述过程，分配不同的人去做工作1，直到4个人都分配到一次，算出这四种情况下所得的总时间，就是分配某人去做工作1的条件下所有解的下界(分配A做工作1，需要总时间2+4+13+8=27，分配B、C、D做工作1，需要总时间分别为41，33，24)，结果如表5-3所示，这些解都不是可行解。第5章 算法思维与程序设计基础表表5-3 4个下界个下界第5章 算法思维与程序设计基础以上结果可表示为图5.2所示的树。圆圈内的数字表示节点编号，圆圈下的数字表示该子集的下界，如27表示分配A去做工作1条件下所有解的下界，分枝边表示分配某
49、人去做工作1。(3)因为节点5的下界最小，所以对节点5进一步分枝。在分配D做工作1的条件下，类似的先分配B、C、A中的任一人做工作2，再分配其他人做工作3和4，但不考虑条件(1)，只要使总时间最小即可。结果如表5-4所示，从表中可以看出，分配D做工作1，A、B、C做工作2，需要总时间分别为36，24，34。第5章 算法思维与程序设计基础图5.2 一次分枝后的搜索树第5章 算法思维与程序设计基础表表5-4 计算计算3个下界个下界第5章 算法思维与程序设计基础这些解也都不是可行解，以上结果可表示为图5.3所示的树。其中所有叶节点没有一个解可行，选限界最小的节点7作为分枝节点。(4)对于节点7的分枝
50、，在已分配D做工作1，分配B做工作2的条件下，只有两种情况：或者分配A做工作3，分配C做工作4，需要总时间为28，这是一个可行解，且28是可行解集合的下界；或者分配C做工作3，A做工作4，需要总时间为31，这虽然也是一个可行解，但总时间大于现有可行解的下界28，故不考虑。第5章 算法思维与程序设计基础以上结果可表示成图5.4所示的树，由节点9得到一个可行解，D1，B2，A3，C4，其值为28。其他叶节点中只有节点2的限界为27，比它小，所以选节点2进一步分枝，得节点11、12、13，其中限界最小的节点为11，下界为28，与节点9相同。从节点11出发，不可能求得耗费比28更小的分配方法。如果是求
