算法设计与分析ppt课件

第一章算法概述 第二章递归与分治策略 第三章动态规划 第四章贪心算法 第五章回朔法 第六章分支限界法 第七章随机化算法 算法设计与分析 目录 1 4 2贪心算法基本要素 4 1活动安排问题 4 3最优装载问题 算法设计与分析 目录 4 7多机调度问题 2 算法设计与分析 贪心算法 4 1活动安排问题 有n个活动E 1 2 n 其中每个活动要使用同一资源 同一时间只允许一个活动使用该资源 每个活动i都有一个开始时间si 和一个结束时间fi 如果选择活动i 则它在时间区间 si fi 内占用该资源 若区间 si fi 与 sj fj 不相交 则称活动i与j是相容的 兼容的 活动安排问题是要求在所给的活动集合中选出最大相容活动子集 3 在安排时应该将结束时间早的活动尽量往前安排 好给后面的活动安排留出更多的空间 从而达到安排最多活动的目标 贪心准则应当是 在未安排的活动中挑选结束时间最早的活动安排 算法设计与分析 贪心算法 直观想法 4 算法设计与分析 贪心算法 算法思路 1 将活动按结束时间排序 得到活动集E e1 e2 en 2 先将e1选入结果集合A中 即A e1 3 依次扫描每一个活动ei 如果ei的si 最后一个选入A的活动ej的fj 则将ei选入A中 否则放弃ei 5 算法设计与分析 贪心算法 定理 考虑任意非空子问题Sk 令am是Sk中结束时间最早的活动 则am在Sk的某个最大兼容活动子集中 证明 令Ak是Sk的一个最大兼容活动子集 且aj是Ak中结束时间最早的活动 若aj am 则证明am在Sk的某个最大兼容活动子集中 若aj am 令集合 即将Ak中的aj替换am因为Ak中的活动都是不相交的 aj是Ak中结束时间最早的活动 而fm fj 所以Ak 中的活动都是不相交的 由于 Ak Ak 因此得出结论Ak 也是Sk的一个最大活动子集 且它包含am 6 2 最优子结构性质当一个问题的最优解包含其子问题的最优解时 称此问题具有最优子结构性质 问题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征 算法设计与分析 贪心算法 7 3 贪心算法与动态规划算法的差异 算法设计与分析 贪心算法 相同点 都具有最优子结构性质区别 8 算法设计与分析 贪心算法 背包问题给定n种物品和一个背包 物品i的重量是wi 其价值为vi 背包的容量为C 应如何选择装入背包的物品 使得装入背包中物品的总价值最大 在选择物品i装入背包时 可以选择物品i的部分 而不一定要全部装入背包 1 i n 不允许重复装入 9 于是 背包问题归结为寻找一个满足约束条件 并使目标函数达到最大的解向量X x1 x2 xn 设xi表示物品i装入背包的情况 根据问题的要求 有如下约束条件和目标函数 算法设计与分析 贪心算法 10 每次捡最轻的物品装 每次捡价值最大的装 每次装包时既考虑物品的重量又考虑物品的价值 也就是说每次捡单位价值最大的装 算法设计与分析 贪心算法 贪心选择 只考虑到多装些物品 但由于单位价值未必高 总价值不能达到最大 每次选择的价值最大 但同时也可能占用了较大的空间 装的物品少 未必能够达到总价值最大 确实能够达到总价值最大 11 首先计算每种物品单位重量的价值vi wi 然后 依贪心选择策略 将尽可能多的单位重量价值最高的物品装入背包 若将这种物品全部装入背包后 背包内的物品总重量未超过C 则选择单位重量价值次高的物品并尽可能多地装入背包 依此策略处理 直到背包装满为止 算法设计与分析 贪心算法 基本步骤 12 算法设计与分析 贪心算法 voidKnapsack intn floatM floatv floatw floatx 价值数组v 1 n 重量数组w 1 n 它们元素的排列顺序满足v i w i v i 1 w i 1 M是背包容量 x是解向量 floatc M 使背包剩余容量初始化为Minti Sort n v w for i 1 icbreak x i 1 c c w i if i n x i c w i 将各种物品依其单位重量的价值从大到小排序 算法的计算时间上界为O nlogn 13 0 1背包问题 给定n种物品和一个背包 物品i的重量是wi 其价值为vi 背包的容量为C 应如何选择装入背包的物品 使得装入背包中物品的总价值最大 在选择装入背包的物品时 对每种物品i只有2种选择 即装入背包或不装入背包 不能将物品i装入背包多次 也不能只装入部分的物品i 算法设计与分析 贪心算法 14 算法设计与分析 贪心算法 对于0 1背包问题 贪心选择之所以不能得到最优解 是因为它无法保证最终能将背包装满 部分闲置的背包空间使每公斤背包空间的价值降低了 事实上 在考虑0 1背包问题时 应比较选择该物品和不选择该物品所导致的最终方案 然后再作出最好选择 由此就导出许多互相重叠的子问题 这正是该问题可用动态规划算法求解的另一重要特征 分析 15 算法设计与分析 贪心算法 4 3最优装载 有一批集装箱要装上一艘载重量为c的轮船 其中集装箱i的重量为wi 最优装载问题要求确定在装载体积不受限制的情况下 将尽可能多的集装箱装上轮船 问题描述 满足 16 1 算法描述最优装载问题可用贪心算法求解 采用重量最轻者先装的贪心选择策略 可产生最优装载问题的最优解 算法设计与分析 贪心算法 17 算法设计与分析 贪心算法 voidLoading intx Typew floatc intn int t newint n 1 Sort w t n for inti 0 i n t i 中存储第i轻集装箱在原来序列中的下标 x i 记载第i个集装箱是否装入 x i 1装入 x i 0未装入 18 物品重量分别为15 10 27 18 船载重为50定义 w 15 10 27 18 物品重量T 1 0 3 2 物品从轻到重排序后序号C 50船载重贪心算法计算步骤 w T 0 10c 算法设计与分析 贪心算法 例 19 20 设 x1 xn 是最优装载问题的一个满足贪心选择性质的最优解 则x1 1时 x2 xn 是轮船载重量为c w1且待装集装箱为 2 n 时相应最优装载问题的一个最优解 算法设计与分析 贪心算法 21 算法设计与分析 贪心算法 3 最优子结构性质最优装载问题具有最优子结构性质 由最优装载问题的贪心选择性质和最优子结构性质 容易证明算法的正确性 算法的主要计算量在于将集装箱依其重量从小到大排序 故算法所需的计算时间为O nlogn 22 算法设计与分析 贪心算法 4 7多机调度问题 问题描述 要求给出一种作业调度方案 使所给的n个作业在尽可能短的时间内由m台机器加工处理完成 作业i所需时间为ti 约定 每个作业均可在任何一台机器上加工处理 但未完工前不允许中断 作业不能拆分成更小的子作业 该问题是NP完全问题 到目前为止还没有有效的解法 用贪心选择策略有时可设计出较好的近似算法 23 贪心近似算法 采用最长处理时间作业优先的贪心策略 当n m时 只要将机器i的 0 ti 时间区间分配给作业i即可 当n m时 将n个作业依其所需的处理时间从大到小排序 然后依次将作业分配给空闲的处理机 算法设计与分析 贪心算法 24 算法设计与分析 贪心算法 classJobNode friendvoidGreedy JobNode int int friendvoidmain void public operatorint const returntime private intID time classMachineNode friendvoidGreedy JobNode int int public operatorint const returnavail private intID avail 多机调度问题的贪心近似算法 作业结点类 机器结点类 25 templatevoidGreedy Typea intn intm if nH m MachineNodex for inti 1 i 1 i 作业分配过程H DeleteMin x 从堆中取出堆顶x机器cout 将机器 x ID 从 x avail 到 x avail十a i time 的时间段分配给作业 a i ID endl x avail a i time 机器的时间分配H insert x 重新插入 调整堆 如果机器数大于作业数直接分配 按照机器结点编号顺序建立堆 26 算法设计与分析 贪心算法 时间复杂度分析nm排序耗时O nlogn 初始化堆O m DeleteMin和Insert耗时O nlogm 共需时间为 O nlogn nlogm O nlogn 27