利用贪婪算法实现多种实际问题
利用贪婪法实现多种实际问题
《算法设计与分析》课程设计任务书
学院名称：数学与计算机学院专业：信息与计算科学专业年级：2007
一、设计题目
题目十四：利用贪婪算法实现多种实际问题
二、主要内容
给出多种可以用贪婪算法解决的典型问题，并分析、证明、编程。
三、具体要求
（1）贪婪算法的基本思想；
（2）给出背包问题的贪婪算法；
（3）给出有限期计算机作业调度的贪婪算法；
（4）给出上面两个算法的证明；
（5）给出上面两个算法的程序。
（6）给出时间复杂度。
四、主要技术路线提示
在用贪婪算法解决资源分配问题、布线问题、0-1背包问题过程中，使用贪婪算法解决问题，通常需要做好以下几个方面的工作：
1、明确问题的求解目标。
2、分析问题所包含的约束条件。
3、建立优化函数。优化函数通常可以通过综合分析问题的求解目标及约束条件归纳出来。
4、制定贪婪准则。
五、进度安排
1、第一周:分析题目的需求，设计抽象数据类型、构思算法、通过类的设计实现抽象数据类型并编写上机程序
2、第二周完成程序开发，进行测试并分析结果，最后撰写课程设计报告
I
利用贪婪法解决实际问题
六、完成后应上交的材料
上交的成果的内容必须由以下四个部分组成，缺一不可。
1．上交源程序：学生按照课程设计的具体要求所开发的所有源程序（应该放到一个文件夹中）。
2．上交程序的说明文件：（保存在.txt中），在说明文档中应该写明上交程序所在的目录，上交程序的主程序文件名，如果需要安装，要有程序的安装使用说明。
3．课程设计报告电子文档：（保存在word 文档中，文件名要求按照“学号姓名算法分析课设报告.doc”起名，如文件名为“200300109张三算法分析课设报告.doc”），按照课程设计的具体要求建立的功能模块，每个模块要求按照如下几个内容认真完成：
其中包括：
（1）需求分析：
在该部分中叙述每个模块的功能要求等。
（2）概要设计
在此说明每个部分的算法设计说明（可以是描述算法的流程图），每个程序中使用的存储结构设计说明（如果指定存储结构请写出该存储结构的定义。
（3）详细设计
各个算法实现的源程序，对每个题目要有相应的源程序（可以是一组源程序，每个功能模块采用不同的函数实现）。
源程序要按照写程序的规则来编写。要结构清晰，重点函数的重点变量，重点功能部分要加上清晰的程序注释。
（4）调试分析
包括测试数据，测试输出的结果，时间复杂度分析，和每个模块设计和调试时存在问题的思考（问题是哪些？问题如何解决？），算法的改进设想。
（5）课设总结
总结可以包括：课程设计过程的收获、遇到问题、遇到问题解决问题过程的思考、程序调试能力的思考、对算法设计与分析这门课程的思考、在课程设计过程中对《算法设计与分析》课程的认识等内容。
4．课程设计报告打印稿。
七、推荐参考资料
教材：
《算法设计与分析》 Anany Levitin 著潘彦译清华大学出版社，2007。
《算法设计与分析》宋文等编重庆大学出版社，2001。
参考书：[1] 《算法设计与分析》周培德电子工业出版社，2000。
[2] 《算法设计与分析》王晓东电子工业出版社，2004
指导教师签名日期年月日
系主任审核日期年月日
II
目录
1引言 (1)
2贪婪算法的概述 (1)
2.1什么是贪婪算法 (1)
2.2贪婪算法的特性 (1)
2.3贪婪算法解决问题的步骤 (2)
2.4贪婪算法的优缺点 (2)
3贪婪算法的应用 (3)
3.1贪婪算法在资源分配问题中的应用 (3)
3.2贪婪算法在布线问题中的应用 (4)
3.3贪婪算法在0/1背包问题中的应用 (6)
3.3.1传统的贪婪算法解决方案 (6)
3.3.2改进的贪婪算法策略 (7)
4 总结与展望 (9)
参考文献 (10)
利用贪婪法实现多种实际问题
引言
为了满足人们对大数据量信息处理的渴望,为解决各种实际问题,计算机算法学得到了飞速的发展,线性规划、动态规划、贪婪策略等一系列运筹学模型纷纷运用到计算机算法学中,产生了解决各种现实问题的有效算法。虽然设计一个好的求解算法更像是一门艺术，而不像是技术，但仍然存在一些行之有效的能够用于解决许多问题的算法设计方法，可以使用这些方法来设计算法，并观察这些算法是如何工作的。一般情况下，为了获得较好的性能，必须对算法进行细致的调整。但是在某些情况下，算法经过调整之后性能仍无法达到要求，这时就必须寻求另外的方法来求解该问题。
目前常用的算法设计技术有分治法、回溯法、贪婪法、动态规划算法、分支限界法等。其中分治法、回溯法主要用于设计非数值问题的算法,而贪婪法、动态规划算法、分支限界法则主要用于设计数值最优化问题的算法。贪婪法是一种求最优解问题的最直接的设计技术，它不是对所有问题都能得到整体最优解，但对许多问题可能产生整体最优解。
2贪婪算法的概述
2.1 什么是贪婪算法
贪婪算法是一种对某些求最优解问题的更简单、更迅速的设计技术。用贪婪法设计算法的特点是一步一步地进行，常以当前情况为基础根据某个优化测度作最优选择，而不考虑各种可能的整体情况，它省去了为找最优解要穷尽所有可能而必须耗费的大量时间，它采用自顶向下,以迭代的方法做出相继的贪心选择,每做一次贪心选择就将所求问题简化为一个规模更小的子问题, 通过每一步贪心选择,可得到问题的一个最优解，虽然每一步上都要保证能获得局部最优解，但由此产生的全局解有时不一定是最优的，所以贪婪法不要回溯。
贪婪算法是一种改进了的分级处理方法。其核心是根据题意选取一种量度标准。然后将这多个输入排成这种量度标准所要求的顺序，按这种顺序一次输入一个量。如果这个输入和当前已构成在这种量度意义下的部分最佳解加在一起不能产生一个可行解，则不把此输入加到这部分解中。这种能够得到某种量度意义下最优解的分级处理方法称为贪婪算法。
对于一个给定的问题，往往可能有好几种量度标准。初看起来，这些量度标准似乎都是可取的，但实际上，用其中的大多数量度标准作贪婪处理所得到该量度意义下的最优解并不是问题的最优解，而是次优解。因此，选择能产生问题最优解的最优量度标准是使用贪婪算法的核心。
一般情况下，要选出最优量度标准并不是一件容易的事，但对某问题能选择出最优量度标准后，用贪婪算法求解则特别有效。最优解可以通过一系列局部最优的选择即贪婪选择来达到,根据当前状态做出在当前看来是最好的选择，即局部最优解选择，然后再去解做出这个选择后产生的相应的子问题。每做一次贪婪选择就将所求问题简化为一个规模更小的子问题，最终可得到问题的一个整体最优解。
2.2贪婪算法的特性
贪婪算法及贪婪算法可解决的问题通常大部分都有如下的特性:
- 1 -
利用贪婪法解决实际问题
（1）有一个以最优方式来解决的问题。为了构造问题的解决方案,有一个候选的对象的集合：比如不同面值的硬币。
（2）随着算法的进行,将积累起其它两个集合：一个包含已经被考虑过并被选出的候选对象,另一个包含已经被考虑过但被丢弃的候选对象。
（3）有一个函数来检查一个候选对象的集合是否提供了问题的解答。该函数不考虑此时的解决方法是否最优。
（4）还有一个函数检查是否一个候选对象的集合是可行的,也即是否可能往该集合上添加更多的候选对象以获得一个解。和上一个函数一样,此时不考虑解决方法的最优性。
（5）选择函数可以指出哪一个剩余的候选对象最有希望构成问题的解。
（6）最后,目标函数给出解的值。
为了解决问题,需要寻找一个构成解的候选对象集合,它可以优化目标函数,贪婪算法一步一步的进行。起初,算法选出的候选对象的集合为空。接下来的每一步中,根据选择函数,算法从剩余候选对象中选出最有希望构成解的对象。如果集合中加上该对象后不可行，那么该对象就被丢弃并不再考虑；否则就加到集合里。每一次都扩充集合，并检查该集合是否构成解。如果贪婪算法正确工作，那么找到的第一个解通常是最优的。
2.3贪婪算法解决问题的步骤
贪婪算法的一般解题步骤:
设计中一类非常重要的问题。每一个最优化问题都包含一组约束条件和一个优化函数，满足约束条件的问题求解方案称为问题的可行解，使优化函数取得最优值的可行解称为问题的最优解。贪婪算法是解决最优化问题的一种基本方法。它采用逐步构造最优解的思想，在问题求解的每一个阶段，都做出一个在一定标准下看上去最优的决策；决策一旦作出，就不可再更改。制定决策的依据称为贪婪准则。使用贪婪算法解决问题，通常需要做好以下几个方面的工作：
1、明确问题的求解目标。
2、分析问题所包含的约束条件。
3、建立优化函数。优化函数通常可以通过综合分析问题的求解目标及约束条件归纳出来。
4、制定贪婪准则。清楚问题的求解目标、所包含的约束条件及优化函数之后，就可以着手制定一个可行的贪婪准则。贪婪准则的制定是用贪婪算法解决最优化问题的关键，它关系到问题能否得到成功解决及解决质量的高低。
2.4贪婪算法的优缺点
贪婪算法是一种重要的算法设计策略,而且其效率高。贪婪算法并不从整体最优考虑,它所做出的选择只是在某种意义上的局部最优选择,即在当前看来最好的选择。希望通过每次所做的贪婪选择导致最终结果是问题的一个最优解。贪婪算法具有良好的爬坡能力，一般情况下该算法都可以较快地求出满足计算精度要求的近似最优解，当算法不能在限定的计算时间内找到满足问题要求的近似最优解时，给出一个可行解及计算误差，作为决策参考。但是随着问题规模和复杂度的不断提升，单一的算法在其收敛性和
2
利用贪婪法实现多种实际问题
求解速度等方面已经表现出局限性。即使贪婪算法的效率很高，它也只适用于少量的实例。
假设某职工的工资为638元，要求统计并输出应发给该职工面值100元、50元、20元、10元、5元、2元、1元的人民币各多少张，使总张数最少。我们该发给他多少张人民币呢？答案可以是638张面值1元的人民币，可以是638/2=319张面值2元的人民币，……无论发给该职工人民币多少张，他拿到的人民币总和都应等于他自己的工资数。要发给该职工638元的工资，并使总张数最少，直觉告诉我们，应先给他6张面值100元的人民币；第7张不能再给100元的，也不能给50元的，否则该职工实际拿到的工资将会超过他应得的工资；显然，第7张应为面值20元的人民币。同理，第8张为面值10元的人民币，第9张为面值5元的人民币，第10张为面值2元的人民币，第11张为面值1元的人民币。该职工共拿到人民币11张，分别为面值100元的6张，面值50元的没有，面值20元、10元、5元、2元和1元的各1张。这样，不但满足了约束条件即100×6+（20+10+5+2+1）×1＝638，而且使该职工拿到的人民币张数最少。把以上操作方法归纳出来就是一种可行的贪婪准则：按面值从大到小的顺序分发人民币，并始终保证职工实际拿到的工资不超过他应得的工资。
当贪婪算法面对不同的货币系统，或者缺少某种面值的货币，或者某种面值的货币数目有限等情况时，它可能只能找出一个次优解或是根本找不到解。假如给出的面值中没有2元和1元或是限定面值的张数时，贪婪算法就不能解决了。因此要具体问题具体对待，可以将贪婪算法与其他算法结合起来应用，多种算法相结合使用的混合优化策略已经逐渐成为新的研究热点。
3贪婪算法的应用
贪婪算法的基本思路：从问题的某一个初始解出发逐步逼近给定的目标,以尽可能快地求得更好的解。当达到某算法中的某一步不能再继续前进时,算法停止。
该算法存在的问题：1) 不能保证求得的最后解是最佳的;2) 不能用来求最大或最小解问题;3) 只能求满足某些约束条件的可行解的范围。
3.1贪婪算法在资源分配问题中的应用
下面介绍争用2个甚至多个资源时的安排：
现有m个资源，如m个多媒体教室。有n个课程的集合E={1,2,……,n}，其中每个课程都要求使用一个资源，而在同一时间内只允许一个课程使用一个资源。每个课程使用某一资源时，为提高利用率，按照资源大小的非递减顺序安排(如果资源大小一样，可省去这个排序工作)。每个课程i都有一个要求使用资源的起始时间si和一个结束时间fi，且si
设A是所要求安排的课程的m个最大相容课程子集，即用A[i][j]存储对最小教室所选择的课程，A[i][m]存储对最大教室所选择的课程。若课程i在集合A[i][x]中(x=1,2,……,m)，则A[i][x]必为true(存入其课程序号)。变量J(x)用以记录最近一
- 3 -
利用贪婪法解决实际问题
次加入到A[i][x]中的课程。已知的各课程的起始时间和结束时存储于数组s和f中，且按结束时间的非减序：f1<=f2<=……<=fn排列。如果未排序，则先按此用O(nlogn)时间排序。其贪婪策略是：先向A[i][1]中安排，安排不下时，安排在A[i][2]中，??直到安排在A[i][m]，仍安排不下，只能另做处理。参考程序如下：
Procedure GREEDY-COURSE-SELECTOR1(E,s,f,A)
begin
n←length(E);A←d;
A[1][1]←1; //A中有m个集合，分别用以存放课
/ /程安排
For x←0 to m-1 do
J[x]←x; //用以存放最近一次加入到A[J][x]
/ /中的课程序号.
For i←2 to n do
If s[i]>=f[J[1]] then
Begin
A[i][1]←I;
J[1]←i
End
Else
For k←0 to m-1 do
If s[i]>=f[J[k]] then
Begin
A[i][k]←I;
J[k]←i
End;
End;
按照上述贪婪策略，将m个资源按照利用率非递减排序，在年n个课程按结束时间非递减排序后，运用贪婪算法依次把相容课程加入到m个相容课程集合中，使该问题在相容课程安排最多时利用率也最大。在n个课程和m个资源事先排队的情况下，用贪婪策略解此问题可以获得最佳解。其计算复杂度至多是O(m*n)，在众多的算法中执行时间最短。
3.2贪婪算法在布线问题中的应用
假定要将一组电子元件安装在线路板上，给定一个连线矩阵CON和一个位置距离矩阵DIST，其中CON(i,j)等于元件i和元件j间的连线数目,DIST(r,s)是此线路板中位置r和位置s间的距离.将这n个元件各自放在线路板的某位置上就构成一种方案, 布线成本是CON(i,j)×DIST(r,s)乘积之和,其中元件i放在位置r,元件j放在位置s。设计一种布线方案,找出其布线成本是最小值。
电路板布线问题分析
电路板上n个位置分别标记为p1,p2,p3,…,pn,这n个位置构成一个无向图,n个顶点,n(n-1)/2条边,任意两个位置之间的距离由矩阵DIST给出。记这个图为G=(V,E)。同样,对n个元件也标上记号,为e1,e2,e3,…,en,这n个元件的一个全排列就对应于一种布线方案,显然,每一个排列也构成一个无向图,n个顶点对应于n个元件,而任意两个顶点之间是否有线连接由CON给出,即CON(r,s)>0,则表示顶点(元件)er,es之间有边相连；否则,CON(r,s)=0时,顶点(元件)er,es, 之间无边相连。这样,也构成一个无向图G’=(V’,E’)。
4
利用贪婪法实现多种实际问题
不考虑顶点,边所代表的具体含义,显然,V=V’,E=E’,而且对于每一条边e∈E,都有e∩V’≠ф。所以，可以将V’看成是G的一个顶点覆盖。所以,电路板布线问题可以看成一个带权值的顶点覆盖问题
针对本文中的电路板布线问题，考虑“贪婪算法＋回溯法”作为求解问题的近似算法。考虑电路板布线问题的代价函数定义，直观的感觉应该是将连线多的元件尽量放在距离短的两个位置上，按照这样的方法，每放一次元件，能够使得布线代价增加得小一些。所以，贪婪策略定义为：按照连线数与位置距离比值递减的次序安装元件。按照这种策略，可以得到一种布线方式。同时，考虑到每一个元件位置对，将两个元件安装在两个位置上有两种不同情况，这样采用回溯法遍历每一对元件位置对的不同安装方式，从中找出相对最优的布线方式。采用这种近似算法最大的优点是效率高，速度快，在短时间内找到一定精度的解。算法描述：
(1) 输入连线矩阵CON和位置距离矩阵DIST
(2) 贪婪算法,找出一种布线方式
(3) 回溯法,对(2)中找到的布线方式,所有的可能交换的
元件位置对进行回溯搜索,得到一种相对较优布线方式及其布线总代价
(4) 输出结果
本文中采用的贪婪策略为:按照连线数与位置距离比值递减的次序安装元件.在使用这种贪婪策略情况下,需要考虑以下几个问题:
(1) 在当前连线矩阵tmpCON中选中最大连线数,确定的关联的两个元件e1,e2不能都出现在链表dis-con中.出现这种情况应该舍弃,并修改tmpDIST使得不会再次出现e1,e2 被同时选中的情况。
(2) 当确定的两个相关联的元件e1,e2中,假设有一个元件e2已经出现在链表dis-con 中,应该从e2对应的位置p2在当前位置矩阵tmpDIST进行搜索,而且确定的另一个位置P1,没有出现在dis-con。
(3) 当确定的两个相关联的元件e1,e2都没有出现在dis-con中,应该使在当前位置矩阵tmpDIST确定的两个位置p1,p2都没有出现在dis-con中。
(4) 当在当前tmpDIST中确定位置P1,P2失败时,应该丢弃当前选定的元件e1,e2,并且修改在tmpCON e1,e2对应的值。
鉴于以上的情况,设计的基于“贪婪算法”的算法如下：
(1) 定义两个矩阵tmpDIST和tmpCON,并用CON和DIST初始化这两个矩阵；
(2) 在矩阵tmpCON选择最大连线数"确定关联的两个元件e1,e2；
(3) 判断两个元件e1,e2是否已经在dis-con中,返回元件e1,e2在dis-con中的个数num.如果num=2,即e1,e2两个元件均在dis-con元件位中,修改矩阵tmpCON中元件e1,e2对应的位置,赋值为-1,使之不能再次被选中,转向(2;)否则,转向(4)；
(4) 如果num=0,即选出的e1,e2两个元件均不在dis-con元件位中,在矩阵tmpDIST 中选出两个位置p1,p2,使p1,p2不在dis-con位置位中;如果num=1,即选出的e1,e2两个元件有一个已经在dis-con元件位中,假设为e2,从e2对应的位置P2进行搜索,选出另一个位置p1,并且保证p1没有出现在dis-con中.如果能够选出p1,p2,转向(5)否则,修改矩阵
- 5 -
利用贪婪法解决实际问题
tmpCON中元件e1,e2对应的位置,赋值为-1并转向(2)；
(5) 将e1,e2,p1,p2分别对应选入dis-con的元件位和位置位中,若num=0,标记这一个元件位置对在dis-con中对应的标志位为0；若num=1,标记这一个元件位置对在dis-con 中对应的标志位为01或10,“1”表示对应的元件和位置不是第一次选入dis-con中.修改矩阵tmpCON中元件e1,e2对应的元素,赋值为-1,修改矩阵tmpDIST中p1,p2对应的元素,赋值为∞；
(6) 判断元件是否已经全部选出。若全部选出,则保存结果,一种布线方式结束贪婪算法，否则转向(2)。
在本文中,采用一个一维数组Ex[m]来模拟对一个深度为m的二叉树进行回溯搜索。定义运算：当Ex[i]+1=2时,令Ex[i]=0,Ex[i+1]=Ex[i+1]+1,这样,对Ex[i]加1,就完成了从二叉树的第i层向第i+1层的回溯。对Ex[i]进行加1操作,直至Ex[i]=1,i=1,2,…,n,以此来模拟二叉树的回溯。“回溯法”的具体算法：
(1) 统计dis_con中元件位置对对应的标志位为00的个数m,在贪婪算法所得到的布线方案中有m对元件位置对可以互换。算法需对一个深度为m的二叉树的叶节点进行搜索,共需要搜索2m次。初始化布线代价和最小值min,及其对应的布线方案x[1:n]
(2) 对于一个叶节点计算其布线代价和sum若sum (3) 判断是否搜索完毕。若搜索完毕,转向(4)否则转向(2) (4) 输出布线代价和最小值min,及其对应的布线方案x[1:n] 根据上面的推导，总的算法复杂度可以表示为：n×T1+2p1n×T2。可以看出,该算法复杂度与贪婪算法循环次数n，一次选择得到有效元件位置对的概率P1有关。对于n 和P1很难有一个精确的估计,所以采用了程序仿真,以得到估计值。 对于电路板布线问题的复杂度,我们给出一般性的结论：当N<400时,采用“贪婪算法+回溯法”的近似算法可以很快地得到问题的一组次优解；而当N很大时,为了尽快地找到问题的次优解,可以不采用“回溯法”,问题的复杂度仅是O(N3),当然会牺牲精度。 3.3 贪婪算法在0/1背包问题中的应用 0/1 背包问题是一个经典的NP完全问题，在现实生活中具有广泛的应用，如物流公司的货物发配问题，集装箱的装运问题等。解决0/1 背包问题的方法可以分为最优算法和启发式算法，最优算法包括穷举法、动态规划算法、递归算法等，可以找到最优解但只适用于小规模问题；启发式算法包括贪婪算法、遗传算法等，一般用于求解较大规模问题，遗传算法根据种群的适应值使种群朝着更优的方向进化，经过一定次数的迭代可以得到近似最优解，但是适应值只能反映种群之间的优劣关系，无法判断最终结果与全局最优解的相似程度，这影响了所求结果的可信性．贪婪算法具有良好的爬坡能力，但是只能搜索一个局部最优解，对于0/1背包问题,很难找到其具有多项式时间的算法。本文通过对贪婪算法的优化,试图找到0 / 1 背包问题的最优解的很好近似。 3.3.1 传统的贪婪算法解决方案 0/ 1 背包问题：给定n 种物品和一个背包。物品i 的重量是wi ,其价值为vi ,背包的容量为 c 。问应如何选择装入背包中的物品,使得装入背包中物品的总价值最大? 该问题中对于每种物品i 只有两种选择,即装入背包或不装入背包。不能将物品i 装入背 6 利用贪婪法实现多种实际问题 包多次,也不能只装入部分的物品i 。此问题的形式化描述为:给定c > 0 ,wi > 0 ,vi> 0 ,1 ≤i ≤n ,要求找出一个n 元0 - 1 向量(x1 ,x2 ,?,xn) ,xi ∈{ 0 ,1} ,1 ≤i ≤n ,使得∑Wixi ≤c , 而且∑vixi 达到最大。用贪婪算法来设计求解0 / 1 背包问题,首先要选出最优的量度标准。可选择的贪婪策略有三种,每个贪婪策略都采用多步过程来完成背包的装入。在每一步过程中利用贪婪策略选择一个物品装入背包。 一种贪婪策略是将目标函数作为量度标准,即每装入一件物品,使背包获得最大可能的价值。其具体步骤是:从剩余的物品中,选出可以装入背包的价值最大的物品。利用这种规则,价值最大的物品首先被装入(假设有足够容量) ,然后是下一个价值最大的物品,如此继续下去。考虑n = 3 , w =[20 ,5 ,4 ] , v = [ 25 ,15 ,15 ] , c = 20。当利用价值贪婪策略时,获得的解为x = (1 , 0 , 0 ) ,这种方案的总价值为25 。而最优解为( 0 , 1 , 1 ) ,其总价值为30 。可见,这种策略不能保证得到最优解。其原因在于,虽然每一步获得了效益值最大的增加,但背包可用容量消耗过快。由此可知,按物品价值的非增次序装包不能得到最优解。由此,用重量作为量度,采用重量贪婪策略,让背包重量尽可能慢地被消耗。这就要求按物品重量的非降次序来把物品放入背包,即从剩下的物品中选择可装入背包的重量最小的物品。虽然这种规则对于前面的例子能产生最优解,但在一般情况下则不一定能得到最优解。考虑n = 2 ,w = [10 ,20 ] , v = [5 ,100 ] , c = 25。当利用重量贪婪策略时,获得的解为x = (1 ,0 ) , 比最优解( 0 ,1) 要差。这是因为重量虽然慢慢地被消耗,但价值没能迅速地增加。为此,采用在价值的增长速率和重量的消耗速率之间取得平衡的量度标准———单位价值贪婪策略。这种选择策略为:从剩余物品中选择可装入包的vi/ wi值最大的物品,这种策略也不能保证得到最优解。利用此策略解n = 3 ,w = [ 20 ,15 ,15 ] , v = [40 ,25 ,25 ] , c = 30 时,获得的解为x = (1 ,0 ,0 ) ,而最优解为x =( 0 ,1 ,1 ) 。 通过上述分析看到,运用这三种策略,都不一定能得到0/ 1 背包问题的最优解,这是因为它无法保证最终能将背包装满,部分背包空间的闲置使每个单位空间所具有的价值降低了。然而,在随机产生的背包问题中,第三种策略获得最优解的几率明显大于前两种。 传统贪心算法解决0/ 1 背包问题的具体算法 void CCompute : :Greedy01KnapsackQ { / / value 为所取物品的总价值,weight 为所取物品的总重量 if ( getRestrictNo () > 1 ) return ;/ / 若约束个数大于1 , 则不能使用贪婪法 long N = getSize() ; / / 获取背包个数 float value = 0 , weight = 0 ; for (int i = start ;i < N;i ++ ) { if ( weight + m fRestrict [0 ] [ i ] > m fRestrict [ 0 ] [N]) continue ; value + = m fDestination[ i ] ; / / 目标函数 weight + = m fRestrict [0 ] [ i ] ; / / 约束函数 } setResult (value) ; } 该算法的主要计算时间在于将各种物品依其单位重量的价值从大到小排序。因此算法的计算时间上界为O (nlogn) 。 3.3.2 改进的贪婪算法策略 - 7 - 利用贪婪法解决实际问题 k 阶优化方法(k - optimal) 0 / 1 背包问题是一个NP复杂问题。对于这类问题,也许根本就不可能找到具有多项式时间的算法。虽然按vi/ wi 非递增的次序装入物品不能保证得到最优解,但它是一个直觉上近似的解。希望它是一个好的启发式算法,且大多数时候能很好地接近最后算法。是否存在一个x(x < 100) ,使得采用单位价值贪婪策略求解最优解的结果与最优值相差在x %以内。经过验证,这种情况是不可能的。例如,对于n = 2 , w = [1 ,y] , v = [10 ,9y] , c = y。贪心算法结果为x = (1 ,0 ) , 最终的价值为10 。而当y ≥10/9 时,最优解的值为9y。因此,贪婪算法的计算结果与最优解的差与最优解之间的比例为( (9y - 10) / 9y 3 100 ) %。当y 值较大时,这个值趋近于100 %。但是,我们可以利用贪心算法来提供解,使解的结果与最优解的值之差在最优值的x % (x <100) 之内。首先将最多k 件物品放入背包,如果这k 件物品重量大于c ,则放弃它。否则,剩余的重量用来考虑将剩余物品按vi/ wi 递减的顺序装入。通过考虑由启发法产生的解法中最多为k 件物品的所有可能的子集来得到最优解。 考虑n = 4 , w = [1 ,2 ,5 ,6 ] , p = [3 ,5 ,10 ,11 ] ,c = 7。当k = 0 时,背包按物品单位价值非递增顺序装入。首先将物品1 放入背包,然后是物品2 ,背包剩下的容量为4 个单元,剩下的物品没有一个合适的,因此解为x = ( 1 , 1 , 0 , 0 ) 。此解获得的价值为8。 现在考虑k = 1 时的贪婪启发法。最初的子集为{ 1 } , { 2 } , { 3 } , { 4 } 。子集{ 1 } , { 2}产生与k = 0 时相同的结果,考虑子集{ 3 } ,置x3为1。此时还剩2 个单位的容量,按单位价值非递增顺序来考虑如何利用这5 个单位的容量。首先考虑物品1 ,它适合,因此取x1 为1 ,这时仅剩下1个单位容量了,且剩余物品没有能够加入背包中的物品。通过子集{ 3 }开始求解得结果为x = (1 ,0,1 ,0 ) ,获得的价值为13 。若从子集{ 4 }开始,产生的解为x = ( 1 , 0 ,0 ,1 ) ,获得的价值为14 。考虑子集大小为0 和1 时获得的最优解为( 1 , 0 ,0 ,1 ) 。这个解是通过k = 1 的贪心启发式算法得到。 若k = 2 ,除了考虑k < 2 的子集,还必需考虑子集{ 1 , 2 } , { 1 , 3 } , { 1 , 4 } , { 2 , 3 } , {2 , 4 }和{ 3 , 4 } 。首先从最后一个子集开始,它是不可行的,故将其抛弃。子集{ 2 , 4 }的重量也超过了背包的允许值,舍弃。剩下的子集经求解分别得到如下结果: ( 1 , 1 , 0 , 0 ) , ( 1 , 0 , 1 , 0) , ( 1 , 0 , 0 , 1 ) 和( 0 , 1 , 1 , 0 ) ,这些结果中最后一个价值为15 ,它的值比k = 0 和k = 1 时获得的解要高,这个答案即为启发式方法产生的结果。这种修改后的贪婪启发方法称为k 阶优化方法(k - optimal) 。也就是,若从答案中取出k 件物品,并放入另外k 件,获得的结果不会比原来的好,而且用这种方式获得的值在最优值的(100/ ( k +1) ) %以内。当k = 1 时,保证最终结果在最优解的5 0 %以内;当k = 2 时,则在33. 33 %以内等等,这种启发式方法的执行时间随k 的增大而增加,需要测试的子集数目为O(nk ) ,每一个子集所需时间为O(n) ,因此当k > 0 时,总的时间开销为O(nk + 1 ) 。而实际测试的性能要更好些。改进的贪婪算法解决0/ 1 背包问题的具体算法描述: void CCompute : : ImprovedGreedy01Knapsack() { if ( getRestrictNo () > 1 ) return ; / / 若约束个数大于1 ,则不能使用贪婪法 long N = getSize() ; / / 获取背包个数 for (int start = 0 ;start < N;start ++ ) { float value = 0 , weight = 0 ; For (int i = start ;i < N;i ++ ) { if ( weight + m fRestrict [0 ] [ i ] > m (Restrict [0 ] [N]) continue ; value + = m fDestination [ i ] ; / / 目标函数 8 利用贪婪法实现多种实际问题 weight + = m fRestrict [0 ] [ i ] ; / / 约束函数 } if ( value > getResultQ) / / 获取当前已有的最大价值 { setResult (value) ; / / 设置当前最大价值 } } setResult (value) ; } 0/ 1 背包问题是一个NP - 复杂问题,尽管已进行了多年的研究,目前还没有一个NP 完全问题有多项式时间算法。利用优化的贪心算法求解0/1 背包问题,虽然不能保证一定得到最优解,但是我们能够在O(nk + 1 ) 的时间复杂度内,获得0/ 1背包问题最优解的很好近似。这也是解决NP 类问题的一个可接受的很好的解决方案。 4 总结 贪婪算法解决优化问题, 在复杂的多目标规划问题, 工农业生产中的配管、配线问题, 以及机器学习, 图象识别等问题中都有应用,并且是比较有效的方法之一,虽然贪婪算法在许多优化问题中都有成功的应用, 但其本身也存在许多不足。例如只进行局部的优化 ,只着眼于眼前的问题考虑,将来的发生的情况不考虑。对于一些复杂的问题不能很好的解决。从而导致算法的收敛性能差, 需要很长时间才能找到最优解, 这些阻碍了贪婪算法的推广应用。如何改善贪婪算法使其更好地应用于实际问题的解决中, 是诸多学者探索的一个主要课题。 贪婪算法在应用方面的丰硕成果, 使人们对它的发展前景充满信心。其主要应用领域在于机器人学(移动机器人路径规划, 关节机器人运动轨迹规划, 细胞机器人的结构优化等) , 控制(瓦斯管道控制, 布线控制等) , 规划(生产规划, 并行机任务分配等) ,设计(通信网络设计等) , 组合优化(背包问题, 图分划问题等) , 图象处理,信号处理等方面.它的应用将涉及更多的方面。 贪婪算法可将一个问题的解决方案视为一系列决策的结果。在贪婪算法中,每用一次贪婪准则便做出一个不可撤回的决策,个最优子序列。当一个问题具有最优子结构时,我们会想到存在着更简单、有效的方法,只要我们总是做出当前看来最好的选择就可以了。贪婪算法所作的选择可以依赖于以往所作过的选择,但决不依赖于将来的选择,也不依赖于子问题的解,这使得算法在编码和执行的过程中都有着一定的速度优势。如果一个问题可以同时用几种方法解决,贪婪算法应该是最好的选择之一。但是贪婪算法并不是对所有的问题都能得到整体最优解或最理想的近似解,与回溯法等比较,它的适用区域相对狭窄许多,因此正确地判断它的应用时机十分重要，贪婪算法的优点结合其他算法的应用将是以后研究的方向。 - 9 - 利用贪婪法解决实际问题 参考文献 [1] 王晓东,计算机算法设计与分析[M] . 电子工业出版社.2001 [2] 余祥宣,崔国化,邹海明,计算机算法基础[M] . 华中科技大学出版社. 1998 [3] 刘洋．解0-1 背包的遗传算法及其改进[J]．天津师范大学学报(自然科学版)，2003，． [4] 邓宏涛,朱峋. 0/1 背包问题的贪心优化解法. 计算机与数字工程, 2006 [5] 徐宗本,张讲社,郑亚林. 计算智能中的仿生学:理论与算法. 北京:科学出版社,2003 [6] 苏德富、钟诚.计算机算法设计与分析.北京：电子工业出版社，2001 [7] 宋文，吴晟，杜亚军.算法设计与分析.重庆：重庆大学出版社，2001 [8] 谭浩强C程序设计（第二版）.北京：清华大学出版社，1999.12. [9] 周向臣，柯熙政．无线电接入网的体系结构研究．光通信技术，2005,6. [10]刘玉娟,王相海.0/1背包问题的两种扩展形式及其解法[J],计算机应用研究,2006,1. [11]王乐,王世卿,张静乐.基于Matlab的0/1背包问题的动态规划求解[J],计算机技术与发 展,2006,4. [12]钱能.c++程序设计教程[M],北京:清华大学出版社 [13]王晓东.算法分析与设计[M],北京:清华大学出版社 10 贪心算法经典例题 发布日期：2009-1-8 浏览次数：1180 本资料需要注册并登录后才能下载！ ·用户名密码验证码找回密码·您还未注册？请注册 您的账户余额为元，余额已不足，请充值。 您的账户余额为元。此购买将从您的账户中扣除费用0.0元。 内容介绍>> 贪心算法经典例题 在求最优解问题的过程中，依据某种贪心标准，从问题的初始状态出发，直接去求每一步的最优解，通过若干次的贪心选择，最终得出整个问题的最优解，这种求解方法就是贪心算法。 从贪心算法的定义可以看出，贪心法并不是从整体上考虑问题，它所做出的选择只是在某种意义上的局部最优解，而由问题自身的特性决定了该题运用贪心算法可以得到最优解。 我们看看下面的例子 例1 均分纸牌（NOIP2002tg） [问题描述] 有 N 堆纸牌，编号分别为 1，2，…, N。每堆上有若干张，但纸牌总数必为 N 的倍数。可以在任一堆上取若干张纸牌，然后移动。移牌规则为：在编号为 1 堆上取的纸牌，只能移到编号为 2 的堆上；在编号为 N 的堆上取的纸牌，只能移到编号为 N-1 的堆上；其他堆上取的纸牌，可以移到相邻左边或右边的堆上。现在要求找出一种移动方法，用最少的移动次数使每堆上纸牌数都一样多。例如 N=4，4 堆纸牌数分别为： ①9 ②8 ③17 ④ 6 移动3次可达到目的： 从③取 4 张牌放到④（9 8 13 10） -> 从③取 3 张牌放到②（9 11 10 10）-> 从②取 1 张牌放到①（10 10 10 10）。 [输入]：键盘输入文件名。 文件格式：N（N 堆纸牌，1 <= N <= 100） A1 A2 … An （N 堆纸牌，每堆纸牌初始数，l<= Ai <=10000） [输出]：输出至屏幕。格式为：所有堆均达到相等时的最少移动次数。 [输入输出样例] a.in： 4 9 8 17 6 屏慕显示：3 算法分析：设a[i]为第i堆纸牌的张数（0<=i<=n），v为均分后每堆纸牌的张数，s为最小移到次数。 我们用贪心法，按照从左到右的顺序移动纸牌。如第i堆(0 贪心算法的应用 课程名称：算法设计与分析 院系：计算机科学与信息工程学院 学生姓名：**** 学号：********** 专业班级：********************************** 指导教师：****** 201312-27 贪心算法的应用 摘要：顾名思义，贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。当然，希望贪心算法得到的最终结果也是整体最优的。虽然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。如单源最短路经问题，最小生成树问题等。在一些情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的很好近似。贪心算法求问题一般具有两个重要性质：贪心选择性质和最优子结构性质。所谓贪心选择性是指所求问题的整体最优解可以通过一系列局部最优解的选择，即贪心选择达到。这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法主要区别。当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。 背包问题是一个经典的问题，我们可以采用多种算法去求解0/1背包问题，比如动态规划法、分支限界法、贪心算法、回溯法。在这里我们采用贪心法解决这个问题。 关键词：贪心法背包问题最优化 目录 第1章绪论 (3) 1.1 贪心算法的背景知识 (3) 1.2 贪心算法的前景意义 (3) 第2章贪心算法的理论知识 (4) 2.1 问题的模式 (4) 2.2 贪心算法的一般性描述 (4) 第3章背包问题 (5) 3.1 问题描述 (5) 3.2 问题分析 (5) 3.3算法设计 (5) 3.4 测试结果与分析 (10) 第4章结论 (12) 参考文献 (13) 附件 (13) 利用贪婪法实现多种实际问题 《算法设计与分析》课程设计任务书 学院名称：数学与计算机学院专业：信息与计算科学专业年级：2007 一、设计题目 题目十四：利用贪婪算法实现多种实际问题 二、主要内容 给出多种可以用贪婪算法解决的典型问题，并分析、证明、编程。 三、具体要求 （1）贪婪算法的基本思想； （2）给出背包问题的贪婪算法； （3）给出有限期计算机作业调度的贪婪算法； （4）给出上面两个算法的证明； （5）给出上面两个算法的程序。 （6）给出时间复杂度。 四、主要技术路线提示 在用贪婪算法解决资源分配问题、布线问题、0-1背包问题过程中，使用贪婪算法解决问题，通常需要做好以下几个方面的工作： 1、明确问题的求解目标。 2、分析问题所包含的约束条件。 3、建立优化函数。优化函数通常可以通过综合分析问题的求解目标及约束条件归纳出来。 4、制定贪婪准则。 五、进度安排 1、第一周:分析题目的需求，设计抽象数据类型、构思算法、通过类的设计实现抽象数据类型并编写上机程序 2、第二周完成程序开发，进行测试并分析结果，最后撰写课程设计报告 I 利用贪婪法解决实际问题 六、完成后应上交的材料 上交的成果的内容必须由以下四个部分组成，缺一不可。 1．上交源程序：学生按照课程设计的具体要求所开发的所有源程序（应该放到一个文件夹中）。 2．上交程序的说明文件：（保存在.txt中），在说明文档中应该写明上交程序所在的目录，上交程序的主程序文件名，如果需要安装，要有程序的安装使用说明。 3．课程设计报告电子文档：（保存在word 文档中，文件名要求按照“学号姓名算法分析课设报告.doc”起名，如文件名为“200300109张三算法分析课设报告.doc”），按照课程设计的具体要求建立的功能模块，每个模块要求按照如下几个内容认真完成： 其中包括： （1）需求分析： 在该部分中叙述每个模块的功能要求等。 （2）概要设计 在此说明每个部分的算法设计说明（可以是描述算法的流程图），每个程序中使用的存储结构设计说明（如果指定存储结构请写出该存储结构的定义。 （3）详细设计 各个算法实现的源程序，对每个题目要有相应的源程序（可以是一组源程序，每个功能模块采用不同的函数实现）。 源程序要按照写程序的规则来编写。要结构清晰，重点函数的重点变量，重点功能部分要加上清晰的程序注释。 （4）调试分析 包括测试数据，测试输出的结果，时间复杂度分析，和每个模块设计和调试时存在问题的思考（问题是哪些？问题如何解决？），算法的改进设想。 （5）课设总结 总结可以包括：课程设计过程的收获、遇到问题、遇到问题解决问题过程的思考、程序调试能力的思考、对算法设计与分析这门课程的思考、在课程设计过程中对《算法设计与分析》课程的认识等内容。 4．课程设计报告打印稿。 七、推荐参考资料 教材： 《算法设计与分析》 Anany Levitin 著潘彦译清华大学出版社，2007。 《算法设计与分析》宋文等编重庆大学出版社，2001。 参考书：[1] 《算法设计与分析》周培德电子工业出版社，2000。 [2] 《算法设计与分析》王晓东电子工业出版社，2004 指导教师签名日期年月日 系主任审核日期年月日 II 贪心算法详解 贪心算法思想： 顾名思义，贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。当然，希望贪心算法得到的最终结果也是整体最优的。虽然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。如单源最短路经问题，最小生成树问题等。在一些情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的很好近似。 贪心算法的基本要素： 1.贪心选择性质。所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。 动态规划算法通常以自底向上的方式解各子问题，而贪心算法则通常以自顶向下的方式进行，以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题。 对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所作的贪心选择最终导致问题的整体最优解。 2. 当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。问题的 最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。 贪心算法的基本思路： 从问题的某一个初始解出发逐步逼近给定的目标，以尽可能快的地求得更好的解。当达到算法中的某一步不能再继续前进时，算法停止。 该算法存在问题： 1. 不能保证求得的最后解是最佳的； 2. 不能用来求最大或最小解问题； 3. 只能求满足某些约束条件的可行解的范围。 实现该算法的过程： 从问题的某一初始解出发； while 能朝给定总目标前进一步do 求出可行解的一个解元素； 由所有解元素组合成问题的一个可行解； 用背包问题来介绍贪心算法： 背包问题：有一个背包，背包容量是M=150。有7个物品，物品可以分割成任意大小。要 求尽可能让装入背包中的物品总价值最大，但不能超过总容量。 贪婪算法在排课问题中分析与应用 摘要：排课问题是教学管理中重要的问题，对教学质量起到十分重要的影响。随着计算机和信息技术的快速发展，通过合理的算法编制排课系统是十分合适的。本文通过排课问题算法的分析，选择贪婪算法来解决排课问题。通过实验表明，目前的算法能够很好的解决排课问题，对问题的解决的复杂度大大降低，使得排课变得十分简单和高效。 关键字：排课，贪婪算法，优先级 1、绪论 在高校日常管理中，教学计划是重要的组成部分。而教学计划的重要体现方式之一就是排课表，其在教学管理中的地位和作用不可低估，课表的管理对教学管理是起到基础和重要的作用。因此排课问题是教学管理中重要的问题，对教学质量起到十分重要的影响。 由于上课约束条件多，课表的编制十分复杂，是一个耗时耗力的工作。目前随着高校人数的越来越多，其很难用手工去编制课表，其工作时间长，工作量大和繁琐的编制过程是一般人很难驾驭的。随着计算机和信息技术的快速发展，通过合理的算法编制排课系统是十分合适的。通过计算机算法的求解来对问题进行抽象和解决。 2、排课算法算法简介 目前对于排课问题的算法较多，主要有蚁群算法、模拟退火算法、遗传算法、整数规划法和贪婪算法等。 （1）蚁群算法 蚁群算法就是将模拟蚂蚁的活动，对参数设置较少。这种算法具备较强的全局搜索能力，但其效率较低，且容易出现停滞[1]。 （2）模拟退火算法 这个算法被较多的学者用来解决排课问题，它是模拟退火的现象，对自然事物进行抽象而来。其比较适合约束条件较少的问题。如果约束条件少，其很快就能获得最优解。但这种算法的参数选择较难，且资源开销大[2]。 （3）遗传算法 遗传算法是基于自然选择和生物遗传的全局优化策略。其优点在于在非线性问题上能够表现出全局最优，可以并行处理而且算法效率相对较高[3]。 但遗传算法本身较为复杂，由于排课问题的约束条件较多，其算法的效率较低，如果排课要求十分严格的话，很有可能造成找不到解。 （4）整数规划法 整数规划法来解决排课问题计算量很大，只适合规模较小排课问题，对于规模较大的，至今都很难找到一个可行算法。 （5）贪婪算法 贪婪算法是指在解决问题的时候，不会考虑整体最优，而是采取局部最优的思想进行最优思想[4]。也就是说，该算法将解决问题分解为每一个步骤，根据其难易程度进行解决，通过满足局部最优的方式来尽可能的获得最满意的解决。虽然在某些情况下，贪婪算法并不能得到最优解，但能得到相对满意的解。 3、排课问题综述 （1）排课原则 排课问题的本质是一个优化问题，是对教师、上课课程、上课时间和上课地点等因素的优化。其目的就是将全校所开设课程在有限的时间和地点下进行合理的安排，确保教学的顺利进行，以达到最优的效果。 为了能够产出一张满意合格的排课表，在排课中要满足一些约束条件。我们将一些约束 武汉理工大学 算法设计与分析论文题目：贪心算法应用研究 姓名：吴兵 学院：信息工程 专业班级：电子133 学号： 1409721303131 任课教师：张小梅 目录 摘要 (1) 1.绪论 (2) 2贪心算法的基本知识概述 (3) 2.1 贪心算法定义 (3) 2.2 贪心算法的基本思路及实现过程 (3) 2.3贪心算法的核心 (3) 2.4贪心算法的基本要素 (4) 2.5 贪心算法的理论基础 (6) 2.6 贪心算法存在的问题 (7) 3贪心算法经典应用举例 (8) 3.1删数问题 (8) 3.2 汽车加油问题 (10) 3.3会场安排问题 (12) 4.总结 (16) 5.参考文献 (17) 摘要 在求最优解问题的过程中，依据某种贪心标准，从问题的初始状态出发，直接去求每一步的最优解，通过若干次的贪心选择，最终得出整个问题的最优解，这种求解方法就是贪心算法。从贪心算法的定义可以看出，贪心法并不是从整体上考虑问题，它所做出的选择只是在某种意义上的局部最优解，而由问题自身的特性决定了该题运用贪心算法可以得到最优解。贪心算法所作的选择可以依赖于以往所作过的选择，但决不依赖于将来的选择，也不依赖于子问题的解，因此贪心算法与其它算法相比具有一定的速度优势。如果一个问题可以同时用几种方法解决，贪心算法应该是最好的选择之一。本文讲述了贪心算法的含义、基本思路及实现过程，贪心算法的核心、基本性质、特点及其存在的问题。并通过贪心算法的特点举例列出了以往研究过的几个经典问题，对于实际应用中的问题，也希望通过贪心算法的特点来解决。 关键词：贪心算法最小生成树多处最优服务次序问题删数问题 从贪心算法的定义可以看出，贪心法并不是从整体上考虑问题，它所做出的选择只是在某种意义上的局部最优解，而由问题自身的特性决定了该题运用贪心算法可以得到最优解。 我们看看下面的例子 例1 均分纸牌（NOIP2002tg） [问题描述] 有 N 堆纸牌，编号分别为 1，2，…, N。每堆上有若干张，但纸牌总数必为 N 的倍数。可以在任一堆上取若干张纸牌，然后移动。移牌规则为：在编号为 1 堆上取的纸牌，只能移到编号为 2 的堆上；在编号为 N 的堆上取的纸牌，只能移到编号为 N-1 的堆上；其他堆上取的纸牌，可以移到相邻左边或右边的堆上。现在要求找出一种移动方法，用最少的移动次数使每堆上纸牌数都一样多。例如 N=4，4 堆纸牌数分别为： ①9 ②8 ③17 ④6 移动3次可达到目的： 从③取 4 张牌放到④（9 8 13 10） -> 从③取 3 张牌放到②（9 11 10 10）-> 从②取 1 张牌放到①（10 10 10 10）。 [输入]：键盘输入文件名。 文件格式：N（N 堆纸牌，1 <= N <= 100） A1 A2 … An （N 堆纸牌，每堆纸牌初始数，l<= Ai <=10000） [输出]：输出至屏幕。格式为：所有堆均达到相等时的最少移动次数。 [输入输出样例] ： 4 9 8 17 6 屏慕显示：3 算法分析：设a[i]为第i堆纸牌的张数（0<=i<=n），v为均分后每堆纸牌的张数，s为最小移到次数。 我们用贪心法，按照从左到右的顺序移动纸牌。如第i堆(0 答：贪婪算法（Greedy algorithm）是一种对某些求最优解问题的更简单、更迅速的设计技术。用贪婪法设计算法的特点是一步一步地进行，常以当前情况为基础根据某个优化测度作最优选择，而不考虑各种可能的整体情况，它省去了为找最优解要穷尽所有可能而必须耗费的大量时间，它采用自顶向下，以迭代的方法做出相继的贪心选择，每做一次贪心选择就将所求问题简化为一个规模更小的子问题，通过每一步贪心选择，可得到问题的一个最优解，虽然每一步上都要保证能获得局部最优解，但由此产生的全局解有时不一定是最优的，所以贪婪法不要回溯。 贪婪算法是一种改进了的分级处理方法。其核心是根据题意选取一种量度标准。然后将这多个输入排成这种量度标准所要求的顺序，按这种顺序一次输入一个量。如果这个输入和当前已构成在这种量度意义下的部分最佳解加在一起不能产生一个可行解，则不把此输入加到这部分解中。这种能够得到某种量度意义下最优解的分级处理方法称为贪婪算法。 对于一个给定的问题，往往可能有好几种量度标准。初看起来，这些量度标准似乎都是可取的，但实际上，用其中的大多数量度标准作贪婪处理所得到该量度意义下的最优解并不是问题的最优解，而是次优解。因此，选择能产生问题最优解的最优量度标准是使用贪婪算法的核心。 一般情况下，要选出最优量度标准并不是一件容易的事，但对某问题能选择出最优量度标准后，用贪婪算法求解则特别有效。最优解可以通过一系列局部最优的选择即贪婪选择来达到，根据当前状态做出在当前看来是最好的选择，即局部最优解选择，然后再去解做出这个选择后产生的相应的子问题。每做一次贪婪选择就将所求问题简化为一个规模更小的子问题，最终可得到问题的一个整体最优解。其有以下特性： ⑴ 有一个以最优方式来解决的问题。为了构造问题的解决方案，有一个候选的对象的集合：比如不同面值的硬币。 ⑵ 随着算法的进行，将积累起其它两个集合：一个包含已经被考虑过并被选出的候选对象，另一个包含已经被考虑过但被丢弃的候选对象。 ⑶ 有一个函数来检查一个候选对象的集合是否提供了问题的解答。该函数不考虑此时的解决方法是否最优。 ⑷ 还有一个函数检查是否一个候选对象的集合是可行的，也即是否可能往该集合上添加更多的候选对象以获得一个解。和上一个函数一样，此时不考虑解决方法的最优性。 ⑸ 选择函数可以指出哪一个剩余的候选对象最有希望构成问题的解。 ⑹ 最后，目标函数给出解的值。 实验报告 课程算法设计与分析实验实验名称贪心算法设计与应用第 1 页一、实验目的 理解贪心算法的基本原理，掌握贪心算法设计的基本方法及其应用； 二、实验内容 (一)Huffman编码和译码问题： 1．问题描述 给定n个字符在文件中的出现频率，利用Huffman树进行Huffman编码和译码。设计一个程序实现： 1.输入含n(n<=10)个字符的字符集S以及S中各个字符在文件中的出现频 率，建立相应的Huffman树，求出S中各个字符的Huffman编码。 2.输入一个由S中的字符组成的序列L，求L的Huffman 编码。 3. 输入一个二进制位串B，对B进行Huffman译码，输出对应的字符序列； 若不能译码，则输出无解信息。 提示：对应10 个字符的Huffman树的节点个数<211。 2．测试数据 Input n=5 字符集合S={a, b, c, d, e}, 对应的频率分别为 a: 20 b: 7 c: 10 d: 4 e: 18 字符序列L=ebcca 二进制位串B=01100111010010 Output S中各个字符的Huffman编码：（设Huffman树中左孩子的权<=右孩子的权）a: 11 b: 010 c: 00 d: 011 e: 10 L的Huffman 编码：10010000011 B对应的字符序列： dcaeeb 若输入的B=01111101001，则无解 (二) 加油问题（Problem Set 1702）： 1.问题描述 一个旅行家想驾驶汽车从城市A到城市B（设出发时油箱是空的）。给定两个 城市之间的距离dis、汽车油箱的容量c、每升汽油能行驶的距离d、沿途油站数n、油站i离出发点的距离d[i]以及该站每升汽油的价格p[i],i=1,2,…,n。设d[1]=0 贪心算法的应用实例 例2．排队问题 【题目描述】 在一个医院B 超室，有n个人要做不同身体部位的B超，已知每个人需要处理的时间为ti，（0 贪心算法浅析 摘要：本文讲述了贪心算法的基本思路及实现过程，贪心算法的特点、存在的问题以及应用。并通过贪心算法的特点举例列出了几个经典问题，通过对问题的探讨和研究，对贪心算法有了更加深入的了解。 关键词：贪心算法；最优解；最优子结构问题；删数问题；活动安排问题 贪心算法的基本思路及实现过程 1贪心的基本思想 用局部解构造全局解，即从问题的某一个初始解逐步逼近给定的目标，以尽可能快地求得更好的解。当某个算法中的某一步不能再继续前进时，算法停止。贪心算法思想的本质就是分治，或者说：分治是贪心的基础。每次都形成局部最优解，换一种方法说，就是每次都处理出一个最好的方案。 利用贪心策略解题，需要解决两个问题： （1）该题是否适合于用贪心策略求解； （2）如何选择贪心标准，以得到问题的最优/较优解。 2贪心算法的实现过程 （1）应用同一规则F，将原问题变为一个相似的、但规模更小的子问题； （2）从问题的某一初始解出发： While（能朝给定目标前进一步） 求出可行解的一个解元素； （3）由所有解元素组合成问题的一个可行解。 贪心算法的特点 贪心算法的最大特点就是快，通常是线性二次式，不需要多少额外的内存。一般二次方级的存储要浪费额外的空间，而且那些空间经常得不出正解。但是，使用贪心算法时，这些空间可以帮助算法更容易实现且更快执行。如果有正确贪心性质存在，那么一定要采用。因为它容易编写，容易调试，速度极快，并且节约空间。几乎可以说，此时它是所有算法中最好的。但是应该注意，贪心算法有两大难点： （1）如何贪心 怎样用一个小规模的解构造更大规模的解呢?总体上，这与问题本身有关。但是大部分都是有规律的。正因为贪心有如此性质，它才能比其他算法快。 具有应当采用贪心算法的问题，当“贪心序列”中的每项互异且当问题没有重叠性时，看起来总能通过贪心算法取得（近似）最优解的。或者，总有一种直觉在引导我们对一些问题采用贪心算法。其中“找零钱”这个问题就是一个例子。题中给出的硬币面值事实上具有特殊性，如果面值发生变化，可能贪心算法就不能返回最优解了。但是，值得指出的是，当一个问题具有多个最优解时，贪心算法并不能求出所有最优解。另外，我们经过实践发现，单纯的贪心算法是顺序处理问题的；而且每个结果是可以在处理完一个数据后即时输出的。 （2）贪心的正确性 要证明贪心性质的正确性，才是贪心算法的真正挑战，因为并不是每次局部最优解都会与整体最优解之间有联系，往往靠贪心算法生成的解不是最优解。这样，贪心性质的证明就成了贪心算法正确的关键。对某些问题贪心性质也许是错的，即使它在大部分数据中都是可行的，但还必须考虑到所有可能出现的特殊情况，并证明该贪心性质在这些特殊情况中仍然正确。而这样容易陷入证明不正确贪心性质的泥塘中无法自拔，因为贪心算法的适用范围并不大，而且有一部分极难证明，若是没有把握，最好不要冒险，还有其他算法会比它要保险。 贪心算法存在的问题 （1）不能保证求得的最后解是最佳的。由于贪心策略总是采用从局部看来是最优的选择，因此并不从整体上加以考虑； （2）贪心算法只能用来求某些最大或最小解的问题； （3）贪心算法只能确定某些问题的可行性范围 贪心算法的应用 1哈夫曼编码 2 0-1背包问题 3磁盘文件的存储 4生产调度问题 5信息查询 贪婪算法思想及其应用 摘要：贪婪算法也称作贪心算法，它没有固定的算法框架，算法设计的关键是贪婪策略的选择，并且所选的贪婪策略要具有无后向性。 关键词：贪婪策略，无后向性，最优 正文： 一．贪婪算法的定义： 贪婪算法又叫登山法，它的根本思想是逐步到达山顶，即逐步获得最优解，是解决最优化问题时的一种简单但适用范围有限的策略。 二．贪婪算法思想： 贪婪算法采用逐步构造最优解的方法，即在每个阶段，都选择一个看上去最优的策略（在一定的标准下）。策略一旦选择就不可再更改，贪婪决策的依据称为贪婪准则，也就是从问题的某一个初始解出发并逐步逼近给定的目标，以尽可能快的要求得到更好的解。而且它在设计时没有固定的框架，关键在于贪婪策略的选择。但要注意的是选择的贪婪策略要具有无后向性，即某阶段状态一旦确定下来后，不受这个状态以后的决策的影响，也就是说某状态以后的过程不会影响以前的状态，只与当前状态有关。 三．贪婪算法的优缺点： 贪婪算法的优点在于在求解问题的每一步它都是选择最优解，这样算法就容易实现也易于理解，同时也提高了效率并节省了时间。然而贪婪算法的缺点也是不容忽视的，由于它采取逐步获得最优解的方法而不从整体最优上加以考虑，它所做出的仅是在某种意义上的局部最优解。因此贪婪算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题它都能得出整体最优解或者是整体最优解的近似解。 四. 实例参考： 下面就列举用贪婪算法成功得出问题最优解的例子： 例：一个小孩拿着一美元去商店买糖果，花了33美分，售货员需要找回67美分给小孩，而美分的面值有25,10,5,1这几种。问题是售货员找个小孩的钱币的个数应是最少的，但同时要满足67美分这个条件。 分析：选择硬币时所采用的贪婪准则如下：每一次都选择面值最大的货币来凑足要找的零钱总数，但前提是不能超出要找的67美分。 解：我们用贪婪算法来处理这个问题，首先我们肯定会选择面值为25的货币，这样的货币我们需要两枚，然后我们依据贪婪准则选择面值为10的货币，这样的货币我们需要一枚，接着继续选择面值为5的货币一枚和面值为1的货币两枚。这样我们用贪婪算法就得到了解决问题的办法，而在实际中这也确实是这个问题的最优解。因此在找钱这个问题上，我们采用贪婪算法就能满足我们找出的钱的个数最少这个条件。 贪婪算法同时也有很多无法得出最优解的例子，比如我们熟知的背包问题： 例：有一个背包，容量是M=150。有7个物品，物品不能分割成任意大小。 要求尽可能让装入背包中的物品的总价值最大，但不能超过总容量。 物品：A B C D E F G 重量：35 30 60 50 40 10 25 价值：10 40 30 50 35 40 30 在使用贪婪算法的前提下解决下列问题，能否得到最优结果？ 贪婪算法在资源分配问题中的应用 彭鹏 贵州财经学院研究生 摘要：贪婪算法的典型应用是解决优化问题，这类算法的策略是只顾眼前，而不考虑以后的影响，它的算法简单容易设计实现，因此在许多实际问题中得到广泛的应用，但是它也存在许多的问题，巧妙的使用贪婪思想，将其融入到资源分配问题中解题中，资源分配问题便焕发出了新的光彩。 本文首先对贪婪算法的基本概念做了介绍，然后通过实例论述了贪婪算法在资源分配问题中的应用。 关键字：贪婪算法研究应用资源分配问题 第一章贪婪算法的概念 1.1什么是贪婪算法 贪婪算法是一种对某些求最优解问题的更简单、更迅速的设计技术。用贪婪法设计算法的特点是一步一步地进行，常以当前情况为基础根据某个优化测度作最优选择，而不考虑各种可能的整体情况，它省去了为找最优解要穷尽所有可能而必须耗费的大量时间，它采用自顶向下,以迭代的方法做出相继的贪心选择,每做一次贪心选择就将所求问题简化为一个规模更小的子问题, 通过每一步贪心选择,可得到问题的一个最优解，虽然每一步上都要保证能获得局部最优解，但由此产生的全局解有时不一定是最优的，所以贪婪法不要回溯。 贪婪算法是一种改进了的分级处理方法。其核心是根据题意选取一种量度标准。然后将这多个输入排成这种量度标准所要求的顺序，按这种顺序一次输入一个量。如果这个输入和当前已构成在这种量度意义下的部分最佳解加在一起不能产生一个可行解，则不把此输入加到这部分解中。这种能够得到某种量度意义下最优解的分级处理方法称为贪婪算法。 对于一个给定的问题，往往可能有好几种量度标准。初看起来，这些量度标准似乎都是可取的，但实际上，用其中的大多数量度标准作贪婪处理所得到该量度意义下的最优解并不是问题的最优解，而是次优解。因此，选择能产生问题最优解的最优量度标准是使用贪婪算法的核心。 一般情况下，要选出最优量度标准并不是一件容易的事，但对某问题能选择出最优量度标准后，用贪婪算法求解则特别有效。最优解可以通过一系列局部最优的选择即贪婪选择来达到,根据当前状态做出在当前看来是最好的选择，即局部最优解选择，然后再去解做出这个选择后产生的相应的子问题。每做一次贪婪选择就将所求问题简化为一个规模更小的子 实验一贪心算法应用及设计 实验课时：6学时 二、实验目的： (1)理解贪心选择算法的思想 (2)熟悉单源、哈夫曼、最小生成树等问题的算法； (3)通过对例题分析、设计、调试，体会和掌握贪心法在程序设计中的应用，并进行贪心优化的相应练习。 二、实验原理： 贪心选择算法思想： （1）贪心选择能得到问题的最优解，要证明我们所做的第一步选择一定包含在一个最优解，即存在一个最优解的第一步是从我们的贪心选择开始。 （2）在做出第一步贪心选择后剩下的子问题应该是和原问题类似的规模较小的子问题 为此我们可以用数学归纳法来证明贪心选择能得到问题的最优解。 三、实验内容： 1、活动安排问题。 问题：有n个活动的集合A={1,2,…,n}，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。 求解：安排尽量多项活动在该场地进行，即求A的最大相容子集。 设待安排的11个活动的开始时间和结束时间按结束时间的升序排列如下： 将此表数据作为实现该算法的测试数据。 （1）给出算法基本思想； （2）给出用C/C++或java语言实现程序的代码; public class actionarrange { public static void main(String []args) { int start[]={1,3,0,5,3,5,6,8,8,2,12}; int finish[]={4,5,6,7,8,9,10,11,12,13,14}; boolean arrange[]=new boolean[10]; for(int i=0;i<10;i++){ arrange[i]=false; } int cout=greedySelector(start,finish,arrange); System.out.println("安排的活动数目："+cout); } public static int greedySelector(int s[],int f[], boolean a[]) { int n=s.length-1; a[0]=true; System.out.println("活动安排情况如下："); System.out.println("活动序号开始时间结束时间"); System.out.println(" "+0+" "+s[0]+" "+f[0]); int j=1; int count=1; for (int i=1;i 贪心算法的基本思想是找出整体当中每个小的局部的最优解，并且将所有的这些局部最优解合起来形成整体上的一个最优解。因此能够使用贪心算法的问题必须满足下面的两个性质： 1.整体的最优解可以通过局部的最优解来求出； 2.一个整体能够被分为多个局部，并且这些局部都能够求出最优解。使用贪心算法当中的两个典型问题是活动安排问题和背包问题。 在对问题求解时，总是作出在当前看来是最好的选择。也就是说，不从整体上加以考虑，它所作出的仅仅是在某种意义上的局部最优解（是否是全局最优，需要证明）。 特别注意：若要用贪心算法求解某问题的整体最优解，必须首先证明贪心思想在该问题的应用结果就是最优解！！ 以经典的活动安排为例： 1、若A是E的最优解，那么E-A 也是问题的最优解，在余下的问题里，继续拿最早结束的； 2、拿可以开始的最早结束。(所以要按结束时间排序一次，然后把可以开始的选择上，然后继续向后推) 贪心子结构是独立的（往往用标志判断而已），不同于动态规划（后面每一边的计算要用到前一步的值，另外开辟空间来保存） 贪心算法的基本步骤： 1、从问题的某个初始解出发。 2、采用循环语句，当可以向求解目标前进一步时，就根据局部最优策略，得到一个部分解，缩小问题的范围或规模。 3、将所有部分解综合起来，得到问题的最终解。 如最经典的活动安排问题，按结束时间从小到大排序，这样找出第一个节目后，剩下的节目已经是最safe的子结构了，再从子结构中最最早结束但又不和上一次观看的节目有冲突的节目 void arrange(int s[],int f[],bool A[],int n) { A[0] = true; int lastSelected = 0; for (int i = 1;i Matlab中贪婪算法求解背包问题的研究与应用 晏 杰 【摘 要】本文对贪婪算法进行了分析，总结了贪婪算法解决问题的思路，根据改进的贪婪算法解决策略，通过Matlab对贪婪算法在背包问题中的应用进行了具体实现和详细的分析. 【期刊名称】赤峰学院学报（自然科学版） 【年(卷),期】2012(000)017 【总页数】2 【关键词】Matlab；贪婪算法；背包；研究与应用 1 引言 为了满足人们对大数据量信息处理的渴望,为解决各种实际问题,计算机算法学得到了飞速的发展,线性规划、动态规划、贪婪策略等一系列运筹学模型纷纷运用到计算机算法学中,产生了解决各种现实问题的有效算法.贪婪算法主要用于设计数值最优化问题的算法，它是一种求最优解问题的最直接的设计技术，它不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题能产生整体最优解或者整体最优解的近似解.算法容易实现也易于理解，这使得算法在编码和执行的过程中都有着一定的速度优势，同时也提高了效率并节省了时间. 2 贪婪算法概述 2.1 贪婪算法的定义 贪婪算法又叫登山法，它的根本思想是逐步到达山顶，即逐步获得最优解，是解决最优化问题时的一种简单但适用范围有限的策略. 2.2 贪婪算法思想 贪婪算法采用逐步构造最优解的方法，即在每个阶段，都选择一个看上去最优的策略（在一定的标准下）.策略一旦选择就不可再更改，贪婪决策的依据称为贪婪准则，也就是从问题的某一个初始解出发并逐步逼近给定的目标，以尽可能快的要求得到更好的解.而且它在设计时没有固定的框架，关键在于贪婪策略的选择.但要注意的是选择的贪婪策略要具有无后向性，即某阶段状态一旦确定下来后，不受这个状态以后的决策的影响，也就是说某状态以后的过程不会影响以前的状态，只与当前状态有关. 2.3 贪婪算法的特性 贪婪算法及贪婪算法可解决的问题通常大部分都有如下的特性: Greedy Algorithm：贪心算法 算法思想 在贪婪算法中采用逐步构造最优解的方法。在每个阶段，都作出一个看上去最优的决策（在一定的标准下）。决策一旦作出，就不可再更改。作出贪婪决策的依据称为贪婪准则（greedy criterion），也就是从问题的某一个初始解出发逐步逼近给定的目标，以尽可能快的地求得更好的解。当达到某算法中的某一步不能再继续前进时，算法停止。 虽然设计一个好的求解算法更像是一门艺术，而不像是技术，但仍然存在一些行之有效的能够用于解决许多问题的算法设计方法，你可以使用这些方法来设计算法，并观察这些算法是如何工作的。一般情况下，为了获得较好的性能，必须对算法进行细致的调整。但是在某些情况下，算法经过调整之后性能仍无法达到要求，这时就必须寻求另外的方法来求解该问题。Greedy Algorithm在设计方面不能保证求得的最后解是最佳的和不能用来求最大或最小解问题，只能求满足某些约束条件的可行解的范围。 Example1 例1-4 [找零钱] 一个小孩买了价值少于1美元的糖，并将1美元的钱交给售货员。售货员希望用数目最少的硬币找给小孩。假设提供了数目不限的面值为2 5美分、1 0美分、5美分、及1美分的硬币。售货员分步骤组成要找的零钱数，每次加入一个硬币。选择硬币时所采用的贪婪准则如下：每一次选择应使零钱数尽量增大。为保证解法的可行性（即：所给的零钱等于要找的零钱数），所选择的硬币不应使零钱总数超过最终所需的数目。 假设需要找给小孩6 7美分，首先入选的是两枚2 5美分的硬币，第三枚入选的不能是2 5美分的硬币，否则硬币的选择将不可行（零钱总数超过6 7美分），第三枚应选择1 0美分的硬币，然后是5美分的，最后加入两个1美分的硬币。 贪婪算法有种直觉的倾向，在找零钱时，直觉告诉我们应使找出的硬币数目最少（至少是接近最少的数目）。可以证明采用上述贪婪算法找零钱时所用的硬币数目的确最少（见练习1）。 Example2 例1-5 [机器调度] 现有n 件任务和无限多台的机器，任务可以在机器上得到处理。每件任务的开始时间为si，完成时间为fi ，si < fi 。[si , fi ] 为处理任务i 的时间范围。两个任务i，j 重指两个任务的时间范围区间有重叠，而并非是指i，j 的起点或终点重合。例如：区间[ 1，4 ]与区间[ 2，4 ]重叠，而与区间[ 4，7 ]不重叠。一个可行的任务分配是指在分配中没有两件重叠的任务分配给同一台机器。因 贪心算法 贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。 贪心法是指从问题的初始状态出发，通过若干次的贪心选择而得出最优解或较优解的一种阶梯方法。事实上，从贪心算法“贪心”一词便可以看出，贪心法总是做出在当前看来是最优的选择，也就是说贪心法不是从整体上加以考虑他所做出的选择只是在某种意义上的局部最优解，而血多问题自身的特性决定了该题可以用贪心算法就能得到最优解。 贪心算法的基本思路 1.建立数学模型来描述问题。 2.把求解的问题分成若干个子问题。 3.对每一子问题求解，得到子问题的局部最优解。 4.把子问题的解局部最优解合成原来解问题的一个解。 实现该算法的过程： 从问题的某一初始解出发； while 能朝给定总目标前进一步 do 求出可行解的一个解元素； 由所有解元素组合成问题的一个可行解。 【问题举例】 11-1-1 购买新年贺卡 问题描述： 新年快到了，笑笑打算给他的好友们发新年贺卡，而且他已经选好了子要购买的样式。俗话说得好，货比三家，笑笑来到了商店，看了各个商铺同一种贺卡的价钱。不仅如此，笑笑还记住了每个商铺的存货量。已知笑笑打算购买m 张贺卡，问他最少花多少钱。 输入格式： 第一行有两个整数m和n。其中m表示要购买的贺年卡的数量，n表示商铺的个数。以下n行，每行有两个整数，分别表示该商铺这种贺年卡的单价和存货量。 输出格式： 进一个数，表示笑笑所化的最少的钱数。 输入样例： 10 4 4 3 6 2 8 10 3 6 输出样例： 36 数据规模： 0贪心算法经典例题
【精选】贪心算法的应用
利用贪婪算法实现多种实际问题
贪心算法详解分析
贪婪算法在排课问题中分析与应用
算法分析与设计选修课-贪心算法应用研究
贪心算法的应用
贪婪算法
贪心算法设计与应用
贪心算法的应用实例
贪心算法浅析
贪婪算法思想及其应用
贪婪算法在资源分配问题中的应用----彭鹏
实验1 贪心算法应用及设计
贪心算法
Matlab中贪婪算法求解背包问题的研究与应用
贪婪算法
贪心算法