(算法课件五贪心算法.pptVIP

贪心算法 目录 背包问题 作业安排问题 带期限的单机作业安排问题 多机调度问题 贪心算法的理论基础-拟阵（略） 贪心算法的进一步讨论 什么是贪心算法 贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。 贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。 喷水装置 现有一块草坪，长为20米，宽为2米，要在横中心线上放置半径为Ri的喷水装置，每个喷水装置的效果都会让以它为中心的半径为实数Ri(0Ri15)的圆被湿润，现有充足的喷水装置i（1i600)个，并且一定能把草坪全部湿润，问：如何选择尽量少的喷水装置，把整个草坪的全部湿润。 解题思路 题目思路：优先使用半径大的喷水装置——半径越大的喷水装置所能覆盖的范围就越大。 这个确定优先选择哪一个的过程就是贪心选择的过程。 先对所有的喷水装置半径排序，计算出每个喷水装置所能覆盖的长度。每次都选出当前半径最大的，直到能覆盖完所有的草地。 贪心算法的证明 贪心算法是从局部的最优解去找全局的最优解，所以很有可能只看眼前不看长远，很有可能走错路。 证明贪心算法的正确性就是一件极为重要的问题。 小结 贪心算法主要用于处理优化问题。每个优化问题都是由目标函数和约束条件组成。满足约束条件的解称为可行解，而那些使得目标函数取得最大（最小）值的可行解称为最优解。如背包问题是一个优化问题，优化是使目标函数取最大值。 贪心算法在每一步的决策中虽然没有完全顾忌到问题整体优化，但在局部择优中是朝着整体优化的方向发展的。为此，贪心算法首先要确定一个度量准则（称为贪心准则），每一步都是按这个准则选取优化方案。 贪心算法抽象化控制流程 Greedy(A, n) // A[1:n]代表那个输入 solution={}; //解向量初始化为空集 for i to n do x:=Select(A) if Feasible(solution, x) then solution:=Union(solution, x) end if End for Return (solution) 背包问题实例 考虑下列情况的背包问题 n=3,M=20,(v1,v2,v3)=(25,24,15),(w1,w2,w3)=(18,15,10) 背包问题贪心算法 GreedyKnapsack (p, w, M, x, n) // M是背包容量，x是解向//量,价值数组p[1..n]、重量数组w[1..n]，它们元素的排列顺//序满足p[i]/w[i]≥p[i+1]/w[i+1] x= 0 // 将解向量初始化为零 rc= M // 背包的剩余容量初始化为M for i to n do if w[i] rc then break end if x[i]:=1, rc:=rc-w[i]; end for if i≤n then x[i]:=rc/w[i]; end if 计算每种物品单位重量的价值Vi/Wi，然后，依贪心选择策略，将尽可能多的单位重量价值最高的物品装入背包。若将这种物品全部装入背包后，背包内的物品总重量未超过C，则选择单位重量价值次高的物品并尽可能多地装入背包。依此策略一直地进行下去，直到背包装满为止。 0-1背包问题与背包问题 对于0-1背包问题，贪心选择之所以不能得到最优解是因为在这种情况下，它无法保证最终能将背包装满，部分闲置的背包空间使每公斤背包空间的价值降低了。 事实上，在考虑0-1背包问题时，应比较选择该物品和不选择该物品所导致的最终方案，然后再作出最好选择。由此就导出许多互相重叠的子问题。这正是该问题可用动态规划算法求解的另一重要特征。 实际上也是如此，动态规划算法的确可以有效地解0-1背包问题。 解决活动安排问题的基本思路是在安排时应该将结束时间早的活动尽量往前安排，也就是说，使剩余的可安排时间段极大化，从而达到安排最多活动的目的。 据此，贪心准则应当是：在未安排的活动中挑选结束时间最早的活动安排。 在贪心算法中，将各项活动的开始时间和结束时间分别用两个数组s和f存储，并使得数组中元素的顺序按结束时间非减序排列：f1≤ f2≤…≤ fn。 活动安排贪心算法伪代码 GreedyAction(s, f，n) // s[1..n]、f[1..n]分别代表n项活动的起始时间和结束时间, 并且满足f[1]≤ f[2]≤…≤ f[n] j:=1, solution:={1} //解向量初始化 for i from 2 to n do if si≥fj t