《贪心法(the greedy method)》由会员分享，可在线阅读，更多相关《贪心法(the greedy method)（74页珍藏版）》请在金锄头文库上搜索。
1、贪心法（The Greedy Method）宫秀军 天津大学计算机科学与技术学院 http:/ 提纲n最优化问题(Optimization problem)n贪心算法基本原理(The principle of greedy method)n贪心算法应用q货箱装船问题（Container Loading)q背包问题（Knapsack Problem）q拓扑排序问题(Topological Sorting )q最短路径问题(Shortest Path)q最小代价生成树(Minimum Spanning Tree)n本章小结13.1优化问题n一个优化问题可以描述如下:q问题的解可表示为一复杂的 结
2、构，例如元组形式q约束条件(结构性的约束条 件n使约束条件为true的元 组称为可行解（feasible solution）q目标函数 n优化解即指使目标函数极大化( 或极小化)的可行解，对应的目标 函数值称为优化值。n很多优化问题是NP难度问题 ，迄今找不到它们的多项式算法 。所以计算上可行的方法就是求 其近似解。贪心法是求近似算法 的主要途径之一。例13.1Thirsty Babyn有一个聪明的婴儿，她可能得到的饮料包括 一桶水、一桶牛奶、多罐不同种类的果汁、许 多不同的装在瓶子或罐子中的苏打水。假定婴 儿可得到n 种不同的饮料。根据以前关于这n 种饮料的不同体验，婴儿知道其中那些饮料更
3、合自己的胃口。因此，婴儿为每一种饮料赋予 一个满意度值si：饮用1盎司第i 种饮料，满 意度si。n设第i种饮料有ai盎司，婴儿共需喝t盎司饮 料例13.1Thirsty Babyn设xi 为第i种饮料的饮 用量，假定满意程度是 可加的，则最满意的选 择是极大化n该优化问题可表示如下q约束条件q目标函数例13.2loading Problemn一艘船准备用来装载货物,所有货物都放在 集装箱中。设第i 个集装箱的重量为wi（ 1in），船的最大载重量为c，试设计一装 载方法使得装入的集装箱数目最多。例13.2 Loading Problemn用n维布尔向量代表一 种装箱方案n约束条件 n目标函数
4、n极大化目标函数例13.3 最小成本通信网络 n城市之间的通信网络应是以这些城市为顶点 的连通图,图的每条边代表一条通信线路.给每 条边赋予一个权值,等于建设这条通信线路所 要花费的成本,最小成本通信网络问题就是找 这样一个连通图,其总成本最小.n设所有的权值都非负,则最小成本通信网络问 题的可行解可限制为连接这些城市的生成树, 而最优解是其中具有最小成本的生成树.例13.3 最小成本通讯网络nn-1 条边的元组n约束条件：这些边构成生成树n目标函数：边权之和原则上所有上述问题需在很大的范围内搜索 优化解；但这常常导致指数复杂度的算法； 是计算上不可接受的。贪心法退而求其次求 所谓的“次优”解
5、。13.2 贪心法n贪心法指每步(stage)按所谓的“贪心标准(策略)”选择 (元组的)一个分量，逐步构造出问题解的方法。n贪心法的主要特点是：q分阶段完成：按一定的步骤，每步决定一个分量（自顶 向下）q不回溯：选定一个分量后,不重试其它可能q贪心标准：指每次选择一个分量时使用的“优化”策略。 所选策略可能导致优化解，但更多情形是得到近似解，特别 是对NP难度问题。不同的人可能有不同的“优化”策略。q常常采纳使目标函数有最大增量的策略为贪心策略。n基本要素q贪心选择性质:所求问题的整体最优解可以通过一系列局 部最优选择(贪心选择)来达到q最优子结构性质：问题的最优解包含其子问题的最优解例13
6、.4找零钱 n一个小孩买了价值少于1美元的糖，并将1美元的钱 放入取款机。取款机要用数目最少的硬币将零钱找给 小孩。假设取款机内有任意多的面值为25美分、10美 分、5美分、及1美分的硬币。n贪心策略为：每次给出不超过应找钱数的面值最大 的硬币。n贪心策略得到优化解: q20-25美分之间：选2个10美分最好. q25-30美分之间选一个25最好;q30美分：一个25加一个5美分等等.n硬币面值之间有倍数关系;否则没解:例如,面值 14,12,5和1;q则17125,用2枚硬币,而贪心法为14加3个1,共4枚硬 币.例13.5 机器调度 n现有n 个任务和足够多台处理这些任务的机器。q每个任务
7、的开始时间为si，完成时间为fi（ si10/9时,优化值9y.n误差为(9y-10)/9y.n对任意大的y误差可近似达到百分之百.例13.9 k-优化算法nk-优化算法是上述密度贪心算法的改进，改 进后其误差可控值在100/(k+1)之内.nk-优化算法：q预先将不超过k种物品的子集装入背包，对其余 物品用密度贪心法。q对所有k物品子集执行上述过程，并从中找到有 最大效益值的解。n考虑n=4, w=2,4,6,7, p=6,10,12,13, c=11。k2：q当k=0时，同于前述的密度贪心法。因此解为 x=1,1,0,0，效益值为16。例13.9(续1）nk =1时。初始子集为1 , 2
8、, 3 , 4。q子集1 , 2产生与k=0时相同的结果：x=1,1,0,0，效 益值为16。q考虑子集3，置x3 为1。此时还剩5个单位的容量，按价 值密度非递增顺序来考虑如何利用这5个单位的容量。首先 考虑物品1，它适合，因此取x1为1，这时仅剩下3个单位容 量了，且剩余物品没有能够加入背包中的物品。通过子集 3开始求解得结果为x=1,0,1,0，获得的价值为18。q若从子集4开始，产生的解为x=1,0,0,1，获得的价值 为19。nk=0,1时获得的最优解为1,0,0,1，获得的价值为19 。 n=4, c=11，w=2,4,6,7, p=6,10,12,13例13.9（续2）n若k=2
9、，除了考虑k0)得到的解误差不超过(100/(k+1)n当k=1时,为50%以内,即如优化值为100,贪心 法算出的值不低于50;当k=2时,为33.33%以内.n算法的时间复杂度随k 的增大而增加,需要测 试的子集数目为O(nk ),每一个子集所需时间为 O(n),因此当k 0时总的时间开销为O(nk+1 )。13.3拓扑排序拓扑排序定义：n任务的先后顺序可用有向图表示,称为AOV网 络(Activity On Vertex).有向图的顶点代表 任务,有向边(i,j)表示先后关系:任务i完成后 才能开始任务j .n根据上述AOV网络我们要对任务进行排序使 得排序序列的先后关系与AOV网定义的
10、先后关 系一致.根据任务的有向图建立拓扑序列的过 程称为拓扑排序.13.3拓扑排序n对所有顶点的排列逐个检验的方法是不足取 的:O(n!)的时间复杂度.n假设从空集开始，每步产生拓扑排序序列中 的一个顶点w,怎样选择顶点w？ngreedy策略:从不在拓扑序列的顶点中选择一 顶点w,其所有先行节点v都在已产生的拓扑序 列中(或无先行顶点). n用减入度的方法确定w:入度变成0的顶点使用栈的伪代码n(1)计算每个顶点的入度n(2)将入度为0的顶点入栈n(3)While(栈不空)任取一入度为0的顶点放入拓扑序列中;将与其相邻的顶点的入度减1;如有新的入度为0的顶点出现,将其放入栈中;n(4)如有剩余
11、的顶点则该图有环路引理13.1n如果伪代码13.5失败，则有向 图含有环路。n证明：当失败时|V| d(i) + cij then d(j) : = d(i) + cij and pred(j) : = i;nUpdate(i) is used in Dijkstras algorithm and in the label correcting algorithmUpdate(7)182713201469532131198d(7) = 6 at some point in the algorithm, because of the path 1-8-2-7Suppose 7 is incide
12、nt to nodes 9, 5, 3, with temporary distance labels as shown.We now perform Update(7). 87no changeOn UpdatesNote: distance labels cannot increase in an update step. They can decrease.We do not need to perform Update(7) again, unless d(7) decreases. Updating sooner could not lead to further decreases
13、 in distance labels.In general, if we perform Update(j), we do not do so again unless d(j) has decreased. 18271320146953213119887no changeDijkstras AlgorithmLet d*(j) denote the shortest path distance from node 1 to node j. Dijkstras algorithm will determine d*(j) for each j, in order of increasing
14、distance from the origin node 1. S denotes the set of permanently labeled nodes. That is, d(j) = d*(j) for j S. T denotes the set of temporarily labeled nodes. That is, d(j) d*(j) for j T.Dijkstras Algorithm begin S : = 1 ; T = N 1; d(1) : = 0 and pred(1) : = 0; d(j) = for j = 2 to n; update(1); whi
15、le S N do begin (node selection, also called FINDMIN) let i T be a node for which d(i) = min d(j) : j T; S : = S i; T: = T i; Update(i) end; end;Why Does Dijkstras Algorithm Work?A standard method for proving correctness.1.Determine things that are true at each iteration. These are called invariants. 2.Prove invariants using induction3.Prove that the algorithm is finite4.Choose invariants so that the algorithms correctness follows directly from the invariants and the fact that the algorithm terminates.Why Does Dijkstras Algorithm Work?nInv
