《可视化计算》第章基本算法和策略(B)VIP

第3章基本算法和策略PARTB 可视化计算 2 基本策略 算法设计过程中 发现问题 分析问题及解决问题的思路 步骤与其他学科中的方法是一致的 就是寻找规律计算机科学家在算法研究过程中总结了一些具有普遍意义的算法策略和一些可循的规律 能够帮助我们较快地找到算法 3 基本策略 贪心策略分治策略回溯策略动态规划将递归算法转成非递归实现 4 贪心策略 贪心算法在对问题求解时 总是做出在当前看来是最好的选择 因此它仅仅是某种意义上的局部最优解但在相当广泛范围内 对许多问题它能产生整体最优解或者是整体最优解的近似解 鼠目寸光 是对贪心算法的最好描述 5 贪心算法的特点 以当前情况为基础根据某个偏好原则作最优选择 而不考虑各种可能的整体情况省去了为寻找最优解要穷尽所有可能而必须耗费的大量时间采用自顶向下 以迭代的方法做出相关的贪心选择每做一次贪心选择就将所求问题简化为一个规模更小的子问题 6 贪心算法的特点 通过每一步贪心选择 可得到问题的一个局部最优解但由此得到的全局解却不一定都是是最优的 7 求解数字三角形 有任意一个数字三角形 只能自第一层 顶层 向下行走 且只能走下接的相邻两个结点如第三层的1只能走第四层的3或1问能否找到一条路径 使得路径上的权值之和最大 8 贪心法求解的算法设计 使用文件保存三角形的层数和所有数据描述一个n层的三角形 需要 n n 1 2个数据和一个描述层次的数据 使用二维数组a 保存数字三角形的所有数据二维数组的大小为N N 当然 其中有一半的元素为空值0 9 贪心法求解的算法设计 使用line colum两个变量在二维数组中 作为数字定位的指针 x作为保存权值累计的变量 line的值同时用来控制路径行走的循环 10 流程图 11 分治策略 分治法 DivideandConquer 的基本思想是 将一个较大规模的问题分解为若干个较小规模的子问题 找出子问题的解 然后把各个子问题的解合并 从而得到整个问题的解分治法的分 Divide 是指将较大的问题划分为若干个较小的问题 然后用递归法求解子问题 分治法的治 Conquer 是指从小问题的解来构建大问题的解 12 分治策略 分治法算法中至少包含有两次递归过程 只有一个递归过程的算法在严格意义上不能算作分治算法 13 求用分治法进行幂运算降序求解 在公钥加密的RSA算法中将高次幂运算转换为低次幂运算可以加快加密和解密的计算过程 从而提高了RSA算法的运算速度算法一 采用递推循环的方式实现类似a b的计算过程 算法二 采用递归方式实现分治算法 a b a a b 2 b 偶数a b a a b 1 b 奇数 14 分治法的计算效率 以求520为例 使用分治方法与不使用分治方法的递归算法比较 分治法可以节省近三分之二时间 15 分治方法乘幂运算流程图 16 回溯策略 如果问题的规模 数量 是按指数速度增加的 那么这些算法的能力将受到一定的限制在这种情况下 回溯法 Backtracking 也许是一个更好的选择回溯法也叫穷尽搜索法 Brute ForceSearch 其基本思想是尝试分步地去解决一个问题 17 现有n种物品 对1 i n 已知第i种物品的重量为正整数Wi 价值为正整数Vi 背包能承受的最大载重量为正整数W现要求找出这n种物品的一个子集 使得子集中物品的总重量不超过W且总价值尽量大 0 1背包问题的数学描述 18 设有物件n项 重量为w 5 3 2 价值v 9 7 8 如果背包只能装5斤 求可以放背包的物品最大价值 使用回溯算法 决策树的建树过程为 深度有限 左侧优先 左侧分支不取东西 右侧取当前物件 0 1背包问题求解 3 5 0 2 3 8 2 5 0 1 2 7 1 5 0 1 3 8 i 红色 表示物品的编号aw 绿色 当前可用空间V 蓝色 当前物品价值 1 0 15 3 8 5 0 0 9 2 7 3 16 2 17 19 k元组的概念 元组 tuple 是一种有穷序列 k个元素的序列称为k元组 与集合不同 集合不考虑元素的顺序 但元组中的元素有严格的顺序规定在0 1背包问题中的决策树中的元素和重量为w 5 3 2 价值v 9 7 8 皆为三元组k元组的概念在下一章的有限状态机和图灵机中还会用到 20 0 1背包回溯算法的main子图 建议测试案例从简单的方案开始 21 0 1背包问题 回溯法求解流程图 22 0 1背包回溯算法说明 Maxvalue是一个递归实现的子程序 其中的主要传递参数如下 w 项目物体的重量数组v 项目物体的价值数组length of w 重量数组的长度 也是最后一个物件下标 遍历循环的开始点 直到第一个元素max weight 背包的最大容量 最后的返回值 即背包中物体的价值 23 动态规划 计算Fibonacci数列的第n项 当项数大于2时 F n F n 1 F n 2 如果计算Fibonacci数列第n项 这需要计算从第3项到第n 1项随着n值的增大 递归解法的算法时间复杂性会按几何级数增长这类问题的关键是子问题 sub problem 有重叠 因而分治法并不适合于此类问题的求解 24 动态规划 基本思想是 如果一个较大问题可以被分解为若干个子问题 并且子问题有重叠 那么 可以将每个子问题的解存放到一个表中 然后通过查表来解决问题 减少不必要的重复计算动态规划是20世纪50年代美国数学家RichardBellman提出的在这个术语中 Programming与编程没有关系 而是规划和设计的意思 25 动态规划解Fibonacci数列第n项 26 算法说明 算法递归子程序中的三个传递参数的作用分别是 a 第n项的输入参数b 第n项的结果输出c 计算过程中的中间结果存留数组 也就是一个线形表 在计算过程中 每次计算的结果都保存在c数组中 出现重叠子问题时 直接到c 数组中调取结果 27 动态规划的分析 要消除计算过程中的重复性过程 动态规划是比较好的选择这也是计算机科学中 进行问题求解的重要途径之一由于动态规划需要保存中间计算结果 势必占用较大的内存空间 这点贪心法就完全不同 但时间复杂性则会降低这就是所谓 空间换时间 的策略 28 动态规划的分析 动态规划与贪心法不同的地方 它是一种最优化算法当所有的解空间可以遍历的前提下 利用动态规划的思想保存所有可能的解再通过比较就可以得到最优的解实现原理非常简单 但非常实用 也是计算机科学中最常用的算法策略请设计使用动态规划求解数字三角形 29 将递归算法转成非递归的实现 递归是计算机科学中非常重要的概念 其主要优点是递归的代码量比非递归的代码量少 算法可以设计的非常简洁这是由于递归所使用的方式是函数调用这在计算机算法实现中属于非常自然的栈结构不需要记录位置信息 不需要添加控制语句这些工作都由函数调用的特性自行解决 30 递归算法的弱点 递归算法的执行效率比一般非递归的执行效率要低因为递归的实质既然是函数调用 而函数调用必然要进行线程栈空间的分配 记录每一次函数调用前的状态等工作 开销是比较大的这个情况读者可以自行应用递归实现汉诺塔案例 输入不同的铁饼数 运行并观察 31 非递归算法的特点 非递归算法则不需要进行这些工作 线程栈空间的分配等 因为非递归使用额外的变量记录当前所处的位置信息 以及额外的控制语句递归与非递归调用最主要区别就是在函数调用上 32 递归与非递归策略思想 因此对解决某些问题时 希望用递归算法分析问题 但用非递归算法解决问题这就需要把递归算法转换为非递归算法 33 递归算法转化为非递归算法 有如下三种基本方法 通过分析 跳过分解过程 直接用循环结构的算法实现求解过程 自己用栈模拟系统的运行栈 通过分析只保存必须保存的信息 从而用非递归算法替代递归算法利用栈保存参数 由于栈的后进先出特性吻合递归算法的执行过程 因而可以用非递归算法替代递归算法 34 使用非递归方法实现汉诺塔算法 35 算法说明 将三个柱子分别命名为na1 na2 na3 初始状态 所有的盘子都在na1上 三个柱子按逆时针方向排列成一个圆环其中存在一个规律 当对于规模为n的汉诺塔问题时 1 奇数编号盘子总是移动移动到它后的第2个柱子上 2 偶数编号的盘子总是移动移动到它的后第1个柱子上 36 基本算法策略的讨论 最优化和非最优化 什么不去追求最优化的解 因为存在一个解空间的规模问题 如果在规定时间里 可以找到所有的解 那么选出其中的最优解 但是 如果不可能 有许多O 2n 以上时间复杂度的问题 那么 只好退而求其次 用次优解来解决问题而贪心策略就是求次优解的常用思 37 基本算法策略的讨论 时间换空间 或空间换时间 大部分递归算法编写简单 但运行的时间会随着问题规模的增长而急剧增长而分治方法 一般要花费较多的时间将问题划分成为较小规模 增加了程序的复杂性 递归程序的非传参实现 也是如此但较为复杂的算法 却换来几何级数的运行时间节省 38 基本算法策略的讨论 回溯策略所解的一些问题往往是不能用数学公式去直接求解的它需要通过一个过程 此过程要经过若干个步骤才能完成 每一个步骤又分为若干种可能 同时 为了完成任务 还必须遵守一些规则和约束 对于这样一类问题 一般采用搜索的方法来解决 回溯法就是搜索算法中的一种控制策略 它能够解决许多搜索中问题 39 基本算法策略的讨论 使用递归算法的思路分析问题 但用非递归算法解决问题 使用递归的思路分析问题 可以得到简便 可行但运行效率低下的算法通过非递归将该算法进行再实现 可以得到极高效率的优秀算法 40 小