|
|
|
17. 1引言
首先通过对一个简单理论的讨论，初步理解贪婪思想。以下棋为例，每一步的决策都需要考虑对后续棋局的影响。而在网球(或排球)比赛中，选手的行为仅取决于当前的状况，选择当下最为正确的动作，而不关心后续的影响。这说明在某些情况下选择当下最佳行为的决策，可以得到一个最优解(贪婪)，但并非所有情况都如此，贪婪策略适用于上述第二类问题。
17. 2贪婪策略的定义
贪婪算法将问题分为多个阶段。在每一个阶段，选取当前状态下的最优决策，而不考虑对后续决策的影响。这意味着算法在执行过程中会选取某些局部最优解。贪婪法假.设通过局部最优解可以获得全局最优解。
17.3贪婪算法的要素
最优贪婪算法需要满足两个基本性质:
[list=1,
[*,贪婪选择性质。
[*,最优子结构。
[/list,贪婪选择性质:全局最优解可以通过寻找局部最优解获得(贪婪)，局部最优解的选择可能依赖于之前的决策，而不是后续的决策。通过迭代方式算法进行一一个个贪婪选择，将原问题简化为规模更小的问题。
最优子结构:如果原问题的最优解包含子问题的最优解，则认为该问题具有最优子结构。这意味着可以对子问题求解并构建规模更大问题的解。
17.4贪婪算法的适用范围
选择局部最优解不是对于所有问题都适用，所以贪婪算法并不总是能得到最优解。在17.8节和第19章将给出这样的例子。
17.5贪婪算法的优缺点
贪婪算法的优点是直观，易于理解，并易于编码实现。当前的决策不会对已经计算出的结果有任何影响，因此不需要再对已有的局部解进行检查。缺点是，对于许多问题，无法用贪婪算法求解。即在许多情况下，无法保证局部最优解能够产生全局最优解。
17.6 贪婪算法的应用
[list,
[*,排序问题:选择排序、拓扑排序。
[*,优先队列:堆排序。
[*,赫夫曼编码压缩算法
[*,Prim和Kruskal算法。
[*,加权图的最短路径问题(Dijkstra算法)。
[*,硬币找零问题
[*,分数背包问题。
[*,并查集的按大小或高度合并问题(或排名)。
[*,任务调度算法。
[*,贪婪算法可用于求解复杂问题的近似算法。
[/list,17.7贪婪思想
本节通过-一个例子来更好地理解贪婪思想，更多细节参见17.6节的相关主题。赫夫曼编码算法
定义:给定来自字母表A的n个字符的集合(字符c∈A)，并已知每个字符出现的频率freq(c)，为每-一个字符c∈A找到一个二进制编码，使得> freq(c) | binarycode(c) |c∈A的值最小，其中| binarycode(c) |表示字符c的二进制编码的长度。以上公式表明所有字符编码长度之和(每个字符出现频率与编码的位数乘积之和)最小。
赫夫曼编码算法的基本思想是，对于出现频率较大的字符用更少的位来编码。利用可变长度编码，赫夫曼算法可以压缩数据存储所需的空间。计算机系统采用8位来表示每一个字符， 但并非所有的位都被使用。此外，某些字符的使用更为频繁。当读取一个文件时，系统通常每次读取8位来确定-一个字符。但是这种8位编码机制是低效的，因为相比而言，有些字符使用更为频繁。例如，字符‘e'往往比字符‘q'的使用频率高10倍。
因此，如果对于字符‘e'用7位编码，而‘q'用9位编码，这将减少整个消息的长度。平均而言，对于标准文件，使用赫夫曼编码在长度上能够减少10%~30%，具体的值取决于字符的频率。这种编码思想是，对于较少使用的字符或字符组采用较长的二进制编码。此外，赫夫曼编码满足任意两个字符的编码互不为前缀。
例子:假设扫描一个文件，得出以下字符频率:
首先，为每一个字符创建- - 棵二叉树，并将其出现频率存储在结点中(见下图)。
赫夫曼算法的流程如下:在列表中寻找根结点中存有最小频率值的两棵二叉树，创建一个不存储任何字符的结点，将这两棵二叉树作为新建结点的左右子树，并将其孩子结点的频率值之和存储到新建结点中。由此可以得出下图:
重复.上述过程直至仅剩下一棵树。
当树构造完后，每一个叶子结点对应于一个字母及其编码。从根结点遍历到叶子结点，就可以得到每一一个结点的编码。对于左分支，在编码中添加0;对于右分支，添加1。对于.上述产生的树，可以得到以下编码:
计算减少的位数:接下来对使用赫夫曼编码减少的位数进行统计，只需要用原始的数据存储位数减去采用赫夫曼编码后的存储位数。
在本例中，由于仅有6个字母，所以假设每个字母用3位进行编码。因为共有133个字符(总频率乘以3)，所以需要的总位数为3X133=399。使用赫夫曼编码，所需要的位数是:
因此，减少了399-238=161位，将近减少40%的存储空间。
HuffmanCodingAlgorithm(int A,, int n) {
//在A中初始化一个包含n个元素的优先队列PQ;
Heap PQ = new Heap0;
BinaryTreeNode temp;
for (i= 1;i<n; i++) {
temp = new BinaryTreeNode);
temp.setLeft(PQ .deleteMin;
temp.setRight(PQ.DeleteMin;
temp.setData(temp.getLeft0.getData) + temp.getRight).getData0);
PQ.insert(temp);
}
return PQ;
}
时间复杂度为O(nlogn)，其中包含在不超过n个元素的优先队列上的--个建堆操作，2n-2次堆删除操作和n-2次堆插入操作，详见第7章。
17. 8贪婪算法的相关问题
问题1给定一个 大小为n的数组F，数组元素F[i,表示第i个文件的长度。现在需要将所有文件合并成一个文件，以下算法是否提供了该问题的最优解?
算法:依次连续合并文件，即按照默认顺序选择最前两个文件进行合并，然后将合并后的文件与第三个文件合并，以此类推。
注意:给定大小分别为m和n的两个文件A和B，则合并的复杂度为O(m+n)。
解答:上述算法不是最优的求解算法。下面给出反例，假设文件大小的数组F如下。
F= {10]5, 100]50]20]15}
根据上述算法，首先合并前两个文件(大小分别为10和5)，合并后的文件列表如下，其中15表示合并大小为10和5两个文件的代价。
{15,100 ,50 ,20]15}
同理，合并大小为15的文件和下一个大小为100 的文件，得到{115，50，20， 15}。以此类推，产生的文件列表如下:
{165,20]15}
{ 185,15}
最后为
{200}
合并的总代价=所有合并代价之和=15+115+ 165+ 185 + 200=680。为了确定上述结果是否是最优解，考虑文件的另一种排列: {5，10，15，20，50，100}。 对于该例，同样按照上述过程，合并总代价=15+30+ 50+ 100+ 200=395。因此，该算法不能给出最优的解决方法。
问题2与问题1类似，以下算法是否给出问题的最优解?
算法:两两合并文件，即将文件依次两两分组合并。第一轮后，产生n/2个中间文件。接下来，将上一轮产生的中间文件两两分组合并，以此类推。
注意:有些文献将上述算法称为两路归并。若不是两两分组，而是一次合并K个文件，则称为K路归并。
解答:上述算法仍然不是最好的求解算法。仍然以上题中给出的例子作为反例进行说明。根据算法思想，第-轮中对第- -组(文件大小为10和5)、第二组(文件大小100和50)、第三组(20和15)分别合并，得到以下文件列表。
{15,150]35}
同理，将以上文件列表两两分组合并，结果为(最后一个分组中仅包含一个元素，结果保持不变):
{165,35}
最后为
{ 185}
合并的总代价=所有合并代价之和=15+150+ 35+165+ 185=550。该代价高于395(见问题1)，因此上述算法不能给出最好的解决方法。
问题3对于问题1， 将所有文件合并为一-个文件最好的方法是什么?
解答:使用贪婪算法降低文件合并的总时间。
算法:
1)按照文件的大小构建一个优先队列，元素的关键值为文件长度。
2)重复以下步骤直至队列中只有一个文件，
a. 选择两个最小的元素X和Y。
b. 将X和Y合并，并将合并后的新文件插入优先队列中。
同样算法的变形:
1)将所有文件按照文件大小进行升序排序。
2)重复以下步骤直至只有一个文件，
a.选择有序表中最前的两个元素(最小)X和Y。
b.合并X和Y，并将合并后的文件插入有序表中。
通过对前面例子的分析来分析上述算法的性能。已知数组
F= {10]5,100]50]20]15}
根据上述算法，对数组进行排序得到{5，10， 15，20，50，100}。合并两个最小的文件(大小分别为5和10)，结果如下所示，其中15表示合并大小为10和5两个文件的代价。
{15,15,20]50] 100}
同理，继续合并两个最小的文件(大小为15 和15)，得到{20，30， 50，100}。接下来，依次得到以下文件列表:
{50]50]100} //合并20和30
{100]100} //.合并20和30
最后为
{200}
合并的总代价=所有合并代价之和=15+ 30+ 50+ 100+ 200= 395。因此，该算法得到该合并问题最好的解决方法。
时间复杂度:使用堆查找最佳合并模式的时间开销O(nlogn)加上文件合并的最低代价。
问题4区间调度算法: 给定一个含n个区间的集合S={(start;，end;)| 1≤i≤n}，寻找S的一个最大子集S'，使得S'中任意- -对区间都不重合。分析以下算法是否可行?
算法:
while(S非空){
选择与其他区间重合数最少的区间I;
将I添加到最终解集合S'中;
将所有与I有重合的区间从S中删除;
}
解答:该算法不能找到非重合区间的最大子集。考虑以下区间，其最优解是{M, O,N，K}。然而，与其他区间重合数最小的是C,因此该算法首先选取C。
问题5对于问题 4，如果选择最先出现的区间(并且与已经选择的区间不重合)，则该算法是否能给出最优解?
解答:不能。该算法也不能给出最优解。反例如下，最优解为4，而该算法得到的解为1。
问题6对于问题4， 如果选择最短的区间(并且与已经选择的区间不重合)，此算法是否能给出最优解?
解答:该算法同样不能给出最优解。反例如下，最优解为2，而该算法得到的解为1。
问题7那么对于问题4， 最优解是什么?
解答:考虑使用贪婪算法寻找最优解。
算法:
将所有区间按照最右端(结束时间)进行排序
对每一个连续的区间{
如果其最左端在，上一一个选择区间的最右端之后，则选取该区间否则，舍弃该区间，进 入下一次迭代
}
时间复杂度=排序的时间+扫描的时间=O(nlogn+n)=O(nlogn)。
问题8考虑如下 问题。
输入:区间集合S= {(start;，end;) |1≤i≤n}。区间(start;，end;)表示在时间段start;到end;，某个课程在某个教室上的一一个使用申请。
输出:寻找所有课程的教室安排方案，使得占用教室最少。
算法:安排尽可能多的课程到第一间教室，然后安排尽可能多的课程到第二间教室,然后安排尽可能多的课程到第三间教室，以此类推。这个算法能否给出最优解?
注意:实际上，该问题与区间调度问题类似，只是应用背景不一样。
解答:.上述算法未解决区间着色问题，考虑如下例子:
最大化第一间教室安排的课程数，则{B, C, F, G}在同一间教室，课程A、D和E分别各占一-间教室，共需4间教室。最优方案是将A安排在一间教室，{B, C，D}安排在一间教室，{E，F, G}安排在一间教室，共3间。
问题9对 于问题8，考虑如下算法。根据课程开始时间按递增顺序依次处理，假设当前正在为课程C安排教室，如果教室R已经安排了C之前的课程，且将C安排到R不会与之前安排的课程重叠，那么将课程C安排到教室R，否则将C安排到一个新教室。这个算法能否解决该问题呢?
解答:上述算法能够解决区间着色问题。因为算法按照课程开始的时间顺序进行教室的安排，所以如果该贪婪算法为当前课程c;安排了一间新教室，这意味着c;的开始时间与所有已使用教室的最后一门课程的时间冲突。因此贪婪算法安排最后--间教室n，因为当前课程的开始时间与其他n-1间教室的课程相冲突。假设任何时刻，任何课程最多只与s门课程冲突，则必有n≤s，即s是所需教室总数的下界。综上可知，贪婪算法是可行的，可以给出最优解。
注意:求最优解的算法参见问题7，代码参见问题10。
问题10假设两个 数组Start[1..n,和Finish[1..n,分别给出每一个课程的开始时间和结束时间，现在需要寻找最大的子集X∈{1, 2，..，n}，使得其中任意两个元素i, j∈X满足Start[i,> Finish[j,或Start[i,> Finish[i,。
解答:目标是尽可能早地完成第一门课，这样为其他课程腾出更多的时间。按照结束时间的顺序轮询每一门课程，当时间不与上一门已选课程相冲突时，选择该门课程。
容易看出，该算法由于排序需要O(nlogn)的时间开销。
问题11思考印度 的货币找零问题。问题的输入为整数M,输出为兑换M卢比所需的最少硬币数。在印度，假设可用的硬币面额有1、5、10、20、25、50卢比，并且每--种面值的硬币数量不限。
对于该问题，以下算法能否给出最优解?
尽可能取用面额最高的硬币，例如，兑换234卢比的零钱，贪婪算法将使用4个面额50卢比的硬币，1个25卢布的硬币，1个5卢比的硬币和4个1卢比的硬币。
解答:对于面额为1. 5、10、20、25、50卢比的硬币找零问题，上述贪婪算法不能给出使硬币数最少的最优解。为了兑换40卢比的硬币，贪婪算法的结果为3个硬币，面额分别为25、10和5卢比，而最优解则为使用两个20先令的硬币。
注意:对于该问题的最优解，参见第19章。
问题12假设在城市 A和B进行长途自驾之旅。在准备旅行时，下载了一-份包含自驾路线上所有加油站之间距离(以英里为单位)的地图。假设汽车的油箱能装载使汽车行驶n英里的汽油(n为已知)。如果在每一个加油站都停车加油，是否是最优解?
解答:_上述算法不能给出最优解。原因很明显，在每-一个加油站均加油不能产生最优解。
问题13对于问题 12，当且仅当没有足够到下一个加油站的汽油时才停车，并且一旦停车，则将油箱加满油。证明该算法能够或不能解决上述问题。
解答:贪婪算法策略如下:将油箱装满油，从A开始旅行，根据地图决定在旅行路线.上n英里以内最远的加油站，在该加油站停车并加满油，然后再次根据地图决定从该停车点出发n英里以内最远的加油站，重复该过程直至到达B。
注意:算法代码参见第19章。
问题14分数背包问题: 有t，t2， ..，t,件物品(希望放入背包的物品)，其重量分别为s,，S2，..，sn，同时每件物品的回报值为U，Vr，...，Vn，在物品净重不超过C的前提下如何最大化回报值?
解答:
算法:
1)为每件物品计算单位重量的价值密度d;= v;/s;。
2)根据以上价值密度对物品进行排序。
3)尽可能多地将价值密度大的物品放入背包中。
时间复杂度:排序为O(nlogn)，贪婪选择为O(n)。
注意:将物品放入一个优先队列，然后一个一个拿出放入背包中直至背包装满或者所有的物品被取出。实际上，这将获得一个更好的运行时间复杂度O(n+clogn)，其中c为被选取物品的实际数量。如果c=O(n)，则运行时间会继续减少，否则复杂度不变。
问题15火车站台数: 一个火车站有一个所有火车到达和离开的时间表，需要找出最小的站台数，使得按照此时间表调度时，可以容纳所有的火车。例如，如下的时间表，最小站台数为3，否则车站将无法容纳所有的火车。
解答:从上面给出的例子可以看出，计算站台的数目等同于确定车站在任一时刻容纳的最大火车数。
首先，在一个数组中对到达时间(A)和离开时间(D)进行排序，将相应的到达或离开状态也保存在数组中。排序后的数组如下表所示。
其次，将数组中的A替换为1，D换成一1，替换后的数组为:
最后，根据上述数组计算-一个累积值数组:
数组中的最大值即为问题的解，这里是3。
注意:如果一列火车的到达时间与另一列火车的离开时间相同，则在排序数组中离开时间优先。
问题16假设某个国家有很长的马路， 居民的房子分散在马路两旁。居民使用移动电话，需要沿着马路架设移动电话基站，每- - 个基站覆盖范围为7千米。设计一个有效算法，使得需要的基站数最少。
解答:该算法用于定位最少数量的基站。
1)从马路起点处开始。
2)找到马路上第-一个未被覆盖的房子。
3)如果找不到这样的房子，则算法终止，否则转到下一步。
4)沿着马路在距离步骤2中的房子7英里处架设基站。
5)转到步骤2。
问题17准备音乐磁带: 假设有n首歌曲，需要将其存储到一盘磁带中。以后用户需要从磁带中读取这些歌曲，但从磁带中读一首歌曲与从磁盘中读取的方式不同。首先需要快进越过其他歌曲，这需要花费大量的时间。假设数组A[1..n,列出了每一首歌曲的长度，例如歌曲i的长度为A[门。如果歌曲按照1~n的顺序存储，那么访问第k首歌曲的开销为:
这个开销表明在访问第k首歌曲之前需要越过磁带前面的所有歌曲。如果改变磁带上歌曲的顺序，则访问歌曲的开销也随之改变。有些歌曲的访问变得非常耗时，而另一些则非常容易。不同的歌曲顺序可能导致不同的期望开销。如果假设每一首歌曲访问的可能性是相等的，那么采用何种歌曲顺序能够使得期望开销尽可能小?
解答:答案非常简单，按照从最短歌曲到最长歌曲的顺序存储，将较短的歌曲存储在靠前的位置减少了访问剩余歌曲的快进时间。
问题18考 虑海德拉巴会议中心( Hyderabad Convention Center，HITEX)的一 组活动安排，假设有n项活动，每项活动需要一个单位时长。如果活动i在时间T[i,或之前开始，则可以创收P[i,卢比(P[i,>0)，其中T[i,为-一个任意数字。如果直至T[i,活动还没开始，则无任何收入。所有活动最早开始时间为时刻0。设计一个有效算法，找到一个收入最大的活动调度方案。
解答:算法
[list,
[*,根据floor(T[i,)对所有活动进行排序(从大到小)。floor表示 下取整函数。
[*,令t为当前调度时刻(初始时t=floor(T[i,))。
[*,所有floor(T[i,)=t 的活动插入一一个优先队列，其收入g;作为关键字。
[*,执行DeleteMax操作选取--个在时刻t开始的活动。
[*,然后t自减，重复上述过程。
[/list,显然时间复杂度为O(nlogn)，其中排序花费O(nlogn)，算法中包含最多n次优先队列的插入和DeleteMax操作，每--个操作花费0(logn)。
如何确定服务客户的最好方法，使得总等待时间减少?
解答:这个问题可以使用贪婪方法轻易地解决。因为目标是减少总等待时间，所以要达到此目的只需选择服务时间较少的用户。即，如果按照服务时间递增的顺序服务顾客，就能够减少总等待时间。
时间复杂度为O(nlogn)。
以上是Java数据结构与算法——第十七章·贪婪算法设计技术整章，整本书为《数据结构与算法经典问题解析-Java语言描述》
本书共二十一章包括：
本书获取方式
关注+转发后，私信关键词 【书籍获得】即可获得本书电子版！
重要的话讲两遍，关注、转发后再发私信，才可以免费拿到哦！ |
|
发表于 2020-7-3 16:33:24
