PowerPoint 演示文稿

Size: px

Start display at page:

Download "PowerPoint 演示文稿"

拳公叔
7 years ago
Views:

1 大学计算机计算思维导论南京航空航天大学 2015 年计算机科学与技术学院

2 计算思维导论第 1 章引论第 2 章计算系统的基本思维第 3 章问题求解框架第 5 章数据抽象设计与挖掘第 6 章计算机网络信息网络与网络化社会

3 4.1 排序问题及其算法排序问题基本排序算法 PageRank 排序 : 排序问题的不同思考方法 4.2 递归及递归算法递归 : 用有限的语句定义对象的无限集合递归算法 : 自身调用自身, 高阶调用低阶 4.3 遗传算法 : 计算复杂性与仿生学算法示例可求解与难求解问题遗传算法 : 仿生学算法的简单示例遗传算法暨问题求解算法的进一步探讨

4 4.2 递归及递归算法什么是递归? 从前有座山, 山里有座庙, 庙里有个老和尚, 正在给小和尚讲故事呢! 故事是什么呢?( 从前有座山, 山里有座庙, 庙里有个老和尚, 正在给小和尚讲故事呢! 故事是什么呢?( 从前有座山, 山里有座庙, 庙里有个老和尚, 正在给小和尚讲故事呢! 故事是什么呢?( 从前 )))

5 4.2 递归及递归算法什么是递归?

6 4.2 递归及递归算法什么是递归?

7 4.2 递归及递归算法什么是递归? 在数学与计算机科学中, 是指用函数自身来直接或间接地调用自身函数的方法, 也常用于描述以自相似方法重复事物的过程, 它可以用有限的语句来定义对象的无限集合

8 4.2 递归及递归算法递归的例子 - 例 1 年龄问题 : 有 5 个人坐在一起, 问第 5 个人的年龄, 他说他比第 4 个人大 2 岁 ; 问第 4 个人的年龄, 他说他比第 3 个人大 2 岁 ; 问第 3 个人的年龄, 他说他比第 2 个人大 2 岁 ; 问第 2 个人的年龄, 他说他比第 1 个人大 2 岁 ; 问第 1 个人的年龄, 他说他 10 岁 ; 问第 5 个人的年龄

9 4.2 递归及递归算法递归的例子 - 例 2 阶乘问题 : 求 n! n!=n*(n-1)!

10 4.2 递归及递归算法递归的例子 - 例 3 Fibonacci 数列问题无穷数列 1,1,2,3,5,8,13,21,34,55,,

11 4.2 递归及递归算法递归的例子 - 例 4 汉诺塔问题 :

12 4.2 递归及递归算法递归问题的求解过程要求解递归问题 p(n), 可以将问题一步步简化 ( 递归步骤 ); 要求 p(n) 应先求 p(n-1) 要求 p(n-1) 应先求 p(n-2) 要求 p(n-2) 应先求 p(n-3) 逐步递归, 但问题的性质没有改变 --- 大事化小当问题简化到递归基础 ( 回推点 ) 时, 便开始回推, 直到推出问题 p(n) --- 小事化了过程 : 逐步递归递归基础回推, 最终使递归问题 p(n) 得到解决

13 4.2 递归及递归算法递归问题的求解过程如果是递归基础 ( 回递点 ), 回推不是递归基础 ( 回推点 ), 进一步递归逐步递归回推过程递归基础 ( 回推点 )

14 4.2 递归及递归算法递归问题的求解过程 - 例 1 年龄问题有 5 个人坐在一起, 问第 5 个人的年龄, 他说他比第 4 个人大 2 岁 ; 问第 4 个人的年龄, 他说他比第 3 个人大 2 岁 ; 问第 3 个人的年龄, 他说他比第 2 个人大 2 岁 ; 问第 2 个人的年龄, 他说他比第 1 个人大 2 岁 ; 问第 5 个人的年龄, 他说他 10 岁 ; 问第 5 个人的年龄递归公式 ( 数学模型 ) age(n) = 10 n=1 递归基础 age(n-1)+2 n>1 递归步骤

15 4.2 递归及递归算法年龄问题递归算法 Start Start (in c, out n) c-- 第几个人 n-- 第 c 个人的年龄 "Input a inteder(>=1) : " 第 GET c Yes c=1 No age(c, m) n 10 age(c - 1, m) PUT m + " is the " + c + " th person's age." n m + 2 End End

16 4.2 递归及递归算法递归问题的求解过程例 2 阶乘递归公式 ( 数学模型 ) fac(n) = 1 n=0 或 n=1 n fac(n-1) n>1

17 4.2 递归及递归算法阶乘问题 Start (in n, out m) 求 n 的阶乘 m 递归算法 Start "Input a integer(>=1) : " 第 GET n Yes n=1 No factorial(n, m) m 1 factorial(n - 1, t) PUT "The factorial of "+n+" is "+m+"." m n * t End End

18 4.2 递归及递归算法递归问题的求解过程 - 例 3 Fibonacci 数列无穷数列 1,1,2,3,5,8,13,21,34,55,, 称为 Fibonacci 数列它可以递归地定义如下 : F( n) = F( n 1) F( n 2) n n n = 1 = 2 > 2

19 4.2 递归及递归算法 Fibonacci 数列问题递归算法 Start Start (in n, out m) 求 Fibonacci 数列第 n 项 "Input a integer (>1): " 第 GET n Yes n=1 or n=2 No m 1 fib(n - 1, t1) fib(n, m) fib(n - 2, t2) PUT "fib( "+n+" )="+m+"." m t1 + t2 End End

20 4.2 递归及递归算法递归问题的求解过程 - 例 4 汉诺塔问题递归算法 (n 个盘子从 A 柱通过 B 柱移动到 C 柱 ) if ( n==1 ) // 如果是回推点将 A 柱上最大的盘子移动到 C 柱上 else // 不是回推点 { 将 n-1 个盘子从 X 柱通过 Z 柱移动到 Y 柱上然后把 X 上最下面的盘子放到 Z 上把 n-1 个盘子从 Y 柱通过 X 柱移动到 Z 柱上 }

21 4.2 递归及递归算法

22 4.2 递归及递归算法 Start hannoi 问题递归算法 "Input a integer (>1): " 第 GET n hannoi(n, "A", "B", "C") 调用递归过程输出 n 个盘子的移动步骤 End

23 4.2 递归及递归算法 Start (in n, in one, in two, in three) hannoi 递归算法 Yes n = 1 是否回推点 No PUT one + " - >" + three hannoi(n - 1, one, three, two) n-1 个盘子从 one 通过 three 移至 two PUT one + " - >" + three one 上最后一个盘子移至 three hannoi(n - 1, two, one, three) n-1 个盘子从 two 通达 one 移至 three End

24 4.2 递归及递归算法递归方法的典型特征 : 自身调用自身, 高阶调用低阶来实现定义和求解! 其最有价值之处是构造, 即用有限的语句来定义或描述对象的无限集合 20 世纪 30 年代正是可计算的递归函数理论与图灵机理论等一起为计算理论的建立奠定了基础复杂性评价 : 运行时间较长占用较多的存储空间优点 : 编程容易

25 4.1 排序问题及其算法排序问题基本排序算法 PageRank 排序 : 排序问题的不同思考方法 4.2 递归及递归算法递归 : 用有限的语句定义对象的无限集合递归算法 : 自身调用自身, 高阶调用低阶 4.3 遗传算法 : 计算复杂性与仿生学算法示例可求解与难求解问题遗传算法 : 仿生学算法的简单示例遗传算法暨问题求解算法的进一步探讨

26 现实世界中的各种问题可计算问题 : 计算机在多项式时间内能够求解的问题 ; 难解性问题 : 计算机在多项式时间内不能求解的问题 ; 不可计算问题 : 计算机完全不能求解的问题判断问题能不能计算计算复杂性 : 是问题规模的函数 ( 例 : 旅行商问题 ), 指问题的一种特性, 即利用计算机求解问题的难易性或难易程度计算复杂性的衡量标准 : 一是计算所需的步数或指令条数, 即时间复杂度 ; 二是计算所需的存储空间大小, 即空间复杂度

27 问题的计算复杂性还涉及到求解算法假设同一个问题有两个求解算法, 问题的规模记为 n=60 第一个算法的计算复杂性是 n 3 ( 多项式函数表达 ) 第二个算法的计算复杂性是 3 n ( 指数函数表达 ) 用每秒百万次的计算机来计算第一个算法只要用时 0.2 秒 ; 第二个算法就要用时秒, 也就是年, 相当于 10 亿台每秒百万次的计算机计算一百万年当 n 很大时, 这两个算法的效率差异是很大

28 问题的计算复杂性还涉及到求解算法一个问题如果存在多项式时间计算复杂性的算法, 被认为是计算机能够求解的, 可计算的 ; 一个问题如果没有多项式时间计算复杂性的算法, 被认为是难解性问题但是, 要断定一个问题是否是难解性问题是很困难的一个问题即使长期没有找到多项式时间计算复杂性算法, 也不能保证以后就一定找不到, 更不能依据此证明这个问题不存在多项式时间计算复杂性算法

29 P 类问题和 NP 类问题 P 类问题 : 能找到计算复杂度为多项式级别的确定算法的问题 NP 类问题 (Non-deterministic Polynomial) : 若存在一个算法, 它可以告知某个可能的结果是否正确, 且其复杂性为多项式时间, 这类问题就叫做 NP 类问题 NP-Hard 问题 : 若 NP 中的任何一个问题都可以在多项式时间规约为问题 A, 则称 A 为 NP-Hard 问题 NP-Complete 问题 :NP 问题与 NP-Hard 问题的交集

30 P 类问题和 NP 类问题

31 复杂问题的一种典型求解思想难解问题可用穷举法或称遍历法得到答案, 即对解空间中每一个可能解进行验证, 直到所有解都被验证是否正确, 便能得到精确的结果验证穷举法求解算法的计算复杂性则很可能是指数级别或阶乘级别, 随问题规模增大很快便会变得不可计算难解问题典型求解思想 : 由于求精确解有可能变得不可计算, 因此求取近似解 ( 多项式时间的近似算法 ) 的设计便成为解决这类问题一种可行的途径

32 NP 类问题的一种典型求解思想近似算法所适应的问题是最优化问题, 即要求在满足约束条件的前提下, 使某个目标值达到最大或最小近似算法应满足以下两个基本要求 : (1) 算法的时间复杂性 : 要求算法能在多项式时间内完成即通过近似而不是精确, 来使复杂性为指数级别的计算问题化简为多项式级别的计算问题 (2) 解的近似程度 : 算法的近似解应满足一定的精度, 即达到满意 ( 满足实际应用需求 ) 的程度

33 问题的解若一个问题解的形式为 x, 由 x 的取值空间给定的任何 x 值被称为可能解而一个问题通常有很多个关于可能解的约束, 即不是任何一个 x 值都满足约束, 我们可将满足问题约束的那些 x 值称为可行解而由一个算法在任何一组可行解中求出的最优解被称为是近似解而符合用户期望的近似解被称为是满意解所有可行解中的最优解是问题的最优解可能解集合可行解集合近似解集合满意解集合最优解集合

34 仿生学算法 : 自然界是人类技术工程及重大发明的源泉模仿鱼类的形体造船, 以木桨仿鳍模仿蝙蝠释放出一种超声波接收回声的特性发明了雷达研究蚂蚁的群体行为, 提出了蚁群算法研究了蜂群行为, 提出了蜂群算法等这些算法可广泛用于 NP 问题的求解, 通称为仿生学算法, 或称为进化算法 (Evolutionary Algorithm) 一种典型的进化算法是遗传算法 (Genetic Algorithm), 模仿生物在自然界中的遗传繁衍以及优胜劣汰适者生存的规律而发明

35 生物学中的遗传与进化自然界的生物从其父代继承特性或性状, 这种生命现象被称为遗传通过遗传, 生物可以一代代繁衍, 而繁衍出的后代则随环境的变化, 优胜劣汰, 适者生存, 实现进化

36 个体 A 的染色体染色体 A 的基因片段两个个体基因重组新个体的染色体种群新一代种群个体 B 的染色体染色体 B 的基因片段色体与基因新个体染繁衍后的种群个体对环境的适应性 : 优胜劣汰

37 生物学中的遗传与进化个体 : 生物体, 基本功能单位是细胞 ; 染色体 : 细胞中的一种微小的丝状化合物, 生物体中遗传信息的载体, 由 DNA( 脱氧核糖核酸 ) 的物质所构成,DNA 在染色体中有规则地排列着, 形成一个链状且相互卷曲的双螺旋结构 ; 基因 : 基本的遗传信息, 是染色体的片段, 基本的遗传单位遗传基因在染色体中所占据的位置称为基因座 (Locus); 同一基因座可能有的全部基因称为等位基因 (Allele); 某种生物所特有的基因及其构成形式称为该生物的基因型而该生物在环境中呈现出的相应的性状称为该生物的表现型

38 生物领域基本的遗传方式基因重组方式复制 (Reproduction): 遗传过程中, 父代的遗传物质 DNA 被复制到子代即细胞在分裂时, 遗传物质 DNA 通过复制而转移到新生的细胞中, 新细胞就继承了旧细胞的基因交配 / 杂交 (Crossover): 有性生殖生物在繁殖下一代时, 两个同源染色体之间通过交叉而重组, 亦即在两个染色体的某一相同位置处 DNA 被切断, 其前后两串分别交叉组合而形成两个新的染色体上代染色体切断位置的随机性增加了下一代生物性状的多样性, 例如同一父母的多个不同子女其特性是不同的突变 (Mutation): 在进行细胞复制时, 虽然概率很小, 有可能产生某些复制差错, 但其却使 DNA 发生某种突变, 产生出新的染色体这些新的染色体表现出新的性状

39 生物界的进化优胜劣汰, 适者生存生物的进化是以集团形式共同进行的, 这样的一个团体称为群体 (Population), 或称为种群组成群体的单个生物称为个体 (Individual), 每一个个体对其生存环境都有不同的适应能力, 这种适应能力称为个体的适应度 (Fitness) 依据个体适应度, 淘汰劣质个体, 保留优质个体的过程可被称为选择 (Selection)

40 生物界的进化优胜劣汰, 适者生存 (i) 生物的所有遗传信息都包含在其染色体中, 染色体决定了生物的性状 (ii) 染色体由基因及其有规律的排列所构成, 遗传和进化过程发生在染色体上 ; (iii) 生物的繁殖过程是由其基因的复制过程来完成的 ; (iv) 通过同源染色体之间的交叉或染色体的变异会产生新的物种, 使生物呈现新的性状 (v) 对环境适应性好的基因或染色体比适应性差的基因或染色体有更多的机会遗传到下一代

41 遗传算法 N700 节省 19% 的能耗, 输出提高 30%

42 遗传算法 1.5 米 38% 93%

43 一个简单示例 --- 遗传算法的基本思想多项式函数求最小值 Min F(X) = X 2-19X +20, 其中 X=1,,64 之间的整数此题不难求解其精确解, 为 X=9 或者 X=10 下面用遗传算法求解, 以便理解遗传算法中的概念和基本思想

44 遗传算法求解染色体 : 可能解的基因型, 是 X 的二进制编码, 由于 X 取 1 64 之间的整数, 因此用 6 个二进制位基因型,(X) 10 = (b 6 b 5 b 4 b 3 b 2 b 1 ) 2 个体 : 一个可能解的表现型, 本例中为十进制的 X 种群 : 若干可能解的集合交叉 : 交配 / 杂交, 是新可能解的一种形成方法, 对两个可能解的编码通过交换某些编码位而形成两个新的可能解的遗传操作变异 : 新可能解的一种形成方法, 通过随机地改变一个可能解的编码的某些片段 ( 或基因 ) 而使一个可能解变为一新的可能解的遗传操作适应度 : 可能解接近最优解的一个度量, 本例直接用 F(X) 作为其适应度的度量, 其值越小越接近最优解选择 : 从种群 ( 解集 ) 中依据适应度按某种条件选择某些个体 ( 可能解 )

47 遗传算法为什么可以求解 NP-Complete 问题? 理论上 NP-Complete 问题可通过枚举 - 验证的遍历算法来实现, 即对解空间中的每个可能解都进行验证, 直到所有解都被验证是否正确, 便能得出精确解但遍历整个解空间的计算量会随规模增大而迅速增长, 被认为是不可行的

48 遗传算法为什么可以求解 NP-Complete 问题? 怎样不用遍历整个解空间, 而搜索到满意的近似解呢? 随机搜索方法利用随机数产生需要验证的若干个可能解, 对其进行验证这种方法是建立在概率论的基础上, 所取随机点越多, 则得到最优解的概率也就越大, 然计算量也会增大

49 遗传算法为什么可以求解 NP-Complete 问题? 怎么改进随机点的选取方法呢? 采取导向性随机搜索即对随机点的选取进行导向 ( 导向到接近最优解的方向或路径 ) 使随机点之间有了某种联系, 或者说某种记忆, 虽然随机但却是向接近最优解的方向在努力这可能比完全随机搜索得到的近似解的满意度要好

50 遗传算法为什么可以求解 NP-Complete 问题? 多条路径的导向性随机搜索并行遗传算法可被认为是这样一种导向性群 ( 体 ) 随机搜索算法它通过在初始种群上, 随机地进行选择交叉变异, 形成了多个搜索路径, 而这样的搜索路径再通过计算个体解的适应度并进行评价选择使其导向到接近最优解的方向

51 遗传算法为什么可以求解 NP-Complete 问题? 对于复杂问题, 当没有其他更好算法可使用时, 可选择遗传算法只需要知道解空间, 即可能解的表现型和基因型, 以及关于可能解的适应度函数的计算方法 ( 适应度用于判断一个可能解接近精确解的程度或方向 ), 就可以使用遗传算法遗传算法提供了一种求解复杂系统问题的通用框架

untitled

untitled 1993 79 2010 9 80 180,000 (a) (b) 81 20031,230 2009 10,610 43 2003 2009 1,200 1,000 924 1,061 800 717 600 530 440 400 333 200 123 0 2003 2004 2005 2006 2007 2008 2009 500 2003 15,238 2009 31,4532003 2009