高中数学 第11章 算法初步 11.1 算法概念和例子课件 湘教版必修5.ppt

例子 给定两个正整数m和n 求它们的最大公因子算法 欧几里德算法输入 正整数m n输出 m和n的最大公因子 11 1算法概念和例子 一 什么是算法及其与程序的区别 s1 保证m n 如果m n 则m n的值互换 否则转s2 s2 求余数 令r mmodn 0 r n s3 判断余数r是否为0 如果r是0 则算法终止 n为答案 否则转s4 s4 置换 即m n n r 转s2 什么是算法 它是一组有穷规则的集合 它规定了解决某一特定类型问题的一系列运算 二 算法的特征1 确定性2 能行性3 输入4 输出5 有穷性 一个算法总是在有限步之后结束 且每一步都可在有穷时间内完成 算法与程序的区别 程序 与某种语言有关 能直接在机器上运行 算法 与特定的语言无关 可用任何语言实现 甚至可以用自然语言实现 但是一般为了避免二义性 本书采用类c语言描述 一个算法总是在执行了有穷步骤的运算后终止 否则就是一个计算过程 有穷性与有效性的关系 三 评价算法的标准 有穷性是对算法的基本要求 如果一个算法要能使用 必须具有有效性 有效性是指算法在规定的时间里终止 时间复杂性和空间复杂性 1 2算法设计的步骤 一 问题的描述 例 货郎担问题设售货员在一天内要到5个城市去推销货物 已知从一个城市到其他城市的费用 求总费用最少的路线 给出的信息主要有五个城市的关系图及相应的费用矩阵 二 模型的拟制建模阶段至少要考虑以下两个基本问题 1 最适合于这个问题的数学结构是什么 2 有没有已经解决了的类似问题可供借鉴 在模型建立好了以后 应该依据所选定的模型对问题重新陈述 并考虑下列问题 1 模型是否清楚地表达了与问题有关的所有重要的信息 2 模型中是否存在与要求的结果相关的数学量 3 模型是否正确反映了输入 输出的关系 4 对这个模型处理起来困难吗 对于货郎担问题 其数学模型是带权图 与此图相关的是费用矩阵 以货郎担问题为例 采用枚举法 分析 三 算法的详细设计 算法的详细设计是指设计求解某个具体问题的一系列步骤 并且这些步骤可以通过计算机的各种操作来实现 输入 城市数目n 费用矩阵c cij n n输出 旅行路线tour 最小费用min salesman n i 1 tour 0 min whilei n 1 do p phrmuti n 1 i phrmuti n 1 i 是生成1到n 1的第i个排列的子过程cost t p efp c t p efp c t 是由费用矩阵c及路线t p 所算得的总费用ifcost t p min tour t p min cost t p i i 1 printmin tour 四 算法的正确性可以分两步考虑 1 算法的终止性 2 算法的每一步是否都正确算法的正确性并不蕴涵算法的有效性 五 算法分析时间复杂性和空间复杂性以上货郎担问题的时间复杂性是 o n 六 文档的编制 1 注释 2 算法的流程图 3 对输入 输出的要求 4 正确性证明 5 时间复杂性和空间复杂性的分析 二 算法分析的要点1 确定使用的运算和执行这些运算所用的时间 运算分为两类 1 基本运算 2 组合 运算 由基本运算组成 1 3算法分析 一 算法分析的原因1 为了对算法的某些特定的输入 估计或限界该算法所需要的空间和运行时间 2 为了建立衡量算法优劣的标准 用以比较同一问题的不同算法 时间是固定量 时间是变化量 2 确定能反映出算法在各种情况下工作的数据集 构造出能产生最好 最坏和有代表性情况的数据配置 三 算法分析的两个阶段 1 事前分析 求出该算法的一个时间限界函数 2 事后测试 收集此算法的执行时间和实际占用空间的统计资料 就算法分析而言 一条语句的数量级指的是执行它的频率 而一个算法的数量级则指的是它所有语句执行频率的和 确定一个算法的数量级是十分重要的 它在本质上反映了一个算法所需要的计算时间 四 计算时间的渐进表示假设某种算法的计算时间是f n 其中变量n可以是输入或输出量 也可以是两者之和 还可以是它们之一的某种测度 例如 数组的维数 图的边数等等 g n 是在事前分析中确定的某个形式很简单的函数 例如 nm logn 2n n 等 它是独立于机器和语言的函数 而f n 则与机器和语言有关 定义1 2如果存在两个正常数c和n0 对于所有的n n0 f n c g n 则记作f n g n 因此 当说一个算法具有o g n 的计算时间时 指的是如果此算法用n值不变的同一类数据在某台机器上运行时 所用的时间总是小于 g n 的一个常数倍 所以g n 是计算时间f n 的一个上界函数 f n 的数量级就是g n 定义1 1 算法中基本操作重复执行的次数是问题规模n的某个函数f n 算法的时间度量记作 t n o f n 随着问题规模n的增大 算法执行时间的增长率和f n 的增长率相同 称作算法的渐近时间复杂度 简称时间复杂度 证明 取n0 1 当n n0时 利用a n 的定义和一个简单的不等式 有取c am a0 定理得证 事实上 只要将n0取得足够大 可以证明只要c是比 am 大的任意一个常数 此定理都成立 定理1 1若a n amnm a1n a0是一个m次多项式 则a n o nm 此定理表明 变量n的固定阶数为m的任一多项式 与此多项式的最高阶nm同阶 因此计算时间为m阶的多项式的算法 其时间都可用o nm 例如 若一个算法有数量级为c1nm1 c2nm2 cknmk的k个语句 则此算法的数量级就是c1nm1 c2nm2 cknmk由定理1 1 它等于o nm 其中m max mi 1 i k 例子 假设有解决同一个问题的两个算法 它们有n个输入 分别要求n2和nlogn次运算 定义1 3如果存在两个正常数c和n0 对于所有n n0 有 f n c g n 则记为f n g n 定义1 4如果存在两个正常数c1 c2 和n0 对于所有的n n0 有则记为f n g n 一个算法的f n g n 意味着该算法在最好和最坏情况下的计算时间就一个常因子范围内而言是相同的 五 算法分类 按时间 多项式时间算法 凡可用多项式来对其计算时间界限的算法 指数时间算法 计算时间用指数函数界限的算法 以下六种计算时间的多项式时间算法是最为常见的 其关系为 o 1 o logn o n o nlogn o n2 o n3 指数时间算法一般有o 2n o n 和o nn 等 其关系为o 2n o n o nn 注意 当数据集的规模很大时 要在现代计算机上运行具有比o nlogn 复杂度高的算法往往是很困难的 六 最好 最坏和平均情况以顺序检索为例 第二章分治法2 1方法概述 一 基本思想1 设计思想 将整个问题分成若干个小问题后 分而治之 2 适用条件 问题规模很大 可以分成若干个与原问题性质相同的子问题 并可以分别求解 子问题的解通过整合可以得到原问题的解 3 设计方法 使用递归策略 4 设计步骤 1 分解 将原问题分解为若干个相互独立 与原问题形式相同的子问题 2 求解 若子问题容易被解决则直接解 否则再继续分解为更小的子问题 直到容易解决 3 合并 将已求解的各个子问题的解 逐步合并以得到原问题的解 二 分治法的算法设计模式divide and conquer n n为问题规模1ifn n0 n0为可解子问题的规模2then3 4解子问题5return 子问题的解 6 4fori 1tok 分解为k个子问题5doyi divide and conquer pi 递归解决pi6t merge y1 y2 yk 合并子问题7returnt 递归过程 注意 分治法可以用递归实现 也可以用循环实现 其中 其中 p 表示问题p的规模 n0为一阈值 表示当问题p的规模不超过n0时 问题已容易直接解出 不必再继续分解 算法merge y1 y2 yk 是该分治法中的合并子算法 用于将p的子问题p1 p2 pk的相应的解y1 y2 yk合并为p的解 时间复杂性分析 其中 t n 是输入规模为n的divide and conquer的时间 g n 是对足够小的输入规模能直接计算出答案的时间 f n 是merge的时间 倘若所分成的两个子问题的输入规模大致相等 则divide and conquer总的计算时间可以用下面的递推关系来表示 n足够小 否则 2 2二分检索 一 问题描述已知一个按非降次序排列的元素表a1 a2 an 要求判定某给定元素x是否在该表中出现 若是 则找出x在表中的位置 并将此下标值赋给变量j 若非 则将j置成0 对于i2 通过比较x和ak容易得到解决 如果x ak 则j k且不需再对i1和i3求解 否则 在i2子问题的j 0 此时若xak 只有i3留待求解 在i1子问题中的j 0 在ak作了比较之后 留待求解的问题 如果有的话 可以再一次使用分治法来求解 如果对所求解的问题 或子问题 所选的下标k都是其元素的中间元素下标 例如 对于i k n 1 2 则所产生的算法就是通常所说的二分检索 三 二分检索算法算法2 3二分检索 给定一个按非降次序排列的元素数组a 1 n n 1 判断x是否出现 若是 置j 使得x a j 若非 j 0 binsearch a n x 1low 12high n 3whilelowhigh 数组a中没有找到x 返回j 04do5 6 取处于low和high之间的中间值7ifx a mid 找到值为x的元素 mid即为其下标 返回mid8thenreturnmid9elseifx a mid 如果x a mid 则x可能位于low与mid之间 10 否则x可能位于mid与high之间11thenhigh mid 112elselow mid 113 14retrun0 非递归形式 四 算法的证明假定在a 9 中顺序存放着以下9个元素 15 6 0 7 9 23 54 82 101 要求检索下列x的值 101 14和82是否在a中出现 从算法中可以看到 所有的运算基本上都是进行比较和数据传送 前两条是赋值语句 频率计数均为1 在while循环中 我们集中考虑循环的次数 而其他运算的频率计数显然与这些元素比较运算的频率计数具有相同的数量级 找到这九个元素中的每一个所需的元素循环的次数如下 五 时间复杂性分析 1 logn logn logn logn logn 分析 对于a中的n个数 如果x在a中出现 则是成功检索 所以成功检索共有n种情况 而不成功的检索 x将取n 1个区间中的不同值 因此在计算出x在这2n 1种情况下的执行时间后 就可以求出其在各种情况下的时间复杂性了 例子 a 1 2 3 4 5 6 7 8 9 元素 15 6079235482101比较次数 323413234 成功检索的比较次数是25 9 2 77 不成功检索有10种 如果x a 1 a 1 x a 2 a 2 x a 3 a 5 x a 6 a 6 x a 7 a 7 x a 8 为了判断x不在a中 算法要比较3次 而其余的情况要比较4次 因此一次不成功检索的元素平均比较次数就是 3 3 3 4 4 3 3 3 4 4 10 3 4 由于算法的执行过程实质上是x与一系列中间元素a mid 的比较过程 所以可以用一个二元比较树来描述 二元比较树 1 此树的结点由内结点和外结点组成 2 每个内结点表示一次元素比较 用圆形结点表示 在以元素比较为基础的二分检索中 每个内结点存放一个mid值 3 外结点用方形结点表示 在二分检索中它表示一次不成功的检索 4 x如果在a中出现 则算法就在一个圆形结点处结束 该结点将指出x在a中的下标 x如果不在a中出现 则算法就在一个方形结点处结束 如图所示 证明 考察以n个结点描述binsrch执行过程的二元比较树 所有成功检索都在内部结点处结束 而所有不成功的检索都在外部结点处结束 由于2k 1 n 2k 因此所有的内部结点在1 2 3 k级 而所有的外部结点在k k 1级 注意 根在1级 即是 成功检索在i级终止所需要的元素比较次数是i 而不成功检索在i级外部结点终止的元素比较数是i 1 因此定理得证 定理2 1若n在区域 2k 1 2k 中 则对于一次成功的检索 binsrch至多作k次比较 而对于一次不成功的检索 或者作k 1次比较或者作k次比较 由此 最坏情况下的成功检索和不成功检索的计算时间是 logn 最好情况下的成功检索在根结点处到达 时间是 1 而最好情况的不成功检索要logn次元素比较 所以时间是 logn 由于外部节点都在k和k 1级 因此 每种不成功检索的时间都是 logn 故平均情况下不成功检索的计算时间是 logn e i 2n 1 令s n 是成功检索的平均比较数 则s n i n 1 2 平均情况下成功检索的时间复杂性分析 设根到所有内部结点的距离之和称为内部路径长度i 由根到所有外部结点的距离之和称为外部路径长度e 可以证明 为什么要 1 令u n 是不成功检索的平均情况比较数 而任何一个外部结点所需要的比较数是由根到该结点路径的长度 由此得 u n e n 1 3 利用 1 3 可以得到 s n 1 1 n u n 1因此 平均情况下成功检索的时间复杂性为 logn 五 一种二分检索的变形binsearch1 binsearch1的while循环中x和a mid 之间只用作一次比较 binsearch1 a n x j 1low 12high n 13whilelow high4do5 6mid low high 27if x a mid 在循环中只比较一次8thenhigh mid9elselow mid10 11ifx a low 12thenj low x出现13elsej 0 x不出现14returnj binsearch和binsearch1相比较可看出 对于任何一种成功的检索 binsearch1平均要比binsearch多作次比较 binsearch1的最好 平均和最坏情况时间对于成功和不成功的检索都是 六 以比较为基础检索的时间下界1 什么是以比较为基础的检索算法检索一给定元素x是否在a中出现 如果只允许进行元素间的比较而不允许对它们实施运算 在这种条件下所设计的算法都称为是以比较为基础的算法 2 二分检索是以比较为基础的检索算法中最坏情况下的最优算法 一 直接求最大 最小元素算法2 5直接找最大和最小元素maxmin a n 将a 1 n 中的最大元素置于max 最小元素置于min 1max a 1 2min a 1 3fori 2ton4do5 6ifmaxa i 7thenmin a i 8 2 3找最大和最小元素 时间复杂性分析 straitmaxmin在最好 平均和最坏情况下均需要作2 n 1 次元素比较 如果稍做修改 用下面的语句代替for循环中的语句 ifa i maxthenmax a i elseifa i minthenmin a i endifendif最好情况将在元素按递增次序排列时出现 元素比较数是n 1 最坏情况将在递减次序时出现 元素比较是2 n 1 至于在平均情况下 a i 将有一半的时间比max大 因此平均比较数是3 2 n 1 二 用分治法求最大 最小元素1 问题分析使用分治策略设计是将任一实例i n a 1 a n 分成一些较小的实例来处理 例如 可以把 分成两个这样的实例i1 n 2 a 1 a n 2 和 n n 2 a n 2 1 a n 如果 和 是 中的最大和最小元素 则 等于 和 中的大者 等于 和 中的小者 如果 只包含一个元素 则不需要作任何分割直接就可得到其解 2 算法算法 递归求取最大和最小元素floata n maxmin i j fmax fmin 最大和最小元素赋给fmax和fmin1ifi j2then3 4fmax a i 5fmin a i 7elseifi j 18thenifa i a j 9then10 11fmax a j 12fmin a i 13 14else15 16fmax a i 17fmin a j 18 19else20 21mid i j 2 22maxmin i mid lmax lmin 23maxmin mid 1 j rmax rmin 24iflmax rmax25thenfmax lmax 26elsefmax rmax27iflmin rmin28thenfmin rmin 29elsefmin lmin 30 递归调用 利用层次分析法分析此递归调用过程 要求掌握 考虑如下例子 a 1 2 3 4 5 6 7 8 9 2213 5 81560173147 讨论 以上算法是否是最优的 1 递归带来的额外的空间开销 2 当元素a i 和a j 的比较时间i和j的比较时间相差不大时 过程maxmin并不可取 因此 当n是 的幂时 3n 2 2是最好 平均及最坏情况的比较数 和直接算法的比较数 n 相比 它少了 可以证明 任何一种以元素比较为基础的找最大和最小元素的算法 其元素比较下界均为次 为说明问题 假设元素比较与i和j间的比较时间相同 又设maxmin的频率计数为c n n 2k k是某个正整数 并且对前两种情况 用i j 1来代替i j和i j 1这两次比较 这样 只用对i和j 1作一次比较就足以实现被修改过的语句 于是maxmin频率计数c n n 2n 2 解此关系式可得c n 2c n 2 3 4c n 4 6 3 2k 1c 2 2k 3 2k 1 3 5n 2 3 分析 straitmaxmin的比较数是3 n 1 包括实现for循环所要的比较 尽管它比5n 2 3大些 但由于递归算法中i j fmax fmin进出栈所带来的开销 因此maxmin在这种情况下反而比straitmaxmin还要慢些 根据以上分析可以得出结论 如果a的元素间的比较远比整数变量的比较代价昂贵 则分治方法产生效率较高 实际上是最优 的算法 反之 就得到一个效率较低的程序 因此 分治策略只能看成是一个较好的然而并不总是能成功的算法设计指导 2 4斯特拉森矩阵乘法 一 一般的矩阵乘法设c a b 则利用常规方法计算 所需时间是 二 分治法求矩阵乘法设n 2k 则可以将两个矩阵的乘法做如下划分 其中 c11 a11b11 a12b21c12 a11b12 a12b21c21 a21b11 a22b21c22 a21b12 a22b22可以证明 c ab 三 斯特拉森矩阵乘法斯特拉森矩阵乘法的设计思想 增加加法的次数 减少乘法的次数 如果分块矩阵的级大于2 则可以继续将这些子矩阵分成更小的方阵 直至每个方阵只含有一个元素 以至可以直接计算其乘积 时间复杂性分析 n 2n 2则t n o n3 先用七个乘法和十个加 减 法来算出以下的p vp a11 a22 b11 b22 q a21 a22 b11r a11 b12 b22 s a22 b21 b11 t a11 a12 b22 u a21 a11 b11 b12 v a12 a22 b21 b22 然后用8个加减法算出这些cijc11 p s t vc12 r tc21 q sc22 p r q u 以上共用了7次乘法 18次加减法 n 2n 2其中a和b是常数 解 t n 7t n 2 an2 72t n2 4 7 4 an2 an2 73t n3 8 7 4 2an2 7 4 an2 an2 an2 1 7 4 7 4 2 7 4 k 1 7kt 1 cn2 7 4 logn 7logn 1 因为 7logn nlog7cn2 7 4 logn cnlog4 nlog7 log4 cnlog4 log7 log4 cnlog7因此上式 1 cnlog7 7logn cnlog7 nlog7 c 1 nlog7 o nlog7 o n2 81 注意 1 当n小于120时 斯特拉森矩阵乘法与普通的乘法没有太大的区别 2 斯特拉森矩阵乘法的核心就是降低乘法的次数而增加加法的次数 那么是否可以使乘法由7次降低为6次呢 已经证明7次是必须的 这一方面改进只能从更高维数如3 3 或4 4并用递归分治的合并方法来实现 现在可以达到o n2 495364 一 基本方法1 例子 背包问题 已知有n种物品和一个容量大小为m的背包 每种物品i的容量为wi 假定将物品i的一部分xi放入背包就会得到pixi的效益 这里 0 xi 1 pi 0 采用怎样的装包方法才会使装入背包物品的总效益最大呢 显然 由于背包容量是m 因此 要求所有选中要装入背包的物品总容量不得超过m 如果这n件物品的总容量不超过m 则把所有物品装入背包自然获得最大效益 如果这些物品容量的和大于m 则在这种情况下该如何装包呢 第三章贪心方法3 1方法概述 例 考虑下列情况下的背包问题 n 3 m 20 25 24 15 18 15 10 其中的四个可行解是 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在这些可行解中 如何得到最优解 正是贪心方法要解决的问题 2 适用条件 1 有n个输入 2 它的解就由这n个输入的某个子集组成 3 这个子集必须满足一定的约束条件 可行解 4 可行解一般不止一个 但是要求的是最优解即使目标函数取得极值的解 3 有关概念 1 约束条件 把子集必须满足的基本条件称为约束条件 2 可行解 把满足约束条件的子集称为该问题的可行解 3 目标函数 可行解一般来说是不唯一的 为了衡量可行解的优劣 事先也给出了一定的标准 这些标准一般以用函数形式给出 这些函数称为目标函数 4 最优解 那些使目标函数取极值 极大或极小 的可行解 称为最优解 二 贪心方法的算法设计模式greedy a n a n 包含n个输入 1solution 将解向量solution初始化为空 2fori 1tondo3 x select a 按最优量度标准在a中选择一个输入4iffeasible solution x thensolution union solution x return solution 三 设计要点 选择能产生问题最优解的最优量度标准是使用贪心法设计求解的核心问题 3 2背包问题一 问题的描述背包问题 已知有n种物品和一个容量为m的背包 每种物品i的容量为wi 效益为pi 假定将物品i的一部分xi放入背包就会得到pixi的效益 这里 0 xi 1 pi 0 采用怎样的装包方法才会使装入背包物品的总效益最大呢 显然 由于背包容量是m 因此 要求所有选中要装入背包的物品总容量不得超过m 如果这n件物品的总容量不超过m 则把所有物品装入背包自然获得最大效益 如果这些物品容量的和大于m 则在这种情况下该如何装包呢 由以上叙述 可将这个问题形式描述如下 约束条件 目标函数 其中 0 xi 1 pi 0 wi 0 0 i nm 背包的容量n 物品种类wi 第i物品的容量pi 第i种物品价值显然 满足约束条件的任一集合是一个可行解 使目标函数取最大值的可行解是最优解 例3 1考虑下列情况下的背包问题 n 3 m 20 pl p2 p3 25 24 15 w1 w2 w3 18 15 10 其中的四个可行解是 x1 x2 x3 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在这四个可行解中 第 个解的效益值最大 下面将可看到 这个解是背包问题在这一情况下的最优解 二 问题的分析为了获取背包问题的最优解 必须要把物品放满背包 由于可以只放物品i的一部分到背包中 因此这一要求是可以达到的 如果用贪心策略来求解背包问题 则正如3 1节中所说的一样 首先要选出最优的量度标准 以下不妨分三种情况进行分析 1 取效益值作为量度标准 即每装入一件物品就使背包获得最大可能的效益值增量 在这种量度标准下的贪心方法就是按效益值的非增次序将物品一件件放到背包中去 如果正在考虑中的物品放不进去 则可只取其一部分来装满背包 量度标准选取 此种选择策略得到 的解 总效益值是28 2 它是一个次优解 由此例可知 按物品效益值的非增次序装包不能得到最优解 为什么上述贪心策略不能获得最优解呢 原因在于 背包可用容量消耗过快 由此 很自然地启发我们用容量作为量度 让背包容量尽可能慢地被消耗 2 用容量作为量度标准在这种量度标准下的贪心方法就是按物品容量的非降次序来把物品放入背包 例3 1的解 就是使用这种贪心策略得到的 它仍是一个次优解 这种策略也只能得到次优解 其原因在于容量虽然慢慢地被消耗 但效益值没能迅速地增加 以上策略也只能得到次优解 其原因在于容量虽然慢慢地被消耗 但效益值没能迅速地增加 这又启发我们应采用在效益值的增长速率和容量的消耗速率之间取得平衡的量度标准 即每装入一件物品应使它占用的每一单位容量获得当前最大的效益 三 算法设计算法3 3背包问题的贪心算法 3 用效益和容量的比值作为量度标准 即 这就需使物品的装入次序按比值的非增次序来考虑 在这种策略下的量度是已装入物品的累计效益值与所用容量之比 其量度标准是每次装入要使累计效益值与所用容量的比值有最多的增加或最少的减小 第二次和以后的装入可能使此比值减小 将此贪心策略应用于例3 l的数据 得到解 knapsack elemtypewp n elemtypepw n floaty n elemtypewc intn p n 和w n 分别含有按p i w i p i 1 w i 1 排序的n件物品的效益值和容量 m是背包的容量大小 而y n 是解向量 1fori 1ton2doy i 0 将解向量初始化为0 3cu c cu是背包中剩余的空间 4fori 1ton5do 依次考察下一个物品是否可以放入背包 6ifw i cubreak 物品i无法全部放入背包 退出for循环 7theny i 1 8cu cu w i 9 10ifi n11theny i cu w i 不能完全装入的物品的部分装入量 量度标准 值得指出的是 a 如果把物品事先按效益值的非增次序或容量的非降次序分好类 再使用以上算法就可分别得到量度标准为 2 或 3 使每次效益增量最大或使容量消耗最慢 的解 b 该算法的解的形式为 1 1 x 0 0 其中x在 0 1 由背包问题量度选取的研究可知 选取最优的量度标准实为用贪心方法求解问题的核心 小结 贪心方法设计步骤 找出问题的约束条件和目标函数 选取合适的量度标准 按照 贪心方法的算法设计模式 的步骤进行算法设计 四 算法分析如果将物体事先按pi wi的非增次序分好类 则过程knapsack就得出这一策略下背包问题的解 如果将物品分类的时间不算在内 则此算法所用时间为o n 五 算法的证明证明的基本思想是 把这贪心解与任一最优解相比较 如果这两个解不同 就去找开始不同的第一个xi 然后设法用贪心解的这个xi去代换最优解的那个xi 并证明最优解在分量代换前后的总效益无任何变化 反复进行这种代换 直到新产生的最优解与贪心解完全一样 从而证明了贪心解是最优解 掌握 定理3 1如果p1 wl p2 w2 pn wn 则算法greedy knapsack对于给定的背包问题实例生成一个最优解 证明 设x x1 xn 是greedy knapsack所生成的解 如果所有的xi等于1 显然这个解就是最优解 于是 设j是使xj 1的最小下标 由算法可知 对于1 i j xi 1 对于j i n xi 0 对于j 0 xj 1 如果x不是一个最优解 则必定存在一个可行解y y1 y2 yn 使得 不失一般性 可以假定 wiyi m 设k是使得yk xk的最小下标 显然 这样的k必定存在 由上面的假设 可以推得ykj分别得证明 若kxk 显然有 wiyi m 与y是可行解矛盾 若yk xk 与假设yk xk矛盾 故ykj 则 wiyi m 这是不可能的 现在 假定把yk增加到xk 那末必须从 yk 1 yn 中减去同样多的量 使得所用的总容量仍是m 这导致一个新的解z z1 z2 zn 其中zi xi 1 i k 且 因此 对于z有 若 0时 则y不是最优解 此与假设矛盾 所以不可能 即 0 当 0时 则z x或z x 则若z x 则 pizi piyi 由于y是最优解 因此z也是最优解 x也是最优解 若z x 重复上面的讨论 用z代替y 则又可求得相应的 0 重复以上过程 直到x z为止 可得x为最优解 讨论 3 3带有限期的作业排序一 问题的描述假定只能在一台机器上处理n个作业 每个作业均可在单位时间内完成 又假定每个作业i都有一个截止期限di 0 它是整数 当且仅当作业i在它的期限截止以前被完成时 则获得pi 0的效益 求具有最大效益值的可行解 也就是最优解 分析 约束条件 每个作业均要在截止期限前完成 目标函数 例子 n 4 p1 p2 p3 p4 100 10 15 20 和 d1 d2 d3 d4 2 1 2 1 可行解处理顺序效益值 1 1100 2 210 3 315 4 420 1 2 2 1110 1 3 1 3或3 1115 1 4 4 1120 2 3 2 325 3 4 4 335 二 问题的分析最优量度标准 目标函数 pi作为量度 即按照pi的非增次序来考虑这些作业 使用这一量度 下一个要计入的作业将是使得在满足所产生的j是一个可行解的限制条件下让 pi得到最大增加的作业 应用以上的量度标准 开始时j 0 由于作业1有最大效益且j 1 是一个可行解 于是把作业1计入j 下一步考虑作业4 j 1 4 也是可行解 然后考虑作业3 因为 1 3 4 不是可行解 故作业3被舍弃 最后考虑作业2 由于 1 2 4 也不可行 作业2被舍弃 最终所留下的是效益值为120的解j 1 4 它是这个问题的最优解 三 算法的粗略描述greedy job d j n 作业按p1 p2 pn的次序输入 它们的期限值d i 1 1 i n n 1 j是在它们的截止期限前完成的作业的集合 1j 1 2fori 2tondo3 ifj i 的所有作业都有能在它们的截止期限前完成thenj j i 4endif5 由前面贪心方法的算法设计模式得到 j是一个作业的集合 而不是调度表 四 算法的证明定理3 2以上算法所描述的贪心方法对于作业排序问题总是得到一个最优解 思路 j是由贪心方法所选择的作业的集合 i是一个最优解的作业集合 可证明j和i具有相同的效益值 从而j也是最优的 i j是作业的集合 而不是作业的调度表 证明 假定 1 i j 因为若i j 则j即为最优解 2 如果ij 则i就不可能是最优的 3 由贪心法的工作方式也排斥了ji 因此 至少存在这样的两个作业a和b 使得a j且ai b i且bj 设a是使得a j且ai的一个具有最高效益值的作业 由贪心方法可以得出 对于在i中又不在j中的所有作业b 都有pa pb 这是因为若pb pa 则贪心方法会先于作业a考虑作业b并且把b计入到j中去 设si和sj分别是i和j的可行调度表 调度表与作业集的区别 1 设i是既属于j又属于i的一个作业 把他们调换到相同的时刻去调度 且尽量将调度时间往后移 设i在si中在t到t 1时刻被调度 而在sj中则在t 到t 1时刻被调度 如果t t 则可以将si中 t t 1 时刻所调度的那个作业 如果有的话 与i相交换 如果j中在 t t 1 时刻没有作业被调度 则将i移到 t t 1 调度 所形成的这个调度表也是可行的 如果t t 则可在和si中作类似的调换 2 对于i j中不同的作业 则以j为标准 将其中不属于i的那些作业找出 设a是这样的作业 它在sj中时刻被调度 设作业b在i中的这一时刻被调度 根据对a的选择在si的时刻去掉作业b而去调度作业a 这就给出了一张关于作业集合i i b a 可行的调度表 显然i 的效益值不小于i的效益值 并且i 比i少一个与j不同的作业 重复使用上述的转换 将使i能在不减效益值的情况下转换成j 因此j也必定是最优解 证毕 五 算法的实现考虑对于一个给定的j 如何确定它是否为可行解的问题 一个明显的方法是检验j中作业的所有可能的排列 对于任一种次序排列的作业序列 判断这些作业是否能在其限期前完成 j是作业集 不是调度表 假定j中有k个作业 这就需要检查k 个排列 对于所给出的一个排列 i1i2i3 ik 由于完成作业ij 1 j k 的最早时间是j 因此 只要判断出 排列中的每个作业的dij j 就可得知 是一个允许的调度序列 从而j就是一个可行解 反之 如果 排列中有一个dij j 则 是一个行不通的调度序列 因为至少作业ij不会在它的限期前完成 故必须去检查j的另外形式的排列 事实上 对于j的可行性可以通过只检验j中作业的一种特殊的排列来确定 这个排列是按期限的非降次序来完成的 定理3 3设j是k个作业的集合 i1i2i3 ik是j中作业的一种排列 它使得di1 di2 dik j是一个可行解 当且仅当j中的作业可以按照 的次序而又不违反任何一个期限的情况下来处理 说明了什么 证明 现证 若j是可行解 则 表示可以处理这些作业的一种允许的调度序列 由于j可行 则必存在 使得假设 那末 令a是使得的最小下标 设 显然b a 在 中将与相交换 因为 故作业可依新产生的排列的次序处理而不违反任何一个期限 连续使用这一方法 就可将 转换成 且不违反任何一个期限 定理得证 算法设计思路 首先将作业按照效益值的非增次序排列 然后试着将作业逐个与当前的部分可行解合并 检查是否可产生新的可行解 注意当前的部分可行解已经按期限值的非降次序排列 其方法是在部分可行解中 看能否找到新作业的合适的位置 使加入了新的作业后 其期限值仍按非降次序排列 且每个作业均在其截止期限前完成 算法3 4带有限期和效益的单位时间的作业排序贪心算法greedyjob intn intd int 体现了量度标准 11 12ifd j r d i andd i r 判断此作业是否可以插入j 13then 14forj ktor 1 j是递减的15do 将第k到第r 1个作业依次后移一位以插入新的作业 16j j 1 j j 17 18j r 1 i 将作业插入位置r 1 19k k 1 记入j的作业数加1 20 21 22returnk 返回记入j中的作业数 七 一种更快的实现通过使用不相交集合的union与find算法以及使用一个不同的方法来确定部分解的可行性 可以把js的计算时间由o n2 降低到数量级相当接近于o n 六 时间复杂性分析经过分析知道 算法js所需要的总时间是o sn 由于s n s为包含在解中的作业数 因此js的最坏计算时间为o n2 分析 该方法较前方法的不同之处在于如何确定部分解的可行性方面 两者的量度标准是一样的 其方法是 如果j是作业的可行子集 那么可以使用下述规则来确定这些作业中的每一个作业的处理时间 若还没给作业i分配处理时间 则分配给它时间片 1 其中 应尽量取大且时间片 1 是空的 此规则就是尽可能推迟对作业的处理 于是 在将作业一个一个地装配到j中时 就不必为接纳新作业而去移动j中那些已分配了时间片的作业 如果正被考虑的新作业不存在像上面那样定义的 这个作业就不能计入j 例3 3设n 5 p1 p5 20 15 10 5 1 和 d1 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 设计思想 1 只考虑时间片 1 b 其中b min n max dj 2 作出一些以期限值为元素的集合 且使得同一集合中的元素都有一个当前共同可用的最接近的空时间片 3 用f i 表示期限为i的作业当前最接近的空时间片ni 初始时 f i i且有b 1个集合与b 1个期限值相对应 4 p i i为根时 表示树中结点数的负值 i不为根时 表示i的父结点 初始时 p i 1 5 若要调度具有期限值是d的作业 则去找包含期限值min n d 的那个根 若根为j且只要f j 0 则f j 是最接近的空时间片 在使用完此时间片后 其根为j的集合与包含期限值f j 1的集合合并 核心 在算法fasterjob中调用了过程union和find 其算法分别描述如下描述如下 算法union i j 的概略描述 union inti intj 1x parent i parent j 计算两棵树的总结点数 4ifparent i parent j 注意这里比较的是两个负数 5then 树i的结点数比j的少 则把i连到以j为根的树上 6parent i j7parent j x 8 9else 树j的结点数比i的少 11parent j i12parent i x 13 此算法的功能是合并根为i j的两个集合 函数find i 算法描述如下 find i 1j i 2whileparent j 0 寻找根结点j 3doj parent j 4k i 5whilek j6do 使用压缩规则 压缩结点i到其根结点之间的路径上的结点 7t parent k 8parent k j 9k t 10 11returnj 返回根结点 一 适用条件多阶段决策过程实际问题中 常有这样一类活动 它们的活动过程可以分为若干个阶段 而且在任一阶段i后的行为都依赖于i阶段的过程状态 而与i阶段之前的过程如何达到这种状态的方式无关 当各个阶段决策确定后 就组成了一个决策序列 因而也就确定了整个过程的一条活动路线 这种把一个问题看作是一个前后关联的具有链状结构的多阶段过程被称为多阶段决策过程 满足最优性原理 第四章动态规划4 1方法概述 状态0决策1决策2 决策n状态n 状态1 状态n 1 状态2 二 最优性原理在多阶段决策过程的每一阶段 都可能有多种可供选择的决策 但必须从中选取一种决策 一旦各个阶段的决策选定之后 就构成了解决这一问题的一个决策序列 决策序列不同 所导致的问题的结果也不同 动态规划的目标就是要在所有容许选择的决策序列中选取一个会获得问题最优解的决策序列 即最优决策序列 三 动态规划方法的关键关键在于获取各阶段间的递推关系式 四 可解决的问题最短路径问题 设备更新问题 资源分配问题 货物装运排序 生产计划等 五 应用实例分析 例4 1 多段图问题 多段图g v e 是一个有向图 它具有如下特性 图中的结点被划分成k 2个不相交的集合vi 1 i k 其中v1和vk分别有一个结点s 源点 和t 汇点 图中所有的边 u v 均具有如下性质 若u vi 则v vi 1 1 i k 1 且每条边 u v 均附有成本c u v 从s到t的一条路径成本是这条路径上边的成本和 多段图问题是求由s到t的最小成本路径 每个集合vi定义图中的一段 由于e的约束 每条从s到t的路径都是从第1段开始 在第k段终止 图4 1所示的就是一个5段图 4 6 对于每一条由s到t的路径 可以把它看成在k 2个阶段中作出的某个决策序列的相应结果 第i次决策就是确定vi 1中的哪个结点在这条路径上 1 i k 2 下面证明最优性原理对多段图成立 假设s v2 v3 vk 1 t是一条由s到t的最短路径 还假定从源点s 初始状态 开始 已作出了到结点v2的决策 初始决策 因此v2就是初始决策所产生的状态 如果把v2看成是原问题的一个子问题的初始状态 解这个子问题就是找出一条由v2到t的最短路径 这条最短路径显然是v2 v3 vk 1 t 如若不然 设v2 q3 qk 1 t是一条由v2到t的更短路径 则s v2 q3 qk 1 t是一条比路径s v2 v3 vk 1 t更短的由s到t的路径 与假设矛盾 故最优性原理成立 因此它为使用动态规划方法来解决多段图问题提供了可能 六 动态规划方法的形式化描述能用动态规划求解的问题的最优化决策序列可表示如下 设s0是问题的初始状态 假定需要作n次决策xi 1 i n 设x1 r1 1 r1 2 r1 p1 是x1的可能决策值的集合 而s1 1是在选取决策值r1 j1以后所产生的状态 1 j1 p1 又设是相应于状态s1 j1的最优决策序列 那末 相应于s0的最优决策序列就是 1 j1 p1 中最优的序列 记为opt 如果已作了k 1次决策 1 k 1 n 设x1 xk 1的最优决策值是r1 rk 1 它们所产生的状态为s1 sk 1 又设 是xk的可能值的集合 是选取决策值后所产生的状态 1 jk pk 是相应于的最优决策序列 因此 相应于sk 1的最优决策序列是 于是相应于s0的最优决策序列为r1 rk 1 rk 七 两种求解方法 1 向前处理法 从最后阶段开始 以逐步向前递推的方式列出求前一阶段决策值的递推关系式 即根据xi 1 xn的那些最优决策序列来列出求取xi决策值的关系式 即 xi f xi 1 xi 2 xn 例子 在k段图问题中 设又设是由到t的最短路径 则s到t的最短路径是中最短的那条路径 若设是s到t的一条最短路径 是路径上的中间结点 则就应分别是由s到vi和由vi到t的最短路径 2 向后处理法 根据x1 xi 1的那些最优决策序列列出求xi的递推关系式 即 xi f x1 x2 xi 1 下例是说明向前处理法在多段图中的使用 见黑板 小结 无论是使用向前处理法还是使用向后处理法 都将所有子问题的最优解保存下来 这样做的目的是为了便于逐步递推得到原问题的最优解并避免对它们的重复计算 由枚举法可知 不同决策序列的总数就其所取决策值而言是指数级的 如果决策序列由n次决策构成 而每次决策有p种选择 那末可能的决策序列就有pn个 而动态规划算法则可能有多项式的复杂度 八 动态规划算法的求解步骤 1 段化 2 自顶向下的分析 测试问题本身是否满足最优化原理 3 从底向上的计算 实现动态规划过程 一 问题的描述例4 1给出了多段图的定义 并且指出一个k段图的每一条由源点s到汇点t的路径可以看成是在k 2个阶段中作出的某个决策序列的相应结果 第i次决策就是确定vi 1中的哪个结点在这条路径上 1 i k 2 进而还证明了最优性原理对多段图成立 因此用动态规划方法有可能找到由s到t的最小成本路径 4 2多段图 二 问题分析 使用向前处理法求各阶段的递推关系式 1 2 若 e 有cost k 1 j c j t 若e 有cost k 1 j 设 p i j 是一条从vi中的结点j到汇点t的最小成本路径 cost i j 是这条路的成本 关键 例子 对图4 1的5段图给出具体实现这一系列计算的步骤 cost 3 6 min 6 cost 4 9 5 cost 4 10 7cost 3 7 min 4 cost 4 9 3 cost 4 10 5cost 3 8 7cost 2 2 min 4 cost 3 6 2 cost 3 7 1 cost 3 8 7cost 2 3 9 cost 2 4 18