《贪‘婪(贪心)算法》由会员分享，可在线阅读，更多相关《贪‘婪(贪心)算法（8页珍藏版）》请在金锄头文库上搜索。
1、贪婪算法分析与设计要使计算机能完成人们预定的工作，首先必须为如何完成预定的工作设 计一个算法，然后再根据算法编写程序。计算机程序要对问题的每个对象和 处理规则给出正确详尽的描述，其中程序的数据结构和变量用来描述问题的 对象，程序结构、函数和语句用来描述问题的算法。算法和数据结构是程序 的两个重要方面。算法是问题求解过程的精确描述，一个算法由有限条可完全机械地执行 的、有确定结果的指令组成。指令正确地描述了要完成的任务和它们被执行 的顺序。计算机按算法指令所描述的顺序执行算法的指令能在有限的步骤内 终止，或终止于给出问题的解，或终止于指出问题对此输入数据无解。通常 求解一个问题可能有多种算法可供
2、选择，选择的主要标准首先是算法的正确 性和可靠性，简单性和易理解性。其次是算法所需要的存储空间少和执行更一个算法应该具有以下五个重要的特征：1. 有穷性： 一个算法必须保证执行有限步之后结束；2. 确切性： 算法的每一步骤必须有确切的定义；3. 输入：一个算法有0 个或多个输入，以刻画运算对象的初始情况，所谓 0 个输入是指算法本身定出了初始条件；4. 输出：一个算法有一个或多个输出，以反映对输入数据加工后的结果。 没有输出的算法是毫无意义的；5. 可行性： 算法原则上能够精确地运行，而且人们用笔和纸做有限次运 算后即可完成。算法的描述可以有多种方式，如语言方式、图形方式、表格方式等。虽然设计
3、一个好的求解算法更像是一门艺术，而不像是技术，但仍然存在一些行之有效的能够用于解决许多问题的算法设计方法，可以使用这些方 法来设计算法，并观察这些算法是如何工作的。一般情况下，为了获得较好 的性能，必须对算法进行细致的调整。但是在某些情况下，算法经过调整之 后性能仍无法达到要求，这时就必须寻求另外的算法来求解该问题。常用的 算法主要有迭代法、穷举搜索法、递推法、贪婪法、回溯法、分治法、动态 规划法等。贪婪算法是一种不追求最优解，只希望得到较为满意解的方法。贪婪算 法一般可以快速得到满意的解，因为它省去了为找最优解要穷尽所有可能而 必须耗费的大量时间。贪婪法常以当前情况为基础作最优选择，而不考虑
4、各 种可能的整体情况，所以贪婪法不要回溯。一、贪婪算法的设计步骤1. 将最优化问题简化，经过选择仅剩下一个待解决的子问题。2. 证明作贪婪算法选择的原问题总是存在一个最优解，因此贪婪法是可 行的。3. 进一步证明在贪婪算选择后剩下的子问题具有如下性质，将一个最优解和贪婪选择后的子问题连接起来，我们将得到原问题的一个最优解。事实上，每一个贪婪算法后面，都总是存在一个更麻烦的动态规划解。 那么，我们如何来判断是否该用贪婪算法来解决一个特殊的最优化问题呢？ 一般来说，没有办法，但是贪婪算法有两个关键要素-贪婪选择特性和最优 子结构。如果我们能证明一个问题有这些性质，那么我们就已经在设计一个 贪婪算法
5、了。贪婪选择特性就是局部最优的贪婪选择可以得到整体的最优解，亦即贪 婪法以当前为基础作最优选择，而不考虑各种可能的整体情况。贪婪法的这 种特性使我们能高效地做出子问题的选择。一个问题的最优解如果包含在它的子问题的最优解中，则该问题就呈现 出最优子结构。这种特性对于动态规划法非常重要，对于贪婪法同样重要。 在贪婪法的应用中，我们大胆地假设通过贪婪选择我们已经得到了原问题的 一个子问题，我们真正需要做的是证明贪婪选择得到的子问题的最优解的集 合就是原问题的最优解。二、应用举例本文中例子都是最优化问题(optimization problem)，每个最优化问 题都包含一组限制条件(cons trai
6、n t)和一个优化函数(opt imiza tion function),符合限制条件的问题求解方案称为可行解(feasible solution)， 使优化函数取得最佳值的可行解称为最优解(op timal solu tion)。例 1 渴婴问题 有一个非常渴的、聪明的小婴儿，她可能得到的东西 包括一杯水、一桶牛奶、多罐不同种类的果汁、许多不同的装在瓶子或罐子 中的苏打水，即婴儿可得到 n 种不同的饮料。根据以前关于这 n 种饮料的不 同体验，此婴儿知道这其中某些饮料更合自己的胃口，因此，婴儿采取如下 方法为每一种饮料赋予一个满意度值：饮用 1 盎司第 i 种饮料，对它作出相 对评价，将一个
7、数值s作为满意度赋予第i种饮料。i通常，这个婴儿都会尽量饮用具有最大满意度值的饮料来最大限度地满 足她解渴的需要，但是不幸的是：具有最大满意度值的饮料有时并没有足够 的量来满足此婴儿解渴的需要。设a是第i种饮料的总量(以盎司为单位)，i而此婴儿需要 t 盎司的饮料来解渴，那么，需要饮用 n 种不同的饮料各多少量才能满足婴儿解渴的需求呢？设各种饮料的满意度已知，令x为婴儿将要饮用的第i种饮料的量，则需i要解决的问题是：找到一组实数x (lWiWn),使sx最大，并满足= ti i i ii-1i=1及 0W x W a。ii需要指出的是：如果a t,贝怀可能找到问题的求解方案，因为即使ii=1喝
8、光所有的饮料也不能使婴儿解渴。对上述问题精确的数学描述明确地指出了程序必须完成的工作，根据这些数学公式，可以对输入/ 输出作如下形式的描述：输入：n, t, s , a (其中lWiWn, n为整数，t、s、a为正实数)。iiii输出：实数x (lWiWn)，使丫 s x最大且丫 x =t (0Wx Wa )。如果ii iiiii=1i=1a t,则输出适当的错误信息。ii=1在这个问题中，限制条件是二t且0Wx Wa , lWiWn。而优化函数iiii=1是 s x。任何满足限制条件的一组实数x都是可行解，而使 s x最大的可行i iii ii=1i=1解是最优解。三、贪婪算法设计在贪婪算法
9、(greedy method)中采用逐步构造最优解的方法。在每个阶 段,都作出一个看上去最优的决策(在一定的标准下)。决策一旦作出,就 不可再更改。作出贪婪决策的依据称为贪婪准则(greedy cri terion)。例2 装载问题 有一艘大船准备用来装载货物。问题简述如下：设有编号为0,1,，n-1的n种物品，体积分别为v , v，v 。将这n种物01n -1品装到容量都为V的若干箱子里。约定这n种物品的体积均不超过V,即对于0WiVn,有0Vv WV。不同的装箱方案所需要的箱子数目可能不同，装箱问i题要求使装尽这n种物品的箱子数要少。若考察将n件物品的集合分划成n 个或小于n个物品的所有子
10、集，最优解就可以找到，但所有可能分划的总数 太大。对适当大的n,找出所有可能的划分要划分的时间是无法承受的。为此， 对装箱问题采用非常简单的近似算法，即贪婪法。该算法依次将物品放到它 第一个能放进去的箱子中，该算法虽然不能保证找到最优解，但还是能找到 非常好的解。不失一般性，设n件物品的体积是按从小到大排好序的，即有: v三v三三v 。如不满足上述要求，只要先对这n件物品按它们的体积从 0 1 n 1大到小排序，然后按排序结果对物品重新编号即可。装箱算法简单描述如下输入箱子的容积；输入物品种数 n；按体积从大到小顺序，输入各物品的体积；预置已用箱子链为空；预置已用箱子计数器box_count为
11、0；for(i=0;iVn;i+)从已用的第一只箱子开始顺序寻找能放入物品i的箱子j；if(已用箱子都不能再放物品i) 另用一只箱子，并将物品 i 放入该箱子； box_count+;else将物品 i 放入箱子 j；上述算法能求出需要的箱子数box_count,并能求出各箱子所装的物品。 但下面的例子说明该算法不一定能找到最优解。设有6 种物品，它们的体积 分别为：60, 45, 35, 20, 20, 20单位体积,箱子的容量为100 单位体积。 按上述算法计算,需三只箱子,各箱子所装物品分别为：第一只箱子装物品 1, 3；第二只箱子装物品 2, 4, 5；第三只箱子装物品 6。而最优解为
12、两只箱子, 如分别装物品 1, 4, 5 和2, 3, 6等。例3找零钱 一个小孩买了价值少于1 美元的糖,并将1美元的钱交给 售货员。售货员希望用数目最少的硬币找给小孩。假设提供了数目不限的面 值为 2 5 美分、1 0 美分、5 美分、及 1 美分的硬币。售货员分步骤组成要找 的零钱数,每次加入一个硬币。选择硬币时所采用的贪婪准则如下：每一次 选择应使零钱数尽量增大。为保证解法的可行性（即：所给的零钱等于要找 的零钱数）,所选择的硬币不应使零钱总数超过最终所需的数目。假设需要找给小孩6 7 美分,首先入选的是两枚2 5 美分的硬币,第三 枚入选的不能是25美分的硬币,否则硬币的选择将不可行
13、（零钱总数超过6 7美分）,第三枚应选择1 0美分的硬币,然后是5 美分的,最后加入两个1 美分的硬币。贪婪算法有种直觉的倾向,在找零钱时,直觉告诉我们应使找出的硬币 数目最少（至少是接近最少的数目）。可以证明采用上述贪婪算法找零钱时 所用的硬币数目的确最少。例4机器调度现有n件任务和无限多台的机器，任务可以在机器上得 到处理。每件任务的开始时间为S，完成时间为f，S f。S , f 为i i i i i i处理任务 i 的时间范围。两个任务 i，j 重叠指两个任务的时间范围区间有重 叠，而并非是指 i ，j 的起点或终点重合。例如：区间 1，4 与区间 2， 4 重叠，而与区间 4， 7 不
14、重叠。一个可行的任务分配是指在分配中没有 两件重叠的任务分配给同一台机器。因此，在可行的分配中每台机器在任何 时刻最多只处理一个任务。最优分配是指使用的机器最少的可行分配方案。假设有n=7件任务，标号为a到g。它们的开始与完成时间如下图所示。任务（n）abcdefgSi0349715fi277111058若将任务a分给机器M，任务b分给机器M ，-，任务g分给机器M ，1 2 7 这种分配是可行的分配，共使用了七台机器。但它不是最优分配，因为有其 他分配方案可使利用的机器数目更少，例如：可以将任务a、b、d分配给同 一台机器，则机器的数目降为五台。一种获得最优分配的贪婪方法是逐步分配任务。每步
15、分配一件任务，且 按任务开始时间的非递减次序进行分配。若已经至少有一件任务分配给某台 机器，则称这台机器是旧的；若机器非旧，则它是新的。在选择机器时，采 用以下贪婪准则：根据欲分配任务的开始时间，若此时有旧的机器可用，则 将任务分给旧的机器。否则，将任务分配给一台新的机器。根据例子中的数据，贪婪算法共分为 n=7 步，任务分配的顺序为 a、 f、 b、c、g、e、do第一步，没有旧机器，因此将a分配给一台新机器（比如M ）。1这台机器在0到2时刻处于忙状态。在第二步，考虑任务f。由于当f启动时旧机器仍处于忙状态，因此将 f 分配给一台新机器（设为 M ）。第三步，考虑2任务b,由于旧机器M在S =3时刻已处于闲状态，因此将b分配给M执行,1 b 1M下一次可用时刻变成f =7, M的可用时刻变成ff = 5。第四步，考虑任务1 b 2c,由于没有旧机器在S = 4时刻可用，因此将c分配给一台新机器（M ）,c3这台机器下一次可用时间为f = 7。第五步考虑任务g,将其分配给机器M， c2第六步将任务e分配给机器M ,最后在第七步，任务d分配给机器M。（注13
