算法的设计.pptx

计算机算法计算机算法设计与分析第四章贪心算法2主要内容主要内容n n贪心算法的基本概念与要素n n几个实例：活动安排、最优装载、Huffman编码、单源最短路径、最小生成树、多机调度问题、带有完成期限的作业调度n n重点与难点：算法本身较简单，很少用递归；关键是如何选择贪心策略；如何证明你选择的贪心策略能获得最优解。例例3贪心算法概述贪心算法概述n n贪心算法也称为优先策略顾名思义是“择优录取”，在某些方面的应用是非常成功的，也是我们设计算法时经常使用的一种策略。国外叫做Greedy method，意即见到好的就抓住不放。它并不一定对所有问题都成功，但是对某些问题特别简单、有效。n n在贪婪算法中采用逐步构造最优解的方法。在每个阶段，都作出一个看上去最优的决策（在一定的标准下）。决策一旦作出，就不可再更改。作出贪婪决策的依据称为贪婪准则(criterion)。4n n贪心算法常常用于求解某些问题得最优解。n n这类问题一般有n个输入，而其解由这n个输入的某个子集组成，要求该子集满足预先给定的约束条件。这一子集称为该问题的一个可行解。其中使目标函数取得极值的可行解称为最优解。NN个输入个输入约束条件约束条件可行解可行解准则准则最优解最优解贪心法的关键是找到一个衡量优劣的标准，然后把n个输入按这种标准排序并尝试局部解。5n n如果这个输入和当前的部分解加起来不能产生一个可行解，则不把此输入加入到部分解当中。6n n一般地，选取最优度量标准并非易事，因此贪心法得到的解往往不是最优解，而是次优解。而一旦找到最优度量标准，则贪心法特别有效。n n贪心法逐步给出解的各部分，在每一步“贪婪地”选择最好的部分解，而不顾及这样选择对整体的影响，因此未必得到最优解。n n贪心法应用的成功示例有：单源最短路径问题、最小生成树问题以及作业调度等。即使得不到最优解，往往能得到较好的近似解。7n n例1找零钱：一个小孩买了价值少于1美元的糖，并将1美元的钱交给售货员。售货员希望用数目最少的硬币找给小孩。假设提供了数目不限的面值为2 5、1 0、5、1美分的硬币。售货员分步骤组成要找的零钱数，每次加入一个硬币。选择硬币时所采用的贪心准则如下：每一次选择应使零钱数尽量增大。为保证解法的可行性（即：所给的零钱等于要找的零钱数），所选择的硬币不应使零钱总数超过最终所需的数目。8n n假设需要找给小孩6 7美分，首先入选的是两枚2 5美分的硬币，第三枚入选的不能是2 5美分的硬币，否则硬币的选择将不可行（零钱总数超过6 7美分），第三枚应选择1 0美分的硬币，然后是5美分的，最后加入两个1美分的硬币。n n贪婪算法有种直觉的倾向，在找零钱时，直觉告诉我们应使找出的硬币数目最少（至少是接近最少的数目）。可以证明采用上述贪婪算法找零钱时所用的硬币数目的确最少。9n n例2：找零钱问题与硬币面值的设定有关。n n比如：要找给顾客3角7分钱，如果硬币面值为1角、5分、2分、1分，那么按照贪心算法：1角：3枚；5分：1枚；2分：1枚 合计：5枚 能得到最优解。n n如果硬币面值为11分、7分、5分、1分，那么按照贪心算法：11分：3枚；1分：4枚 合计：7枚但最优解应该是5枚，贪心法不成功。10背包问题背包问题n n假设：n=3,c=20,(w1,w2,w3)=(18,15,10)(v1,v2,v3)=(25,24,15)n n四个可行解：n n 重量 价值 （1/2，1/3，1/4）16.5 24.25 （1，2/15，0）20 28.2 （0，2/3，1）20 31 （0，1，1/2）20 31.5选取度量标准是用贪心法求解问题的关键。11n n用贪心算法求解背包问题的步骤：1）计算每种物品的单价vi/wi2）按物品的单价，从大到小排序3）单价高的物品优先装包，直至装满。（最后一种物品可能装入一部分）n n时间复杂性 排序：O(n log n)其它：O(n)n n为什么采用贪心策略能得到最优解？12n n0/1背包问题的几种贪婪策略：1）从剩余的物品中，选出可以装入背包的价值最大的物品2）从剩下的物品中选择可装入背包的重量最小的物品3）从剩余物品中选择可装入包的pi/wi 值最大的物品n n这三种策略都不能保证得到最优解。n n我们不必因所考察的几个贪婪算法都不能保证得到最优解而沮丧，0/1背包问题是一个NP复杂问题。对于这类问题，也许根本就不可能找到具有多项式时间的算法。13n n虽然按pi/wi 非递增的次序装入物品不能保证得到最优解，但它是一个直觉上近似的解。我们希望它是一个好的启发式算法，且大多数时候能很好地接近最后算法。n n据统计，在600个随机产生的背包问题中，用这种启发式贪婪算法来解有239题为最优解。有583个例子与最优解相差10%，所有600个答案与最优解之差全在25%以内。该算法能在O(n log n)时间内获得如此好的性能。我们也许会问，是否存在一个x(x100)，使得贪婪启发法的结果与最优值相差在x%以内。答案是否定的。14n n为什么贪心策略不适用于0/1背包问题？n n例：c=50,w=(10,20,30),V=(60,100,120)n n单价 v/w=(6,5,4)按贪心策略，应装入前两个物品，价值160；而最优解应为装入后两种物品，价值220。n n原因：贪心法不能保证0/1背包装满，闲置部分使背包价值降低。n n考虑0/1背包问题，应比较选择wi与不选择wi所导致的结果，然后作出选择，由此导致相互重叠的子问题。所以可用动态规划法。15void Knapsack(int n,float M,float v,float w ,float x)Sort(n,v,w);/按单位价值排序/int i;for(i=1;i=n;i+)xi=0;float c=M;/c为背包剩余空间/for(i=1;i c)break;xi=1;c-=wi;if(i=n)xi=c/wi;算法分析算法分析:排序为主要算法时间,所以 T(n)=O(nlogn)背包问题的贪心算法背包问题中的物体不能分拆背包问题中的物体不能分拆,只能整个装入称为只能整个装入称为0-10-1背包问题背包问题.算法证明算法证明:该算法能得到在最优解 用贪心算法能得到用贪心算法能得到0-10-1背包的最优解吗背包的最优解吗?16贪心算法的基本要素贪心算法的基本要素n n贪心法在作每一次选择时，都是当前状态下的最好选择，希望以此得到整个问题的最优解。能否奏效？n n用贪心法求解的问题应具备两个特性：（1）最优子结构性质 问题的最优解包含着子问题的最优解。（2）贪心选择性质 局部最优解的选择整体最优解17n n贪心法与动态规划法的比较贪心法：当前状态下，局部最优选择，然后求解作出此选择之后的子问题。贪心选择依赖于以往作出的选择，但不受将来所作的选择，既不依赖于子问题的解。动态规划法：每步所作的选择依赖于相关子问题的解，只有在解出相关子问题以后，才能作出选择。n n如何证明一个问题具有贪心选择性质？思路：证明每步贪心选择问题的整体最优解。18n n证明步骤：1）假设问题有一个整体最优解。2）修改这个最优解，使其以贪心选择开始，并且证明修改后的解仍然为最优解。3）运用数学归纳法，证明：每一步贪心选择问题的整体最优解。因为作出贪心选择以后，根据最优子结构性质，原问题转化为规模更小的子问题。