算法设计与分析1.ppt

算法设计与分析 唐光海2005 2006学年第一学期 本课程主要介绍在实践应用中行之有效的解决非数值数据处理问题的若干种经典的计算机算法 以帮助学生提高运用计算机解决实际问题的能力 教材 邹海明 余祥宣编 计算机算法基础 第2版 华中科技大学出版社 目录 第一章导引与基本数据结构第二章分治法第三章贪心方法第四章动态规划第五章基本检索与周游方法第六章回溯法第七章分枝 限界法第八章NP 难度和NP 完全的问题第九章并行算法 第一章导引与基本数据结构 1 1算法 一 基本概念 算法 解决某一特定问题的一组有穷的 有效的运算规则 1 确定性 每一条规则 每一步 都有确切的含义 2 能行性 每一步都是可行的 可在有限的时间内完成 3 输入 一个算法有零个或多个输入 4 输出 一个算法产生一个或多个输出 5 有穷性 一个算法总是在执行了有穷步的运算之后终止 二 算法的五个基本特点 是否有穷是算法与计算过程的主要区别 由于算法要投入到计算机上运行 所以应考虑算法的效率 考虑的算法应在相当有穷步内终止 三 拟制算法的步骤 2 表示算法 用一种语言描述 如类C语言 1 设计算法 分析问题 考虑问题的解决方法 3 确认算法 证明算法对所有可能的合法输入都能得出正确结果 通常用测试的方法证明 4 分析算法 对算法的时空复杂度作定量的分析 以便了解算法的性能 了解算法的最佳适用环境 在同一问题的多种算法中选择一种最有效的算法 5 测试程序 调试 在抽象数据集上执行程序 以确定是否会产生错误的结果 若有 则修改程序 作时空分布图 用各种给定的数据执行调试没有出错的程序 测定花费的时间与空间 以印证以前所作的分析是否正确 指出实现最优化的有效逻辑位置 四 评价一个算法的标准 2 易读性 通俗易懂 易交流 1 正确性 能正确解决所给定的问题 无语法与逻辑错误 给定一组正确的数据有正确的结果 任意给定一组有刁难性的正确数据都有正确的结果 对所有的正确数据都能得出正确的结果 3 健壮性 容错性 输入非法数据能识别并能作出反应或进行处理 4 易编码 易实现 5 省时 效率高 6 节省空间 1 2分析算法 分析算法的好坏 促使我们去设计一些更好的算法 以收到少花钱多办事 办好事的效果 提高经济效益 假设算法实现时使用的是一台 通用 计算机 每次执行程序中的一条指令 有足够的RAM 在固定时间内可以把一个数从任一单元取出或存入 一 分析算法的前提 1 确定使用哪些运算以及执行这些运算所用的时间 基本运算 加 减 乘 除 比较 赋值 过程调用 每种运算只花费一个固定量的时间 设为一个单位时间 由基本运算的任意长序列组成的运算 时间的长短取决于序列的长短 2 确定能反映出算法在各种情况下工作的数据集 以了解算法的性能 假设数据为n个 二 算法分析方法 1 事后测试 收集算法的执行时间和实际占用空间的统计资料 作出时空分布图 受到的影响 2 事前分析 求出算法的一个时间限界函数 即时间复杂度 数量级 机器环境 语言及相应的编译系统 问题的规模 时钟的准确性 概念 一条语句的时间复杂度 执行它的频率一个算法的时间复杂度 算法中所有语句的执行频率之和 定义 设T n 为算法的执行时间函数 f n 为n的某个简单函数 若存在常数C 0 自然数n0 使得对于任意自然数n n0 均有 T n C f n 则称算法的执行时间数量级为 f n 或称T n 与f n 是同数量级的 或称算法具有 f n 的计算时间 记为T n f n 要确定一个算法的时间数量级是很复杂的 经常不能写成一个简单函数 可用下述定理简化 常用的指数时间算法 2n n nn 定理 T n aknk ak 1nk 1 a1n a0 nk 其中ak 0 算法的分类 a 多项式时间算法 可用多项式来对其计算时间限界的算法b 指数时间算法 计算时间用指数函数限界的算法 常用的多项式时间 1 logn n nlogn n2 n3 1 3描述算法 描述算法的语言要考虑到两个标准 易读 易实现 用类C语言描述 1 4基本数据结构 1 线性表 由n 0 个同类型的数据元素组成的有限序列 记为 a1 a2 an 有顺序存储结构和链式存储结构两种常用方式 栈和队列是两种特殊的线性表 一 栈和队列 2 栈 限定在表的一端 栈顶 进行插入 进栈 操作和删除 出栈 操作的特殊线性表 又称后进先出表 设置一个栈顶指针指向栈的顶部 1 顺序栈 typedefstructnode Elemtypestack m inttop STACK STACKs 进栈 if s top m 1 printf 栈满 else s top s stack s top x return s 出栈 if s top 1 printf 栈空 else y s stack s top s top return s 2 链栈 typedefstructnode Elemtypedata structnode link STACK STACK top 进栈 p STACK malloc sizeof STACK p data x p link top top p return top 出栈 if top NULL printf 栈空 else y top data p top top top link free p return top 3 队列 限定在表的一端 队尾 进行插入 入队列 操作 另一端 队首 进行删除 出队列 操作的特殊线性表 又称先进先出表 设置两个指针 一个队首指针指向队列的第一个元素的前一个位置 一个队尾指针指向队列的最后一个元素的位置 typedefstructsqueue Elemtypea m intfront rear SQUEUE SQUEUEQ 1 顺序队列 入队列 if Q rear 1 m Q front printf 队满 else Q rear Q rear 1 m Q a Q rear x return Q 出队列 if Q rear Q front printf 队空 else y Q a Q front 1 m Q front Q front 1 m return s 2 链队列 typedefstructnode Elemtypedata structnode link NODE typedefstructqueue NODE front rear QUEUE QUEUEQ 入队列 p NODE malloc sizeof NODE p data x p link NULL Q rear link p Q rear p return Q 出队列 if Q rear Q front printf 队空 else p Q front link y p data Q front link p link free p return Q 二 树型结构 树 一个或多个结点组成的有限集合 由一个唯一的称为根的结点和若干个互不相交的称为根的子树的子集合组成 结点的度 分支结点 叶结点 树的度 父结点 子结点 结点的层次 树的深度 森林 树的存储结构 见P17图1 12 图1 13 1 二叉树 1 定义 由n 0 个结点组成的有限集合 当n 0时 称为空二叉树 n 0时 由一个唯一的称为根的结点和两个互不相交的分别称为根的左 右子树的子集合组成 2 性质 一棵二叉树第i层最多有2i 1个结点 深度为k的二叉树最多有2k 1个结点 满二叉树 深度为k有2k 1个结点的二叉树 完全二叉树 除最下面一层外都是满的 最下一层的结点都集中在左边的二叉树 有n个结点的完全二叉树中 对于编号为i的结点 当i 1时 i的父亲为 i 2 否则无父亲 当2i n时 i的左孩子为2i 否则无左孩子 当2i 1 n时 i的右孩子为2i 1 否则无右孩子 4 两种常用的二叉树 堆 最大堆 每个结点的值都不小于其左右孩子的值的完全二叉树 最小堆 每个结点的值都不大于其左右孩子的值的完全二叉树 二分检索树 每个结点的值都大于其左子树中所有结点的值 小于其右子树中所有结点的值的二叉树 2 树转换成二叉树方法 加边 加兄弟之间的边 减边 减去每个结点与第一个孩子结点之外的孩子结点的边 旋转 顺时针旋转450 三 集合的树表示和不相交集合的合并 用树表示集合 集合中的每个结点均有一个指向其父结点的信息 用序号代表结点 parent i 代表结点i的双亲信息 根结点的父结点为0 1 简单的合并与查找1 合并 合并根为i j的两棵树intU inti intj parent i j return j 时间复杂度为O 1 2 查找 找i所在的树的根intF inti intj j i while parent j 0 j parent j return j 比较次数为结点i所在的层次 例 若有n个集合 Si i 1 i n 即n棵均只有一个结点的树构成的森林 依次执行U 1 2 F 1 U 2 3 F 1 F 1 U n 1 n 时间为1 2 1 3 n 1 1 n 1 2 3 n 1 n 1 n n 1 2 1 O n2 得到的树为 2 使用加权规则的合并算法1 加权规则 若树i的结点数少于树j的结点数 则j成为i的双亲 否则i成为j的双亲 即结点数多的树的根为合并后的树的根 根结点的parent值为结点个数的相反数 2 算法 intUNION inti intj intx x parent i parent j if parent i parent j parent i j parent j x return j else parent j i parent i x return i 3 使用压缩规则的查找算法1 压缩规则 若j是由i到它的根的路径上的一个结点 则置parent j root i 2 算法 intFIND inti intj k t j i while parent j 0 j parent j k i while k j t parent k parent k j k t return j 四 图 1 概念 图G V E 其中 V 顶点集E V中的顶点之间的边集 有向图 无向图 子图网 有向网 无向网邻接顶点的度 入度 出度路径 简单路径 环 简单环 连通图 连通子图 连通分量强连通图 强连通子图 强连通分量森林 2 图的存储结构 1 邻接矩阵 适用于稠密图2 邻接表 适用于稀疏图 1 5递归与消去递归 递归的优点 算法简单 正确性容易证明 缺点 实现的代价高 时间 空间 一 递归的例子 斐波那契数列 0 1 1 2 3 5 8 13 定义为 F0 0 F1 1 Fi Fi 1 Fi 2i 1 算法 intF intn if n 0 return 0 elseif n 1 return 1 elsereturn F n 1 F n 2 算法 intGCD inta intb if b 0 return a elsereturn GCD b a b 检索 在A 0 A n 1 中找x查找成功返回x在A中的位置 否则返回 1 算法 intsearch inti intj Elemtypex ElemtypeA if i j return 1 elseif A i x return i elsereturn search i 1 j x A 调用语句为search 0 n 1 x A 二 消去递归的方法 1 迭代法 一般地 受限于一个条件B的递归程序P可以表示为基语句Si 不包含P 和P自身的组合 Si P 递归算法的方案为P ifB Si P 可改写成P x x0 whileBS 其中S不包含P 方法 利用题给条件求出第1 i个值作为初值赋给局部变量A1 Ai 给循环变量赋初值 确定循环终值 重复下列步骤 直到循环变量的值超过终值为止 把利用A1 Ai的值按题给条件求出的值赋给中间变量T 将T Ai A2的值依次赋给Ai A1 给循环变量增值 此时的局部变量Ai的值即为所求 例 intF intn inti f1 f2 f if n 0 f 0 elseif n 1 f 1 else f1 0 f2 1 i 2 while i n f f1 f2 f1 f2 f2 f i return f 2 消去尾递归 递归调用语句是过程或函数的最后一条执行语句的情况 对于尾递归 从调用返回后不需再执行别的语句 返回地址在过程或函数的末尾 外层的实际参数值和返回地址不需要再用 所以不必保存 但编译程序不识别尾递归 仍会把各层的实际参数值和返回地址保存下来而浪费了存储单元 为节省存储单元 可利用循环语句消去尾递归 方法 将最外层实际参数值赋给局部变量 重复下列步骤 直到原递归条件不满足为止 执行语句体 将向里一层的实际参数值赋给局部变量 其中 语句体为原递归算法中除递归调用语句外的所有可执行语句 3 利用堆栈消去递归 这种情况下 当向里一层递归运算执行完后返回原调用层时 还要继续执行后面的执行语句 所以 递归调用进入内层时 外层和各形式参数相对应的实参和返回地址要记录下来 以备返回时用 用栈实现 方法 设置栈 将最外层的所有实参值 局部变量及返回地址进栈 重复下列步骤 直到栈为空为止 执行语句体1 当要进行递归调用时 将栈顶指针加1 将本次递归调用的所有实参值 局部变量及返回地址进栈 然后返 执行 否则执行 执行语句体2 若栈非空 则将栈顶元素出栈 将其值赋给参变量与局部变量 将栈顶指针减1 转至本次返回地址执行 即转 执行 其中 语句体1与语句体2分别为递归调用语句前 后的所有可执行语句 第二章分治法 2 1一般方法 将整个问题分成若干个同类型的小问题分而治之 抽象化描述算法 函数类型DANDC intp intq if small p q return G p q else m DIVIDE p q return COMBINE DANDC p q DANDC m 1 q 2 2二分检索 输入n A n x 在A 0 A n 1 中找x的位置 若找到则返回x在数组A中的位置 即下标 若找不到 则返回 1 一 二分检索算法 在数组A l A h 中找x 先找中点A m 若A m x 则m为所求 若A m x 则在A l A m 1 中找x intBINSRCH ElemtypeA intn Elemtypex intj m l h j 1 l 0 h n 1 whle lA m l m 1 else j m l h 1 return j 例 P39例2 1 用二叉树描述算法 每个内结点表示一次元素比较 用圆形结点表示 每个外结点表示一种不成功检索的情况 用方结点表示 二分检索时间 最好平均最坏成功的检索 1 logn logn 不成功的检索 logn logn logn 二 每次循环只用一次比较的二分检索 intBINSRCH1 ElemtypeA intn Elemtypex intj m l h j 1 l 0 h n h总比可能的最大下标大1 whle l h 1 m l h 2 if x A m h m elsel m if x A l j l elsej 0 return j 此算法保证每次循环只需一次比较 将A 0 A n 分成A 0 A m 和A m A n 两部分 但当x A m 时还需继续循环 对应的检索树形如B 树 所以 不论什么情况都要等循环结束后才能判定x是否在A中 所以 所有情况的时间复杂度均为 logn 三 以比较为基础检索的时间下界 只允许进行元素间的比较而不允许对它们实施运算 在这种条件下设计的算法称为以比较为基础的算法 以比较为基础的检索算法对应一棵比较树 二叉树 树的高度为比较的最大次数 当比较树每个结点为中点时 树的高度最低 为 logn 1 即比较次数 时间 最小 结论 二分检索是解决检索问题的最优的最坏情况算法 2 3找最大最小元素 在A 0 A n 1 中找最大最小元素 一 直接算法 voidstraitmaxmin ElemtypeA intn Elemtype max Elemtype min inti max A 0 min A 0 for i 1 i max max A i elseif A i min min A i 比较次数为 最好最坏平均n 12 n 1 3 n 1 2 二 分治策略算法 voidMAXMIN ElemtypeA inti intj Elemtype max Elemtype min intm Elemtype gmax gmin hmax hmin if i j 1 if A i hmax max gmax else max hmax if gmin hmin min gmin else min hmin 两个算法平均时间基本相同 而MAXMIN算法要大量进出栈的开销 因而会更慢 三 结论 2 若A的元素间的比较远比整数间的比较代价高 则分治方法会产生效率较高 最优 的算法 反之 会得到一个效率较低的算法 所以 分治策略只能看成是一个较好的然而并不是总能成功的算法设计指导 2 4归并分类 voidMergesort ElemtypeA intl inth intm if l h m l h 2 Mergesort A l m Mergesort A m 1 h Merge A l m h 一 归并分类算法 voidMerge ElemtypeA intl intm inth ElemtypeB max inti j k t i l j m 1 k l while i m 例 P48例2 3 算法的不足之处 当n 2时还要递归调用 浪费时间 附加空间为 n 二 改进的归并分类算法 voidMergesort1 ElemtypeA intl inth int p intm q r if h l 1 16 Insertionsort1 A l h p else m l h 2 Mergesort1 A l m q Mergesort1 A m 1 h r Merge1 A q r p voidMerge1 ElemtypeA int q int r int p inti j k i q j r k 0 while i 0 其中 link数组为全程数组 初值全为0 voidInsertionsort1 ElemtypeA intl inth int p inti j k for i l i h i j 0 k link j while k 0 三 结论以比较为基础的分类算法的最坏情况时间下界为 nlogn 归并分类算法是最坏情况的最优算法 例 P51例2 4 改进算法的时间复杂度仍为 nlogn 快速分类又称为分区交换分类 其基本思想是 首先将待分类数据序列中的所有数据作为当前待分类区域 从中任选取一个数据 比如第一个 并以该数据为基准 从位于待分类数据序列左右两端开始 逐渐向中间靠拢 交替与基准数据进行比较 交换 每次比较 若遇右侧数据小于基准数据 则将其与基准数据交换 使其移到基准数据的左侧 若遇左侧数据大于基准值 则将其与基准数据交换 使其移至基准数据的右侧 2 5快速分类 一 快速分类算法 1 快速分类的基本思想 最后让基准数据到达它的最终位置 此时 基准数据将待分类数据分成了左右两个区域 位于基准数据左侧的数据都小于或等于基准数据 位于基准数据右侧的所有数据都大于或等于基准数据 这就是一趟快速分类 或称为一次划分 然后分别对左右两个新的待分类区域 重复上述一趟快速分类的过程 其结果分别让左右两个区域中的基准数据都到达它们的最终位置 同时将待分类数据序列分成更小的待分类区域 再次重复对每个区域进行一趟快速分类 直到每个区域只有一个数据为止 此时所有的数据都到达了它的最终位置 即所有待分类数据按升序排列 至此分类结束 2 算法 1 划分算法 intpartition intp intq inti j Elemtypev i p j q v a i while i j while i j 2 快速分类算法voidquicksort intp intq intm if p q m partition p q quicksort p m 1 对左侧分区域进行快速排序 quicksort m 1 q 对右侧分区域进行快速排序 3 例 Vk1k2k3k4k5k6 Vk1k2k3 43 28152128 28 Vk1k2 Vk5k6 151521 二 快速分类算法时间复杂度分析 2 6选择问题 在A 0 A n 1 中找第k小元素 利用划分算法求出划分元素所在位置m 若k m 1 则A m 为第k小元素 若km 1 则第k小元素在A m 1 A n 1 中 继续在A m 1 A n 1 中找第k m 1小元素 一 选择问题算法 1 算法intselect ElemtypeA intn intk intp q m p 0 q n 1 while p q m partition p q if k m 1 return m 1 elseif k m 1 q m 1 elsep m 1 2 时间复杂度 二 最坏情况时间为 n 选择算法 二次取中值法 2 使用二次取中值规则的选择算法的说明性描述见P60算法2 16P62算法2 17 第三章贪心方法 3 1一般方法 问题 集合 一 概念 约束条件 可行解 最优解 次优解 满足 目标函数 取极值 贪心方法 是一种改进了的分级处理方法 首先根据题意选取一种量度标准 然后按这种量度标准对这n个输入排序 并按序一次输入一个量 如果这个输入和当前已构成在这种量度意义下的部分最优解加在一起不能产生一个可行解 则不把此输入加到这部分解中 这种能够得到某种量度意义下的最优解的分级处理方法称为贪心方法 核心 选择能产生问题最优解的最优量度标准 二 算法 贪心方法的抽象化控制 函数类型GREEDY ElemtypeA intn solution for i 1 i n i x SELECT A ifFEASIBLE solution x solution UNION solution x return solution 3 2背包问题 一 问题 已知有n种物品和一个可容纳M重量的背包 每种物品i的重量为wi 假设将物品i的一部分xi放入背包就会产生pixi的效益 0 xi 1 pi 0 如何装载背包使得装入背包内的物品产生最大的效益 可行解 x1 x2 xn 二 例 例3 1考虑下列情况的背包问题 n 3 M 20 p1 p2 p3 25 24 15 w1 w2 w3 18 15 10 其中的四个可行解为 x1 x2 x3 wixi pixi 1 2 1 3 1 4 16 524 25 1 2 15 0 2028 2 0 2 3 1 2031 0 1 1 2 2031 5 三 量度标准的选择 每一次装入的物品应使它占用的每一单位容量获得当前最大的单位效益 量度标准 每次装入要使得累计效益值与所占容量的比值有最多的增加 第一次 或最少的减少 第二次及以后的装入 方法 按pi wi的非增次序装入 四 结论 按pi wi的非增次序装入可使得 pixi取得最大值 即可得最优解 五 算法voidGREEDY KNAPSACK intP intW intM intX intn floatPW max intcu i for i 1 i n i PW i P i W i quicksort1 PW 1 n 将PW数组按非增次序排列 for i 1 icu break X i 1 cu cu W i if i n X i cu W i 3 3带有限期的作业排序 一 问题 约束条件 被选中的作业均能在其截止期限内完成 可行解 n个作业中满足约束条件的作业组成的子集J 二 例 例3 2n 4 p1 p2 p3 p4 100 10 15 20 d1 d2 d3 d4 2 1 2 1 可行解为 J处理顺序效益值 1 1100 2 210 3 315 4 420 1 2 2 1110 1 3 3 1或3 1115 1 4 4 1120 2 3 2 325 3 4 4 335 三 量度标准的选择 J 1 for i 2 i n i if J i 的所有作业都能在它们的截止期限前完成 J J i 四 抽象化描述算法P71算法3 3 五 定理 定理3 2算法3 3所描述的贪心方法对于作业排序问题总是得到一个最优解 定理3 3设J是k个作业的集合 i1i2 ik是J中作业的一种排列 它使得di1 di2 dik J是一个可行解 当且仅当J中的作业可以按照 的次序而不违反任何一个期限的情况来处理 定理3 3给我们启示 在判断J是否是一个可行解时 只要将J中的作业按截止期限非降次序排列后J中的作业是否都能在其截止期限内完成即可 六 算法带有限期和效益的单位时间的作业排序贪心算法 voidJS intd intJ intn int k inti j r for i 0 id i 七 一种更快的作业排序算法 如果J是作业的可行子集 则使用下列规则来确定这些作业中的每一个作业的处理时间 若还没给作业i分配处理时间 则分配给它时间片 1 其中 是使得1 di的最大整数 且 1 是空的 此规则就是尽可能地推迟对作业i的处理 在将作业一个一个地装配到J中时 不必为接纳新作业而去移动J中那些已分配了时间片的作业 若正被考虑的新作业不存在像上面那样定义的 这个作业就不能计入J 1 例设n 5 p1 p2 p3 p4 p5 20 15 10 5 1 d1 d2 d3 d4 d5 2 2 1 3 3 使用上述可行性规则得J已分配的时间片正被考虑的作业动作 无1分配 1 2 1 1 2 2分配 0 1 1 2 0 1 1 2 3不适合 舍弃 1 2 0 1 1 2 4分配 2 3 1 2 4 0 1 1 2 2 3 5不适合 舍弃最优解为J 1 2 4 由于只有n个作业且每个作业花费一个单位时间 故只需考虑这样一些时间片 i 1 i 1 i b 其中b min n max di 为简单起见 用i来表示时间片 i 1 i 这n个作业的期限值只能是 1 2 b 中的某些 或全部 元素 把这b个期限值分成一些集合 对于任一期限值i 设ni是使得nj i的最大整数且是空的时间片 即所要处理的作业的期限值如果是i 则当前可分配的最接近的时间片是ni 为避免极端情况 引进一个虚构的期限值0和时间片 1 0 当ni nj时 期限值i和j在同一个集合中 显然 若i j 则i i 1 j都在同一个集合中 作出一些以期限值为元素的集合 且使同一个集合中的元素都有一个当前共同可用的最接近的空时间片 对于每个期限值i 0 i b 用F i 表示当前最接近的空时间片 即F i ni 使用树表示集合 最初 这b 1个期限值最接近的时间片是F i i 0 i b 有b 1个集合与这b 1个期限值相对应 如果要调度具有期限d的作业 则寻找包含期限值min n d 的那个根j 若F j 0 则F j 是最接近的空时间片 在使用了这一时间片后 其根j的集合要与包含期限值F j 1的集合合并 2 算法voidFJS intd intn intb intJ int k inti j l for i 0 i n i F i i k 0 for i 1 i n i j FIND min n d i if F j 0 k J k i l FIND F j 1 j UNION l j F j F l 3 例P75例3 4 4 时间分析最多执行2n次FIND n次UNION最少执行n次FIND 0次UNION 最坏时间为O n O 2n 2n n 1 O n 最好时间为O n O n n 1 O n 3 4最优归并模式 一 问题 约束条件 无 可行解 任一次序归并得到的归并树 归并n个文件x1 x2 xn用外结点表示原始文件 用内结点表示归并后的文件 则得到一棵归并树 二 例 q1 q2 q3 q4 q5 20 30 10 5 30 对应归并树为 q1 q2 q3 q4 q5 20 30 10 5 30 三 量度标准的选择 BirtreeTREE Birtree L intn inti Birtree T for i 1 ilchild LEAST L 在森林L中找根的权值最小的树 T rchild LEAST L T data T lchild data T rchild data INSERT L T 将树T插入到森森L中 return LEAST L 四 算法 定理3 4若L是最初n 1棵包含单个结点的树构成的森林 这些树依次有权值为q1 q2 qn 则算法TREE对于具有这些长度的n个文件生成一棵最优的二叉归并树 五 定理 若用k路归并 则每次选取k棵具有最小长度的子树进行归并 要求最初的文件数n满足条件 n k 1 1否则要补充若干个长度为0的文件使其满足条件 3 5最小生成树 一 问题 求由n个结点组成的图G V E 的最小生成树T V E 设图G中有m条边 每条边 i j 上的权值为Cij 约束条件 V T V G 且T是连通的且有最少的边数 可行解 由n个结点n 1条边组成的树 生成树 二 量度标准的选择 以目标函数作为量度标准 每次选择使得迄今为止所计入的边的成本之和有最小的增量的那条边 三 prim算法 使得迄今为止所选择的边的集合A构成一棵树 将要计入到A中的下一条边 u v 是一条不在A中且使得A u v 也是一棵树的最小成本的边 算法3 7prim算法 voidprim intCOST intn intT intmincost inti j k min t NEAR mincost 0 for i 2 i n i NEAR i 1 NEAR 1 0 for i 1 i n i min MAX t 0 for j 1 j n j if NEAR j 0 设t是NEAR j 0且COST j NEAR j 最小的下标 T i 1 t T i 2 NEAR t mincost mincost COST t NEAR t NEAR t 0 for k 1 kCOST k t NEAR k t if mincost MAX printf nospanningtree n 考察的边依次为 1 2 被选中将2加入V T 中 2 5 被选中将5加入V T 中 2 3 被选中将3加入V T 中 1 4 被选中将4加入V T 中 5 7 被选中将7加入V T 中 7 8 被选中将8加入V T 中 3 6 被选中将6加入V T 中 将1加入V T 中 例 四 kruskal算法 按图中边的成本的非降次序来考虑 对于生成树迄今为止所选择的边的集合T 应使得它完成后的T有可能成为一棵树 算法3 8kruskal最小生成树算法的概略描述 T while T的边少于n 1条 从E中选取一条最小成本的边 u v 从E中删去 u v if u v 在T中不生成环 将 u v 加到Telse舍弃 u v 算法3 9kruskal算法voidkruskal intCOST intn intT int mincost inti j k p max for i 1 i n i p i 1 mincost 0 i 0 while i n 1 从E中选取一条最小成本的边 u v 且从E中删去 u v j FIND u k FIND v if j k i T i 1 u T i 2 v mincost mincost COST u v UNIOU j k if i n 1 printf nospanningtree n 考察的边依次为 1 2 被选中 2 5 被选中 2 3 被选中 1 4 被选中 5 6 不被选中 5 7 被选中 7 8 被选中 3 6 被选中 例 3 6单源点最短路径 一 问题 设有一个含有n个结点e条边的无向图G V E 每条边上的代价为COST i j 求由G中某个指定结点到其它各个结点的最短路径长度和最短路径 约束条件 从v0出发可到达vt 即有路径v0 vi1 vim vt 可行解 v0vi1 vimvt是v0到vt的路径 目标函数 t COST 0 i1 COST i1 i2 COST im t 最优解 使得 t取最小值的路径v0vi1 vimvt 二 量度标准的选择 用迄今为止已生成的所有路径长度之和作为量度 即 t 每构造一条最短路径应使 t有最小的增量 按最短路径长度的非降次序来求 假设已生成i条最短路径 则下面要构造的路径是下一条最短的最短长度路径 设源点为t 设S表示已生成最短路径的结点 包括源点t 构成的集合 设D i 为从源点t出发只经过S中的点到达i的最短路径长度 设P i 为从源点t出发只经过S中的点到达i的最短路径中i的前驱结点 当S包含图中所有结点时 D i 即为从源点t出发到达i的最短路径长度 P i 即为从源点t出发到达i的最短路径中i的前驱结点 三 算法 重复以下过程n 1次 算法3 10voidSHORTEST PATHS inta intn intt intD intP intS m i j min for i 1 i n i S i 0 D i a t i if a t i MAX P i t elseP i 0 S t 1 for k 1 kD j a j i D i D j a j i P i j for i 1 i n i if D i MAX printf d d D i i j P i while j t printf d j j P j printf d n j elseprintf 1到 d nopath n i 算法时间复杂度为O n2 SjD P 1 3 2 5 4 601510503060131514 1 3 2 5 4660131514 1 3 2 545090131515 1 3 256030100131311 1 32156030100131311 130 10 30100101011 第四章动态规划 4 1一般方法 多阶段决策问题 活动过程可以分为若干个阶段 而且在每一个阶段i后的行为仅依赖于i阶段的过程状态 而与i阶段之前的过程如何到达这种状态的方式无关 这样的过程就构成一个多阶段决策过程 在多阶段决策过程的每一阶段 都可能有多种可供选择的决策 但必须从中选取一种决策 一旦各个阶段的决策选定之后 就构成了解决这一问题的一个决策序列 决策序列的不同所导致的问题的结果也不同 动态规划的目标就是要在所有容许选择的决策序列中选取一种会获得问题最优解的决策序列 即最优决策序列 动态规划 动态规划是一种减少枚举量的方法 它利用了最优决策序列具有如下特点 无论过程的初始状态和初始决策是什么 其余的决策必须相对初始决策所产生的状态构成一个最优决策序列 解决问题的关键 建立各阶段间的递推关系式 设要作n次决策x1 x2 xn 一 向前处理法 从最后阶段开始 以逐渐向前递推的方式列出求前一阶段决策值的递推表达式 即根据xi 1 xn的那些最优决策序列来列出求xi的决策值的关系式 二 向后处理法 从第一阶段开始 以逐渐向后递推的方式列出求后一阶段决策值的递推表达式 即根据x1 xi 1的那些最优决策序列来列出求xi的决策值的关系式 4 2多段图 一 向前处理法 设P i j 为Vi中结点j到汇点t的最小成本路径 cost i j 为这条路径的成本 D i j 为对j作的决策 D j 为使得cost l c j l 取最小值的点l 设D j 为使得cost l c j l 取最小值的点l 算法 voidFGRAPH intc intk intn intP intcost D j r l min cost n 0 for j n 1 j 1 j min MAX for r j 1 r n r if c j r cost r min min c j r cost r l r cost j c j l cost l D j l P 1 1 P k n for j 2 j k j P j D P j 1 二 向后处理法 设BP i j 为源点s到Vi中结点j的最小成本路径 Bcost i j 为这条路径的成本 D i j 为对j作的决策 设D j 为使得Bcost l c l j 取最小值的点l 设D j 为使得Bcost l c j l 取最小值的点l 算法 voidBGRAPH intc intk intn intP intBcost D j r l min Bcost 1 0 for j 2 j 1 r if c r j Bcost r 1 j P j D P j 1 4 3每对结点之间的最短路径 一 问题 在有n个结点的图G V E 中求每对结点i与j之间的最短路径长度和最短路径 设cost i j 表示边 i j 的长度 对于任意两个点i和j 先决策哪一个结点是i到j的路径上具有最大编号的中间结点k 然后求由i到k和由k到j这两条最短路径 设图的邻接矩阵为cost n 1 n 1 设A k i j 表示顶点i到顶点j的经过不大于k的顶点的最短路径长度 设P k i j 表示顶点i到顶点j的经过不大于k的顶点的最短路径中j的前驱顶点 则A n i j 表示顶点i到顶点j的最短路径长度 P n i j 表示顶点i到顶点j的最短路径中j的前驱顶点 算法voidALL PATHS intcost intn intA intP inti j k for i 1 i n i for j 1 j n j A i j cost i j if cost i j MAX P i j i elseP i j 0 for k 1 kA i k A k j A i j A i k A k j P i j P k j 算法时间复杂度为O n3 4 4最优二分检索树 一 问题 设有n个关键字a1 a2 an 设P i 是对ai检索的概率 Q i 是检索x ai x ai 的概率 0 i n 求使得 1 式取最小值的二分检索树T 二 方法对于这些ai决策出将其中的哪一个作为T的根结点 若选ak为T的根结点 则a1 ak 1 及E0 Ek 1 在左子树中 ak 1 an 及Ek En 在右子树中 设c i j 表示包含ai 1 aj和Ei Ej的最优二分检索树的成本 则所要求的最优二分检索树的成本为c 0 n c 0 n min cost T 若T是最优二分检索树 则其左 右子树也是最优二分检索树 即若cost T c 0 n 则cost L c 0 k 1 cost R c k n 其中k为使得cost T 即 2 式 取最小值的k 设R i j 为使得 3 式取最小值的k 对 3 式依次就j i j i 1 j i 2 j i n计算c i j R i j 则R 0 n 即为T的根 设为k 同理可知左子树的根为R 0 k 1 右子树的根为R k n 利用上述推理依次求出各子树的根 即各级决策值 于是得到最优二分检索树 三 例 P101例4 10 四 算法voidOBST intP intQ intn intc intw intR inti j k t m min for i 0 i n i w i i Q i c i i 0 R i i 0 w i i 1 Q i Q i 1 P i 1 c i i 1 Q i Q i 1 P i 1 R i i 1 i 1 w n n Q n n c n n 0 R n n 0 for m 2 m n m for i 0 i n m i j i m w i j w i j 1 P j Q j min MAX for t R i j 1 t R i 1 j t if c i t 1 c t j min min c i t 1 c t j k t c i j w i j c i k 1 c k j R i j k 已知有n种物品和一个可容纳M重量的背包 每种物品i的重量为wi 对任意一种物品或者全部装入背包或者全部不装 若将物品i放入背包就会产生pi的效益 pi 0 如何装载背包使得装入背包内的物品产生最大的效益 4 50 1背包问题 一 问题 二 例 例 考虑以下情况的背包问题 n 3 w1 w2 w3 2 3 4 p1 p2 p3 1 2 5 和M 6 所以背包问题KNAP 1 3 6 的最优解为6 x1 x2 x3 1 0 1 三 方法 上例可由P104图4 10表示从图中可知 每个fi由一些序偶 Pj Wj 组成的集合说明 其中Wj是使fi在其处产生一次阶跃 跳跃 的x值 Pj fi Wj P0 W0 0 0 设Si 1是fi 1的所有序偶的集合 S1i是fi 1 X wi pi的所有序偶的集合 则S1i P W P pi W wi Si 1 Si是Si 1与S1i在支配规则下的合并 支配规则 若Si 1和S1i之一有序偶 Pj Wj 另一有序偶 Pk Wk 且在Wj Wk时有Pj Pk 则 Pj Wj 被舍弃 求决策序列 设 pixi P1 wixi W1 则有 P1 W1 Sn 若 P1 W1 Sn 1 则xn 0 否则xn 1 且有 P1 pn W1 wn Sn 1 用两个一维数组P W存放序偶 Pi Wi S0 S1 Sn互相邻接地存放 F i 指示Si中第一个元素所在的位置 F n 1 指示Sn中最后一个元素的位置加1 就可不保存S1i生成Si的方法 见P106 四 算法 五 用启发性方法进行加速 见P107 108 见P108 109 设计一个系统 该系统由若干个以串联方式连接在一起的不同设备组成 4 6可靠性设计 一 乘积函数最优化问题 若设备Di有mi台 将mi台Di并联 再将D1 D2 Dn串联 则可提高可靠性 可靠性为 ri 太低其中ri是设备Di的可靠性 求解此问题是对m1 m2 mn的一系列决策的结果 求解 可求出fn X 及mn m1 二 例 P110 111例4 15 求具有最小成本的周游路线 4 7货郎担问题 一 问题 设g i S 是由结点i开始 通过S中的所有点在结点1终止的一条最短路径的长度 则g 1 V 1 是一条最优的周游路线的长度 二 方法 按 S 1 S 2 S n 1求 1 可得问题的解 三 例 P112 113例4 17 假设在一条流水线上有n个作业 每个作业要求执行m个任务 T1i T2i Tmi 1 i n 且任务Tji只能在设备Pj上执行 1 j m 假设对每一个作业i 在任务Tj 1 i还没有完成之前 不能对任务Tji开始处理 而且同一台设备在任何时刻不能同时处理一个以上的任务 若完成任务Tji所用的时间是tji 1 j m 1 i n 如何将这n m个任务分配给这m台设备 才能使这n个作业在以上要求下顺利完成 4 8流水线调度问题 一 问题 1 非抢先调度2 抢先调度作业i的完成时间fi S 调度S的完成时间调度S的平均调动时间MFT S 最优完成时间OFT调度抢先最优完成时间POFT调度最优平均完成时间调度OMFT调度抢先最优平均完成时间调度POMFT调度 二