计算思维导论第3章课件.ppt

1、3-1/603-2/601974年图灵奖获得者年图灵奖获得者Donald Ervin Knuth: 计算机科学就是算法的研究计算机科学就是算法的研究The Art of Computer Programming计算机计算机输入输入输出输出算法算法问题问题算法与计算机之间的关系算法与计算机之间的关系3-3/60一、算法的起源一、算法的起源公元前公元前300300年：古希腊著名数学家欧几里得提出求最大年：古希腊著名数学家欧几里得提出求最大公约数的一种算法公约数的一种算法, ,即辗转相除法又称即辗转相除法又称欧几里得算法。欧几里得算法。公元公元263263年：三国魏人刘徽注释年：三国魏人刘徽注释九章

2、算术九章算术中不仅对中不仅对原书的方法、公式和定理进行一般的解释和推导，而原书的方法、公式和定理进行一般的解释和推导，而且在其论述中多有创造。如他运用割圆术得出圆周率且在其论述中多有创造。如他运用割圆术得出圆周率的近似值的近似值3927/12503927/12503.14163.1416。公元公元825825年：波斯数学家年：波斯数学家al-al-KhwarizmiKhwarizmi撰写了著名的撰写了著名的Persian TextbookPersian Textbook中概括了进行四则算术运算的法则。中概括了进行四则算术运算的法则。Algorithm(Algorithm(算法算法) )一词就来

3、源于这位数学家的名字。一词就来源于这位数学家的名字。3-4/60二、算法的定义二、算法的定义 算法算法3.13.1欧几里得算法。欧几里得算法。输入：正整数输入：正整数m m、n n输出：输出：m m、n n的最大公约数的最大公约数 r rm mod nm mod n 若若r r0 0，输出最大公约数，输出最大公约数n n 若若r0r0，令，令m mn n，n nr r，转继续，转继续 算法算法：是解决某一特定问题的一组有穷规则的集合。：是解决某一特定问题的一组有穷规则的集合。算法算法：对特定问题求解步骤的一种描述，是由若干条：对特定问题求解步骤的一种描述，是由若干条指令组成的有穷集合。指令组成

4、的有穷集合。3-5/60三、算法的特征三、算法的特征确定性确定性：算法中每一个步骤都是清晰的、无歧义：算法中每一个步骤都是清晰的、无歧义有穷性有穷性：算法必须在有限步内终止：算法必须在有限步内终止输输 入入：有零个或多个输入，作为初始状态：有零个或多个输入，作为初始状态输输 出出：有一个或多个输出，作为计算结果：有一个或多个输出，作为计算结果可行性可行性：算法中的操作可通过有限次基本运算来实现：算法中的操作可通过有限次基本运算来实现判断一个算法的好坏主要依据如下标准判断一个算法的好坏主要依据如下标准：正确性正确性：在合理输入下能在有限时间内得出正确结果：在合理输入下能在有限时间内得出正确结果可

5、读性可读性：算法主要是为了人的阅读与交流，其次执行：算法主要是为了人的阅读与交流，其次执行健壮性健壮性：算法应具备检查错误和对错误进行处理能力：算法应具备检查错误和对错误进行处理能力效效 率率：算法执行时所需计算机资源的多少：算法执行时所需计算机资源的多少3-6/60算法的描述目的算法的描述目的记录算法思想记录算法思想方便他人理解算法方便他人理解算法算法的描述方法算法的描述方法自然语言自然语言流程图流程图伪代码伪代码程序设计语言程序设计语言3-7/60一、自然语言一、自然语言自然语言自然语言是人们日常进行交流的语言，如汉语、英语等是人们日常进行交流的语言，如汉语、英语等优点优点：通俗易懂，即使

6、没有学过算法也能看懂算法执行：通俗易懂，即使没有学过算法也能看懂算法执行缺点缺点：不够严谨，容易出现歧义和错误：不够严谨，容易出现歧义和错误 例题例题 利用自然语言描述欧几里得算法。利用自然语言描述欧几里得算法。 输入输入m m、n n 判断判断n n是否为是否为0 0，如果不为，如果不为0 0，转步骤，否则转，转步骤，否则转 m m对对n n取余，其结果赋值给取余，其结果赋值给r r，n n赋给赋给m m，r r赋给赋给n n，转，转 输出输出m m，算法结束，算法结束3-8/60二、流程图二、流程图 常用来描述算法的图形工具有常用来描述算法的图形工具有：流程图或程序框图、：流程图或程序框图

7、、N-SN-S图和图和PADPAD图。图。 优点优点：直观形象，简洁明了。：直观形象，简洁明了。 缺点缺点：画起来费事，不易修改。：画起来费事，不易修改。常用的流程图符号常用的流程图符号：3-9/60 例题例题 利用流程图描述欧几里得算法。利用流程图描述欧几里得算法。3-10/60三、伪代码三、伪代码 伪代码是由带标号的指令构成，但是它不是伪代码是由带标号的指令构成，但是它不是C C、C+C+、JavaJava等通常使用的程序设计语言，而是算法步骤的描述。等通常使用的程序设计语言，而是算法步骤的描述。 伪代码介于自然语言和程序设计语言之间。伪代码介于自然语言和程序设计语言之间。伪代码的具体表示

8、伪代码的具体表示：赋值语言：赋值语言：分支语句：分支语句：ifthenelseifthenelse循环语句：循环语句：while, for, repeat untilwhile, for, repeat until转向语句：转向语句：gotogoto输出语句：输出语句：returnreturn调用：调用：注释：注释：/3-11/60 例题例题 利用伪代码描述欧几里得算法。利用伪代码描述欧几里得算法。输入：正整数输入：正整数m m、n n输出：输出：m m、n n的最大公约数的最大公约数1 repeat1 repeat2 r m mod n2 r m mod n3 m 3 m n n4 n 4

9、n r r5 until r=05 until r=06 return m6 return m 3-12/60四、程序设计语言四、程序设计语言 程序设计语言是一个能完整、准确和规则程序设计语言是一个能完整、准确和规则地表达人们的意图，并用以指挥或控制计算机地表达人们的意图，并用以指挥或控制计算机工作的工作的符号系统符号系统，如，如C C、C+C+、JavaJava等程序设计等程序设计语言可以描述算法。语言可以描述算法。 优点优点：描述的算法能在计算机上直接执行：描述的算法能在计算机上直接执行 缺点缺点：抽象性差、不易理解且有严格的语：抽象性差、不易理解且有严格的语法限制等。法限制等。3-13/

10、60输入：正整数输入：正整数m m、n n输出：输出：m m、n n的最大公约数的最大公约数intint gcd(intgcd(int m, m, intint n) n) intint r;r; do do r = m % n; r = m % n; m = n; m = n; n = r; n = r; while(r)while(r); ; return m; return m; 例题例题 利用利用C C语言描述欧几里得算法。语言描述欧几里得算法。3-14/60 算法是解决问题的方案，由于实际问题千奇算法是解决问题的方案，由于实际问题千奇百怪，因而制定出的解决方案也将千差万别。百怪，因而

11、制定出的解决方案也将千差万别。 算法设计的一般步骤算法设计的一般步骤： 理解待求解问题理解待求解问题 解决问题是设计算法的最终目标。除了需要分析问题的解决问题是设计算法的最终目标。除了需要分析问题的求解目标、输入数据和限制条件外，还要判断清楚待求解问求解目标、输入数据和限制条件外，还要判断清楚待求解问题的种类，是否有现成的算法可以直接应用。题的种类，是否有现成的算法可以直接应用。 确定算法运行的环境确定算法运行的环境 了解算法的运行环境，才能设计出可行且高效的算法。了解算法的运行环境，才能设计出可行且高效的算法。比如在小型的嵌入式环境中只能运行需要较小内存的算法，比如在小型的嵌入式环境中只能运

12、行需要较小内存的算法，而对于并行分布式的运行环境，则要设计高效的并行算法。而对于并行分布式的运行环境，则要设计高效的并行算法。3-15/60 设计算法设计算法 设计算法是将算法具体化，即设计出算法的详细规格说明。设计算法是将算法具体化，即设计出算法的详细规格说明。也就是，首先确定算法所需要的数据结构，然后结合具体问题的也就是，首先确定算法所需要的数据结构，然后结合具体问题的特性来选择算法的设计策略，最后根据算法设计技术的原理描述特性来选择算法的设计策略，最后根据算法设计技术的原理描述算法的具体流程算法的具体流程( (流程图、伪代码和程序设计语言等流程图、伪代码和程序设计语言等) )。 分析算法

13、分析算法 对所设计出的算法进行复杂性分析，考察其在时间和空间方对所设计出的算法进行复杂性分析，考察其在时间和空间方面的计算开销。若算法在某些环节的计算开销较大，可有针对性面的计算开销。若算法在某些环节的计算开销较大，可有针对性地改进该环节，若整个算法的计算开销太大，则需要返回第步地改进该环节，若整个算法的计算开销太大，则需要返回第步重新考虑采用新的算法设计技术来求解该问题。重新考虑采用新的算法设计技术来求解该问题。 编程实现编程实现 采用某种程序设计语言将设计好的算法实现出来。采用某种程序设计语言将设计好的算法实现出来。3-16/60 算法分类算法分类： 数值算法数值算法 求解线性方程组、数值

14、积分等，有特定的计算步骤求解线性方程组、数值积分等，有特定的计算步骤 数值数值计算方法计算方法课程课程 非数值算法非数值算法 求解判定问题、最优化问题求解判定问题、最优化问题等等，需需要要掌握算法设计掌握算法设计技术技术 算法设计与分析算法设计与分析课程课程 软计算方法软计算方法 遗传算法、遗传算法、粒子群粒子群算法、蚁群算法、人工算法、蚁群算法、人工神经网络等神经网络等 计算智能计算智能课程课程3-17/60一、穷举法一、穷举法( (又称蛮力算法又称蛮力算法) ) 穷举法穷举法指在问题的解空间范围内逐一测试，指在问题的解空间范围内逐一测试，找出问题的解。找出问题的解。它它是一种简单而有效的算

15、法设计是一种简单而有效的算法设计策略同时也是一种很容易应用的方法。策略同时也是一种很容易应用的方法。 穷举法的应用穷举法的应用 国王的婚姻中国王使用的算法国王的婚姻中国王使用的算法 旅行商问题旅行商问题中中逐条路线计算逐条路线计算 密码学中的暴力破解法密码学中的暴力破解法 图论中四色定理的证明图论中四色定理的证明 百钱买百钱买百鸡问题百鸡问题 3-18/60 案例一案例一 暴力破解法是一种用穷举法实现的密码暴力破解法是一种用穷举法实现的密码破译方法。破译方法。最原始、最基本的攻击方式，对密码进行逐一最原始、最基本的攻击方式，对密码进行逐一测试直到找到真正的密码。测试直到找到真正的密码。原则上可

16、以破译所有密码，但费时费力。原则上可以破译所有密码，但费时费力。密码暴力破解软件：密码暴力破解软件：89Winrar89Winrar QQ QQ密码暴力破解软件密码暴力破解软件3-19/60 案例二案例二 四色定理四色定理( (又称四色问题或四色猜想又称四色问题或四色猜想) )。四色问题描述四色问题描述：任何一张地图只用四种颜色就能使具有共同边：任何一张地图只用四种颜色就能使具有共同边界的国家着上不同的颜色。界的国家着上不同的颜色。数学语言表示数学语言表示：将平面任意地细分为不相重叠的区域，每一个：将平面任意地细分为不相重叠的区域，每一个区域总可以用区域总可以用1 1、2 2、3 3、4 4这

17、四个数字之一来标记，而不会使相这四个数字之一来标记，而不会使相邻的有公共边界的两个区域得到相同的数字。邻的有公共边界的两个区域得到相同的数字。证明四色定理证明四色定理( (穷举法穷举法) )：利用数学理论推出证明所有例子可以归约到证明有限个特例利用数学理论推出证明所有例子可以归约到证明有限个特例上；上；利用计算机程序产生了所有特例利用计算机程序产生了所有特例( (大约大约17001700个例子个例子) )，通过穷，通过穷举发现所有特例都是四着色的。举发现所有特例都是四着色的。3-20/60 案例三案例三 百钱买百鸡问题百钱买百鸡问题 百钱买百鸡：鸡翁一，值钱五百钱买百鸡：鸡翁一，值钱五 鸡母一

18、，值钱三鸡母一，值钱三 鸡雏三，值钱一鸡雏三，值钱一问翁、母、雏各几何？问翁、母、雏各几何？意思是：公鸡每只意思是：公鸡每只5 5元、母鸡每只元、母鸡每只3 3元、小鸡元、小鸡3 3只只1 1元，元，用用100100元钱买元钱买100100只鸡，求公鸡、母鸡、小鸡的只数。只鸡，求公鸡、母鸡、小鸡的只数。3-21/60 设鸡翁、鸡母、鸡雏的个数分别为设鸡翁、鸡母、鸡雏的个数分别为x x、y y、z z，根据题意可得，根据题意可得如下方程如下方程组组： 5x5x3y3yz/3z/3100100 x xy yz z100100 1x 1x20, 1y20, 1y33, 3z33, 3z100, z

19、mod 3100, z mod 30 0 测试集合：测试集合：1 1x x20, 120, 1y y3333，z=3,6,9,.,99z=3,6,9,.,99测试条件：测试条件：5x5x3y3yz/3z/3100100 x xy yz z1001003-22/60 巧妙和高效的算法很少来自于穷举法，但基于以下巧妙和高效的算法很少来自于穷举法，但基于以下因素，穷举法仍是一种重要的算法设计策略：因素，穷举法仍是一种重要的算法设计策略： 穷举法几乎可以通用于任何领域的问题求解，可穷举法几乎可以通用于任何领域的问题求解，可能是唯一一种解决所有问题的一般性方法；能是唯一一种解决所有问题的一般性方法； 即

20、使效率低下，仍可用穷举法求解一些小规模的即使效率低下，仍可用穷举法求解一些小规模的问题实例；问题实例； 如果解决的问题实例不多，而穷举法可用一种可如果解决的问题实例不多，而穷举法可用一种可接受的速度对问题求解，那么花时间去设计一个更高效接受的速度对问题求解，那么花时间去设计一个更高效地算法是得不偿失的。地算法是得不偿失的。 思考题思考题 举例说明生活中的穷举法应用。举例说明生活中的穷举法应用。3-23/60二、回溯法二、回溯法 回溯回溯法法是一种选优搜索法，按选优条件向前是一种选优搜索法，按选优条件向前搜索，以达到目标。搜索，以达到目标。在搜索过程中，能进则进，在搜索过程中，能进则进，不能进则

21、退回来，换一条路再试，通过此种方式不能进则退回来，换一条路再试，通过此种方式提高搜索效率，减少不必要的测试。提高搜索效率，减少不必要的测试。回溯法的应用回溯法的应用 迷宫问题迷宫问题 搜索引擎中的网络爬虫搜索引擎中的网络爬虫 八皇后问题八皇后问题3-24/60 案例一案例一 老鼠走迷宫老鼠走迷宫老鼠从迷宫入口出发，任老鼠从迷宫入口出发，任选一条路线向前走，在到选一条路线向前走，在到达一个岔路口时，任选一达一个岔路口时，任选一个路线走下去个路线走下去，如此继，如此继续，直到前面没有路可走续，直到前面没有路可走时，老鼠退回到上一个岔时，老鼠退回到上一个岔路口，重新在没有走过的路口，重新在没有走过的

22、路线中任选一条路线往前路线中任选一条路线往前走。按这种方式走下去，走。按这种方式走下去，直到走出迷宫。直到走出迷宫。 3-25/60 案例二案例二 搜索引擎中的网络爬虫。搜索引擎中的网络爬虫。 搜索引擎搜索引擎是指根据一定的策略、运用特定的计算机程序从是指根据一定的策略、运用特定的计算机程序从互联网上搜集信息，在对信息进行组织和处理后，为用户提供互联网上搜集信息，在对信息进行组织和处理后，为用户提供检索服务，将用户检索相关的信息展示给用户的系统。百度和检索服务，将用户检索相关的信息展示给用户的系统。百度和谷歌等是搜索引擎的代表。谷歌等是搜索引擎的代表。 搜索引擎的组成搜索引擎的组成：下载、索引

23、和查询。：下载、索引和查询。3-26/60网络爬虫网络爬虫：自动下载互联网所有网页。：自动下载互联网所有网页。 网络爬虫原理网络爬虫原理：图的遍历，从图中某一顶点出发访遍图中所有顶图的遍历，从图中某一顶点出发访遍图中所有顶点，且使每个顶点仅被访问一次。点，且使每个顶点仅被访问一次。回溯算法回溯算法：图的深度优先遍历：图的深度优先遍历（广度优先遍历）。广度优先遍历）。深度优先遍历顺序：深度优先遍历顺序：V V1 1,V,V2 2,V,V4 4,V,V8 8,V,V5 5,V,V3 3,V,V6 6,V,V7 73-27/60 案例三案例三 八皇后问题八皇后问题。在。在8 88 8格国际象棋的棋盘

24、格国际象棋的棋盘上摆放八个皇后，使其不能互相攻击，即任意两上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上个皇后都不能处于同一行、同一列或同一斜线上问有多少种摆法？问有多少种摆法？3-28/60 回溯法解八皇后问题思路回溯法解八皇后问题思路：逐行摆放皇后。初始第：逐行摆放皇后。初始第1 1行皇后行皇后放第放第1 1列；摆放第列；摆放第i i行皇后时，从第行皇后时，从第1 1列开始，逐列判定是否与前列开始，逐列判定是否与前i-1i-1行皇后攻击，直到找到一个不攻击的位置，继续第行皇后攻击，直到找到一个不攻击的位置，继续第i+1i+1行的摆行的摆放；若第放；若第

25、i i行无摆放位置，则拿掉该行皇后，回溯至第行无摆放位置，则拿掉该行皇后，回溯至第i-1i-1行，第行，第i-1i-1行皇后从当前位置的下一列开始判定，继续搜索。当第行皇后从当前位置的下一列开始判定，继续搜索。当第1 1行皇行皇后的摆放位置超出棋盘时，全部求解过程结束。后的摆放位置超出棋盘时，全部求解过程结束。(92(92种种) ) 3-29/60 回溯法有通用解法之称，当一个问题没有显而易见的解法回溯法有通用解法之称，当一个问题没有显而易见的解法时，可尝试使用回溯法求解，这实际是与穷举法一致的，因其时，可尝试使用回溯法求解，这实际是与穷举法一致的，因其本质仍是穷举。需要注意，回溯和穷举虽然能

26、解很多问题，但本质仍是穷举。需要注意，回溯和穷举虽然能解很多问题，但其算法效率可能很低。其算法效率可能很低。 回溯法的基本思想是回溯法的基本思想是能进则进，不能进则退能进则进，不能进则退。为了求得问。为了求得问题的解，先选择某一种可能情况向前探索，在探索过程中，一题的解，先选择某一种可能情况向前探索，在探索过程中，一旦发现原来的选择是错误的，就退回一步重新选择，继续向前旦发现原来的选择是错误的，就退回一步重新选择，继续向前探索，如此反复进行，直至得到解或确定该问题无解。探索，如此反复进行，直至得到解或确定该问题无解。 回溯法是求解实际问题的一个重要算法，很多无法使用贪回溯法是求解实际问题的一个

27、重要算法，很多无法使用贪心算法和动态规划算法进行求解的问题，都可以使用回溯算法心算法和动态规划算法进行求解的问题，都可以使用回溯算法进行求解，并且可以保证得到问题的最优解。进行求解，并且可以保证得到问题的最优解。3-30/60三、递归算法三、递归算法 递归递归：直接或间接地调用自身的算法。：直接或间接地调用自身的算法。 递归思想就是用与自身问题相似但规模较小递归思想就是用与自身问题相似但规模较小的问题来描述自己。的问题来描述自己。递归算法的应用递归算法的应用 盗梦空间盗梦空间( (美国影片美国影片) ) 欧几里得算法欧几里得算法 德罗斯特效应德罗斯特效应( (DrosteDroste Effe

28、ct) Effect) 斐波纳契数列斐波纳契数列(Fibonacci(Fibonacci数列数列) )3-31/60 案例一案例一 德罗斯特效应德罗斯特效应。递归的一种视觉形式，。递归的一种视觉形式，它指一张图片的某个部分与整张图片相同，如此它指一张图片的某个部分与整张图片相同，如此产生无限循环。产生无限循环。3-32/60 案例二案例二 12021202年，意大利数学家斐波纳契出版了他的年，意大利数学家斐波纳契出版了他的算盘全书算盘全书。他在书中提出了一个关于兔子繁殖问题：如果一对兔子每月能生他在书中提出了一个关于兔子繁殖问题：如果一对兔子每月能生一对小兔一对小兔( (一雄一雌一雄一雌) )

29、，而每对小兔在它们出生后的第三个月里，而每对小兔在它们出生后的第三个月里，又能开始生一对小兔，假定在不发生死亡的情况下，由一对出生又能开始生一对小兔，假定在不发生死亡的情况下，由一对出生的小兔开始，的小兔开始，5050月后会有多少对兔子？月后会有多少对兔子？分析分析：第一个月只有一对兔子，第二个月仍只有一对兔子，第三：第一个月只有一对兔子，第二个月仍只有一对兔子，第三个月兔子对数为第二个月兔子对数加第一月兔子新生的对数。同个月兔子对数为第二个月兔子对数加第一月兔子新生的对数。同理，第理，第i i个月兔子对数为第个月兔子对数为第i-1i-1月兔子对数加第月兔子对数加第i-2i-2月兔子新生的月兔

30、子新生的对数。即从第一个月开始计算，每月兔子对数依次为：对数。即从第一个月开始计算，每月兔子对数依次为： 1,1,2,3,5,8,13,21,34,55,89,144,233,1,1,2,3,5,8,13,21,34,55,89,144,233,。 22121nFFnFnnn3-33/60兔子繁殖的规律兔子繁殖的规律1 11 10 00 01 12 20 01 10 01 13 31 10 01 12 24 41 11 11 13 35 52 21 12 25 56 63 32 23 38 87 75 53 35 513133-34/60递归过程递归过程F F5 5=F=F4 4+F+F3 3

31、F F4 4=F=F3 3+F+F2 2F F3 3=F=F2 2+F+F1 1F F2 2=1=1F F1 1=1=1F F3 3=1+1=2=1+1=2F F4 4=2+1=3=2+1=3F F5 5=3+2=5=3+2=5回溯阶段回溯阶段递推阶段递推阶段3-35/60FibonacciFibonacci数列递归算法的伪代码描述数列递归算法的伪代码描述：FibonacciFibonacci数列的递归算法数列的递归算法输入：正整数输入：正整数n n输出：输出：FibonacciFibonacci数列的第数列的第n n项项Fib(nFib(n) ) 1 IF n2 1 IF n2 2 2 TH

32、EN RETURN 1 THEN RETURN 1 3 RETURN Fib(n-1)+Fib(n-2) /3 RETURN Fib(n-1)+Fib(n-2) /调用自身调用自身 3-36/60 递归算法的主要优点递归算法的主要优点：结构清晰、可读性强，而：结构清晰、可读性强，而且容易用数学归纳法来证明算法的正确性，因此它为且容易用数学归纳法来证明算法的正确性，因此它为设计算法、调试程序带来了很大方便。设计算法、调试程序带来了很大方便。 递归算法的主要缺点递归算法的主要缺点：递归算法的运行效率相对：递归算法的运行效率相对较低，无论是耗费的计算时间还是占用的存储空间都较低，无论是耗费的计算时间

33、还是占用的存储空间都比非递归算法要多。通常的解决方法是消除递归算法比非递归算法要多。通常的解决方法是消除递归算法中的递归调用，使递归算法转化为非递归算法。中的递归调用，使递归算法转化为非递归算法。3-37/60四、分治法四、分治法 分治算法分治算法：将一个难以直接解决的大问题，分解成一些规：将一个难以直接解决的大问题，分解成一些规模较小的子问题，以便模较小的子问题，以便各个击破，分而治之各个击破，分而治之。如果子问题还比。如果子问题还比较大，可反复使用分治算法，直到最后的子问题可以直接得出较大，可反复使用分治算法，直到最后的子问题可以直接得出它们的结果。由于分治算法的子问题类型常与原来的相同，

34、因它们的结果。由于分治算法的子问题类型常与原来的相同，因而很自然地使用递归算法。而很自然地使用递归算法。分治法的分治法的应用应用国王的婚姻中宰相的策略国王的婚姻中宰相的策略GoogleGoogle的的MapReduceMapReduce技术技术二分查找二分查找用于组织管理和军事等领域用于组织管理和军事等领域3-38/60 案例一案例一 GoogleGoogle的的MapReduceMapReduce技术技术 谷歌在全球有谷歌在全球有3636个数据中心，服务器不计其数。它的三个数据中心，服务器不计其数。它的三大核心技术是：大核心技术是： GFS(GoogleGFS(Google File Sys

35、tem) File System)：专用文件系统；：专用文件系统； BigTableBigTable：分布式数据库系统；：分布式数据库系统； MapReduceMapReduce：并行计算编程模型。：并行计算编程模型。3-39/60 MapReduceMapReduce模型中两项核心操作模型中两项核心操作： Map Map映射；映射；ReduceReduce化简、归约化简、归约MapReduceMapReduce处理大数据过程是由划分、治理、处理大数据过程是由划分、治理、合并三个步骤组成，是分治策略的完美应用。合并三个步骤组成，是分治策略的完美应用。 3-40/60 案例二案例二 二分查找二分

36、查找 常用的二分查找是一个典型的分治算法。常用的二分查找是一个典型的分治算法。 二分查找基本原理二分查找基本原理：用于在：用于在n n个元素的有序序列中查找指个元素的有序序列中查找指定元素定元素e e。将。将n n个元素分成个数大致相同的两半，取个元素分成个数大致相同的两半，取a an/2n/2与欲查与欲查找的找的e e作比较，作比较， 若若e=ae=an/2n/2，则找到，则找到e e，算法终止，算法终止 若若eaeaxan/2n/2，则只需在数组，则只需在数组a a的后半部分继续二分查找的后半部分继续二分查找e e 二分查找每次比较将数据减少一半，也称折半查找。二分查找每次比较将数据减少一

37、半，也称折半查找。 3-41/60二分查找在列表中查找二分查找在列表中查找JohnJohn的计算过程的计算过程 3-42/60 分治策略是解决工作、学习和生活中常见问题的一种思维方分治策略是解决工作、学习和生活中常见问题的一种思维方法，它在组织管理和军事领域得到广泛的应用法，它在组织管理和军事领域得到广泛的应用 例如：某大企业的销售公司，由于其许多产品优质而非常畅例如：某大企业的销售公司，由于其许多产品优质而非常畅销，总部会到各地建立分支机构，这其中就蕴涵着分治思想。销，总部会到各地建立分支机构，这其中就蕴涵着分治思想。 再如：中国革命战争时期经常遇到敌军强大，因此采用再如：中国革命战争时期经

38、常遇到敌军强大，因此采用集中集中优势兵力，逐个击破优势兵力，逐个击破的分治策略往往能产生以弱胜强的优异战果的分治策略往往能产生以弱胜强的优异战果 又如：各种大型体育赛事通常分为初赛和决赛，世界杯足球又如：各种大型体育赛事通常分为初赛和决赛，世界杯足球赛要从报名参赛的赛要从报名参赛的200200多支球队中选出成绩最好的多支球队中选出成绩最好的3232支球队支球队, ,难度难度很大，成本也高。因此通过分区预选赛选出成绩最好的很大，成本也高。因此通过分区预选赛选出成绩最好的3232支球队支球队进入决赛圈，这种做法也包含分治思想并降低了难度和复杂度。进入决赛圈，这种做法也包含分治思想并降低了难度和复杂

39、度。3-43/60五、贪心法五、贪心法 1.1.问题的提出问题的提出 假设有假设有3 3种硬币，它们的面值分别是种硬币，它们的面值分别是1 1元、元、5 5角、角、1 1角。现在角。现在有一个小孩买了价值有一个小孩买了价值6 6元元2 2角的东西，并给售货员角的东西，并给售货员1010元钱。当售元钱。当售货员找给小孩零钱时，希望她找给小孩的硬币数目最少。货员找给小孩零钱时，希望她找给小孩的硬币数目最少。3 33 31 01 03 83 82 2 2 22 2 2 23 2 1 03 2 1 03 8 13 183 8 13 18这种简单地从具有最大面值的币种开始，按递减的顺序这种简单地从具有最

40、大面值的币种开始，按递减的顺序考虑各种币种的方法称为考虑各种币种的方法称为贪心法贪心法，或，或启发式搜索法启发式搜索法。3-44/60 2. 2.贪心算法贪心算法 贪心法的基本思想贪心法的基本思想：将待求解的问题分解成若干个子问：将待求解的问题分解成若干个子问题进行分步求解，且每一步总是做出当前最好的选择，即得题进行分步求解，且每一步总是做出当前最好的选择，即得到局部最优解，再将各个局部最优解整合成问题的解。到局部最优解，再将各个局部最优解整合成问题的解。 贪心法体现了一种贪心法体现了一种快刀斩乱麻快刀斩乱麻的思想，以当前和局部利的思想，以当前和局部利益最大化为导向的问题求解策略。益最大化为导

41、向的问题求解策略。 利用贪心法求解问题的过程：利用贪心法求解问题的过程：分解：将原问题分解为若干个相互独立的阶段；分解：将原问题分解为若干个相互独立的阶段；解决：对每个阶段求局部的最优解，即进行贪心选择解决：对每个阶段求局部的最优解，即进行贪心选择合并：把各个阶段的解合并为原问题的一个可行解。合并：把各个阶段的解合并为原问题的一个可行解。3-45/60利用贪心法对问题进行求解的过程利用贪心法对问题进行求解的过程3-46/60 3. 3.贪心法的应用贪心法的应用 案例一案例一 田忌赛马田忌赛马 战国时期，齐威王与大将田忌赛马，齐威王和田忌各有战国时期，齐威王与大将田忌赛马，齐威王和田忌各有三匹好

42、马：上马、中马与下马。比赛分三次进行，每次赛马三匹好马：上马、中马与下马。比赛分三次进行，每次赛马以千金作赌。由于两者的马力相差无几，而齐威王的马分别以千金作赌。由于两者的马力相差无几，而齐威王的马分别比田忌相应等级的马要好，所以大家都认为田忌必输无疑。比田忌相应等级的马要好，所以大家都认为田忌必输无疑。田忌采纳了门客孙膑的意见，田忌采纳了门客孙膑的意见，用下马对齐威王的上马，用上用下马对齐威王的上马，用上马对齐威王的中马，用中马对马对齐威王的中马，用中马对齐威王的下马，结果田忌以齐威王的下马，结果田忌以比胜齐威王而得千金。比胜齐威王而得千金。3-47/60 将齐王的马、田忌的马均按上、中、下

43、马顺序排列，齐王依将齐王的马、田忌的马均按上、中、下马顺序排列，齐王依次出马，次出马，孙膑的贪心选择策略孙膑的贪心选择策略： 若剩下的最强的马都赢不了齐王剩下的最强的马，选择用若剩下的最强的马都赢不了齐王剩下的最强的马，选择用最差的一匹马对阵齐王最强的马；最差的一匹马对阵齐王最强的马； 若剩下的最强的马可以赢齐王剩下的最强的马，选择用这若剩下的最强的马可以赢齐王剩下的最强的马，选择用这匹马去赢齐王剩下的最强的马；匹马去赢齐王剩下的最强的马； 若剩下的最强的马和齐若剩下的最强的马和齐王剩下的最强的马打平的话，王剩下的最强的马打平的话，可以选择打平或者用最差的马可以选择打平或者用最差的马输掉比赛。

44、输掉比赛。3-48/60 案例二案例二 电缆铺设电缆铺设 假设要在假设要在n n个城市之间铺设光缆个城市之间铺设光缆, ,铺设光缆费铺设光缆费用很高，且各个城市之间铺设光缆的费用不同，用很高，且各个城市之间铺设光缆的费用不同，问如何铺设问如何铺设, ,使得使得n n个城市的任意两个之间都可以个城市的任意两个之间都可以通信，且使铺设光缆的总费用最低？通信，且使铺设光缆的总费用最低？可用图论中的最小生成树求解可用图论中的最小生成树求解求解最小生成树算法是贪心法求解最小生成树算法是贪心法 3-49/60 利用贪心法求解最小生成树，其中一种贪心利用贪心法求解最小生成树，其中一种贪心选择策略是：贪心选择

45、权值最小的边，若与之前选择策略是：贪心选择权值最小的边，若与之前加入的边构成回路，则放弃；否则，加入最小生加入的边构成回路，则放弃；否则，加入最小生成树。成树。电缆铺设的电缆铺设的最小生成树最小生成树3-50/60 贪心算法是最接近于人类日常思维的一种问贪心算法是最接近于人类日常思维的一种问题求解方法，它已在人类工作和生活的各个领域题求解方法，它已在人类工作和生活的各个领域得到广泛的应用。得到广泛的应用。 例如：公司招聘新员工是从一批应聘者中招例如：公司招聘新员工是从一批应聘者中招收最能干的人。收最能干的人。 再如：学校招生是从众多报考者中招收一批再如：学校招生是从众多报考者中招收一批最好的学

46、生。最好的学生。 这种按照某种标准挑选最接近该标准的人或这种按照某种标准挑选最接近该标准的人或物的做法就是贪心算法。物的做法就是贪心算法。 3-51/60六、动态规划六、动态规划 1.1.问题的提出问题的提出动态规划是解决多阶段决策最优化问题的一种方法。动态规划是解决多阶段决策最优化问题的一种方法。 案例一案例一GPSGPS中的最优路径。中的最优路径。全球定位系统全球定位系统GPS(GlobalGPS(Global Positioning System)Positioning System)可以为我们计算出满足各种不同要可以为我们计算出满足各种不同要求的、从出发地到目的地最优路径，可能是花费时

47、间最求的、从出发地到目的地最优路径，可能是花费时间最短，也可能是过路费最少。短，也可能是过路费最少。GPSGPS寻找最优路径的算法就是寻找最优路径的算法就是动态动态规划算法。规划算法。3-52/60 假设计算下图中顶点假设计算下图中顶点0 0到顶点到顶点6 6的最短路径。的最短路径。第第0 0阶段阶段第第1 1阶段阶段第第2 2阶段阶段第第3 3阶段阶段第第4 4阶段阶段3-53/60定义定义costicosti ：从顶点：从顶点0 0到顶点到顶点i i的最短路径。的最短路径。第第0 0阶段：阶段：cost0=0cost0=0第第1 1阶段：阶段：cost1=cost0+4=4cost1=co

48、st0+4=4 cost2=cost0+5=5 cost2=cost0+5=5第第2 2阶段：阶段：cost3=mincost3=mincost0+8cost0+8,cost1+4,cost2+5=8,cost1+4,cost2+5=8第第3 3阶段：阶段：cost4=mincost4=mincost1+6cost1+6,cost3+8=10,cost3+8=10 cost5=mincost5=mincost2+cost2+7 7, ,cost3cost3+9=12+9=12第第4 4阶段：阶段：cost6=mincost6=mincost4+5cost4+5,cost3+9,cost5+4=

49、15,cost3+9,cost5+4=15根据计算，从顶点根据计算，从顶点0 0到顶点到顶点6 6的最短路径值为的最短路径值为1515。从顶点从顶点6 6向前回溯，最短路径为向前回溯，最短路径为01460146。3-54/60 2.2.动态规划算法动态规划算法 动态规划是美国数学家动态规划是美国数学家R.BellmanR.Bellman等人于等人于19511951年在研究多年在研究多阶段决策过程的优化问题时创立的一种解决问题的新方法。阶段决策过程的优化问题时创立的一种解决问题的新方法。 在现实生活中，有一类问题可以将其活动过程分解成若干在现实生活中，有一类问题可以将其活动过程分解成若干个相互联

50、系的阶段，在它的每一阶段都需要作出决策，从而使个相互联系的阶段，在它的每一阶段都需要作出决策，从而使整个过程达到最好的活动效果。这种将一个问题看作是一个前整个过程达到最好的活动效果。这种将一个问题看作是一个前后相互关联且具有链状结构的多阶段过程称为多阶段决策过程后相互关联且具有链状结构的多阶段过程称为多阶段决策过程将解决多阶段决策的最优化的过程称为动态规划算法将解决多阶段决策的最优化的过程称为动态规划算法。3-55/60 动态规划法主要适用于最优化问题的求解动态规划法主要适用于最优化问题的求解：这类问题会有：这类问题会有多种可能的解，每个解都有一个值，而动态规划找出其中最优多种可能的解，每个解