第五章-贪心算法课件

第第5章章 贪心法贪心法信工计算机系信工计算机系2008本章学习内容本章学习内容 n贪心法设计方法及基本要素n贪心法举例：背包问题、货郎担问题 最优装载、活动安排、多机调度等5.1 5.1 贪心法设计方法及基本要素贪心法设计方法及基本要素例5.1 货币兑付问题 解：解：约束条约束条约束条约束条件件件件目标函目标函目标函目标函数数数数5.1 5.1 贪心法设计方法及基本要素贪心法设计方法及基本要素这类最优问题，是在问题的解空间中，搜索满足约束条件且使目标函数达到极值的解向量。其中满足约束条件的解称为问题的可行解，使目标函数取极值的可行解，称为最优解。共2n个不同的向量，可用穷举法求解。本章讲解解此类问题的简单算法贪心算法。例5.1中，问题的解空间：贪心法通常用来解决具有最大值或最小值的优化问题。通常从某一个初始状态出发，根据当前局部而非全局的最优决策，以满足约束方程为条件，以使得目标函数的值增加最快或最慢为准则，选择一个最快地达到要求的输入元素，以便尽快地构成问题的可行解。贪心法设计方法贪心法设计方法其设计方法描述如下：选择准则选择准则例例5.25.2 用贪心法求解货币兑付问题。设支付现金用贪心法求解货币兑付问题。设支付现金 A=25.9 A=25.9元，支付集合元，支付集合P=10P=10、5 5、1 1、0.5,0.2 0.5,0.2、0.10.1元各元各1010张张 解：解：贪心法设计举例贪心法设计举例最少货币张数最少货币张数 贪心选择货币面值大者。贪心选择货币面值大者。s=s=10 15.9 s=10,10 5.9 s=10,10,5,0.5,0.2,0.2 0贪心法通过一系列选择得到问题的解。其所做出的贪心法通过一系列选择得到问题的解。其所做出的每一个选择都是当前状态下的局部最好选择，即贪每一个选择都是当前状态下的局部最好选择，即贪心选择。心选择。贪心法并不总能得到问题的最优解贪心法并不总能得到问题的最优解用贪心法求解的问题一般具有两个重要性质：用贪心法求解的问题一般具有两个重要性质：贪心选择性质贪心选择性质 最优子结构性质最优子结构性质 贪心法基本要素贪心法基本要素是指所求问题的整体最优解可以通过一系列局部是指所求问题的整体最优解可以通过一系列局部最优的选择（仅依赖于以往所做过的选择，不依赖最优的选择（仅依赖于以往所做过的选择，不依赖于将来所做的选择），即贪心选择来达到。每做出于将来所做的选择），即贪心选择来达到。每做出一次贪心选择将所求问题简化为规模更小的子问题。一次贪心选择将所求问题简化为规模更小的子问题。贪心法基本要素贪心法基本要素贪心选择性质贪心选择性质当一个问题的最优解包含其子问题的最优解时，称当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。此问题具有最优子结构性质。贪心法基本要素贪心法基本要素最优子结构性质最优子结构性质n问题原型有两类背包问题：物体可分割本节研究物体不可分割0/1背包问题，后续章节研究5.2 5.2 贪心法例贪心法例 背包问题背包问题即求X=(x1,x2,xn)，满足上述优化方程。背包问题的数学描述背包问题的数学描述1.1.价值最大价值最大 贪心选择价值大者贪心选择价值大者 例：背包重量10 物体1：重量9 价值5 物体2：重量4 价值4 物体3：重量3 价值2 选物体1，x1=1；剩余可装重量1，价值5 选物体2，x2=0.25；剩余0，价值6 但若令但若令X=(1/3,1,1);X=(1/3,1,1);则背包价值为则背包价值为7.6677.667 因此此贪心选择不一定达到最大价值。因此此贪心选择不一定达到最大价值。贪心法解背包问题解法贪心法解背包问题解法1 1 2.2.价值最大价值最大 贪心选择贪心选择价值价值/重量重量大者大者 例：背包重量例：背包重量10 物体物体1：重量：重量9 价值价值5 物体物体2：重量：重量4 价值价值4 物体物体3：重量：重量3 价值价值2 贪心法解背包问题解法贪心法解背包问题解法2 2 贪心选择物体2 w2m,故x2=1;m=m-w2=6 p=p+p2=4 贪心选择物体3 w3m,故x3=1;m=m-w3=3 p=p+p3=6 贪心选择物体1 w1m,故x1=m/w1=1/3 p=p+p1*x1=7.667 最优解为：X=(1/3，1，1）。贪心算法的重点是找到正确的贪心选择标准初始：背包剩余重量m=M=10 背包当前价值p=0对物体按价值/重量的降序排序，得2 3 1 时间复杂性分析时间复杂性分析时间复杂性分析时间复杂性分析：排序O(nlogn)，贪心选择O(n)，故时间复杂性为O(nlogn)。最优解分析：最优解分析：最优解分析：最优解分析：设物体1,物体2,物体n已按价值重量比的降序排序。贪心选择性质：贪心选择性质：设X=x1,x2,xn是背包问题的一个最优解。令k=mini|xi0,1in，若k=1，则X是以贪心算法开始的最优解。贪心法解背包问题算法分析贪心法解背包问题算法分析说明：证明贪心选择性质的一般方法是：首先假设问题的一个整体最优解，并证明可修改这个最优解，使其以贪心算法开始。若k1，令Z中zk=0，z1=wkxk/w1，zi=xi(1in，ik，i1)最优子结构性质：最优子结构性质：贪心选择物体1之后，问题转化为背包重量为m-w1*x1，物体集为物体2,物体3,，物体n的背包问题。且该问题的最优解包含在初始问题的最优解中。n问题原型某售货员要到若干个城市销售货物，已知各城市之间的距离，要求售货员选择出发的城市及旅行路线，使每个城市经过一次，最后回到原出发城市，而总路程最短。5.3 5.3 贪心法例贪心法例 货郎担问题货郎担问题货郎担问题数学描述货郎担问题数学描述 求距离最短的哈密尔顿回路，需求从各城市出发的 最短回路，再对n条回路求极小值。回路最短贪心选择距离短的路线 贪心法解货郎担问题贪心法解货郎担问题 例：假设5个城市的费用矩阵为：33263732372523236253 1 2 3 4 512345从城市1出发：1-4-3-5-2-1，总距离14从城市2出发：2-5-4-1-3-2，总距离17其它城市同理，再在5条回路中选择最小距离。时间复杂性分析：从一个城市出发的最短回路计算为O(n2)，共n个城市，故时间复杂度为O(n3)，远小于穷举法的n!。最优解分析：从城市1出发最优路线：1-2-5-4-3-1，距离13贪心法求解货郎担问题不具有贪心选择性质和最优子结构性质。只能得到近似解，不能得到最优解。贪心法解货郎担问题算法分析贪心法解货郎担问题算法分析n问题原型假设有n个集装箱，其中集装箱i的重量为wi，最优装载问题要求在装载体积不受限制的情况下，将尽可能多的集装箱装上载重量为c的轮船。5.4 5.4 贪心法例贪心法例 最优装载问题最优装载问题最优装载问题数学描述最优装载问题数学描述目标是装入集装箱个数最多贪心选择重量轻者优先 例：c=100吨 w1=10吨 w2=30吨 w3=20吨 w4=40吨 初始剩余载重g=100 装入个数k=0 贪心选择w1 w1g 故x1=1 g=g-w1=90 k=1 贪心选择w2 w2g 故x2=1 g=g-w2=60 k=2 同理，继续。得X=1，1，1，1贪心法解最优装载问题贪心法解最优装载问题时间复杂性分析：排序O(nlogn)，贪心选择O(n),故时间复杂性为O(nlogn)最优解分析：具有贪心选择性质和最优子结构性质，能得到问题的最优解。贪心法解最优装载问题算法分析贪心法解最优装载问题算法分析n问题原型5.5 5.5 贪心法例贪心法例 活动安排问题活动安排问题按fi非减序对活动排序 相容活动子集合最大贪心选择与已选活动相容，且fi小者。贪心法解活动安排问题贪心法解活动安排问题例：设待安排的11个活动的开始时间和结束时间按 结束时间的非减序排列如下：i1234567891011si130535688212fi4567891011121314用贪心法求其最大相容活动子集。解为：1、4、8、11时间复杂性分析：排序的时间复杂度O(nlogn)，贪心选择的时间复杂度O(n)，故时间复杂度为O(nlogn)。最优解分析：该贪心算法具有贪心选择性质和最优子结构性质，能得到问题的最优解。贪心法解活动安排问题算法分析贪心法解活动安排问题算法分析n问题原型5.6 5.6 贪心法例贪心法例 多机调度问题多机调度问题调度时间最短贪心选择作业执行时间大者，将其调度到可最早开始加工它的机器上。贪心法解多机调度问题贪心法解多机调度问题例：设7个作业的执行时间如下表，将在3机器上加 工处理。请给出它们的调度安排。i1234567ti7345383贪心法解多机调度问题贪心法解多机调度问题解：设分别用T3表示3台机器的最早开始时间。初始：T0=T1=T2=01.选作业6，调度至机器0，T0=82.选作业1，调度至机器1，T1=7 作业排序得：6 1 4 3 2 5 7 3.选作业4，调度至机器2，T2=54.选作业3，调度至机器2，T2=9 5.选作业2，调度至机器1，T1=106.选作业5，调度至机器0，T0=117.选作业7，调度至机器2，T2=12调度示意图如下所示：6（8）5（3）1（7）2（3）4（5）3（4）7（3）P0P1P2时间复杂性分析：O(nlogn+nlogm)多机问题不一定得到最优解：不具有贪心选择性质和最优子结构。多机调度是NP完全问题，贪心算法得到其近似解。贪心法解多机调度问题算法分析贪心法解多机调度问题算法分析上例的一种最优调度示意图如下所示：P0P1P26(8)5(3)1(7)3(4)4(5)2(3)7(3)p经常不断地学习,你就什么都知道。你知道得越多,你就越有力量pStudyConstantly,AndYouWillKnowEverything.TheMoreYouKnow,TheMorePowerfulYouWillBe写在最后Thank You在别人的演说中思考，在自己的故事里成长Thinking In Other PeopleS Speeches，Growing Up In Your Own Story讲师：XXXXXX XX年XX月XX日