文档介绍：2017-3-2第三章贪心方法华中科技大学计算机学院 2017-3-2 一般方法 1. 问题的一般特征问题有 n个输入,问题的解是由这 n个输入的某个子集组成,这个子集必须满足某些事先给定的条件。?约束条件:子集必须满足的条件; ?可行解:满足约束条件的子集;可行解可能不唯一; ?目标函数:用来衡量可行解优劣的标准,一般以函数的形式给出; ?最优解:能够使目标函数取极值(极大或极小)的可行解。分类:根据描述问题约束条件和目标函数的数学模型的特性和问题的求解方法的不同,可分为:线性规划、整数规划、非线性规划、动态规划等。——最优化问题求解贪心方法:一种改进的分级的处理方法,可对满足上述特征的某些问题方便地求解。 2017-3-2 2. 贪心方法的一般策略问题的一般特征:问题的解是由 n个输入的、满足某些事先给定的条件的子集组成。 1 )一般方法根据题意,选取一种度量标准。然后按照这种度量标准对 n个输入排序,并按序一次输入一个量。如果这个输入和当前已构成在这种量度意义下的部分最优解加在一起不能产生一个可行解,则不把此输入加到这部分解中。否则,将当前输入合并到部分解中从而得到包含当前输入的新的部分解。 2 )贪心方法这种能够得到某种量度意义下的最优解的分级处理方法称为贪心方法注: ?贪心解最优解?直接将目标函数作为量度标准也不一定能够得到问题的最优解 3 )使用贪心策略求解的关键选取能够得到问题最优解的量度标准。?= 2017-3-2 3. 贪心方法的抽象化控制描述 procedure GREEDY(A,n) //A(1:n) 包含 n个输入// solution ←Φ // 将解向量 solution 初始化为空// for i ← 1 to n do x ← SELECT(A) // 按照度量标准,从 A中选择一个输入,其值赋予 x 并将之从 A中删除// if FEASIBLE(solution,x) then // 判定 x是否可以包含在解向量中, 即是否能共同构成可行解// solution ← UNION(solution,x) // 将x和当前的解向量合并成新的解向量,并修改目标函数// endif repeat return end GREEDY 2017-3-2 背包问题 n种物品具有重量(w 1 ,w 2,…,w n)和效益值(p 1 ,p 2,…,p n ) ,及一个可容纳 M重量的背包;设当物品 i全部或一部分 x i放入背包将得到 p i x i的效益,这里, 0≤x i≤1, p i >0 。问题:采用怎样的装包方法才能使装入背包的物品的总效益最大? 分析: ①装入背包的总重量不能超过 M ②如果所有物品的总重量不超过 M,即≤M,则把所有的物品都装入背包中将获得最大可能的效益值③如果物品的总重量超过了 M,则将有物品不能(全部)装入背包中。由于 0≤xi≤1,所以可以把物品地一部分装入背包,所以最终背包中可刚好装入重量为 M的若干物品(整个或一部分) 目标:使装入背包的物品的总效益达到最大。???ni iixw 1 2017-3-2 问题的形式描述目标函数: 约束条件: 可行解:满足上述约束条件的任一集合(x 1 ,x 2,…,x n)都是问题的一个可行解——可行解可能为多个。 (x 1 ,x 2,…,x n)称为问题的一个解向量最优解:能够使目标函数取最大值的可行解是问题的最优解——最优解也可能为多个。???ni iixp 1niwpx Mxw iii ni ii??????????1,0,0,10 1 2017-3-2 例 背包问题的实例设, n=3 , M=20 , (p 1 ,p 2 ,p 3 ) = (25,24,15) , (w 1 ,w 2 ,w 3 ) = (18,15,10) 。可能的可行解如下: (x 1 ,x 2 ,x 3)①(1/2,1/3,1/4) //没有放满背包// ②(1, 2/15, 0 ) 20 ③(0, 2/3, 1) 20 31 ④ (0, 1, 1/2) 20 ? iixp? iixw 2017-3