利用贪婪算法实现多种实际问题.doc

利用贪婪法实现多种实际问题
《算法设计与分析》课程设计任务书

学院名称： 数学与计算机学院 专业： 信息与计算科学专业 年级： 2007

一、设计题目
题目十四：利用贪婪算法实现多种实际问题

二、主要内容
给出多种可以用贪婪算法解决的典型问题，并分析、证明、编程。
三、具体要求
（1）贪婪算法的基本思想；
（2）给出背包问题的贪婪算法；
（3）给出有限期计算机作业调度的贪婪算法；
（4）给出上面两个算法的证明；
（5）给出上面两个算法的程序。
（6）给出时间复杂度。
四、主要技术路线提示
在用贪婪算法解决资源分配问题、布线问题、0-1背包问题过程中，使用贪婪算法解决问题，通常需要做好以下几个方面的工作：
1、明确问题的求解目标。
2、分析问题所包含的约束条件。
3、建立优化函数。优化函数通常可以通过综合分析问题的求解目标及约束条件归纳出来。
4、制定贪婪准则。
五、进度安排
1、第一周:分析题目的需求，设计抽象数据类型、构思算法、通过类的设计实现抽象数据类型并编写上机程序
2、第二周 完成程序开发，进行测试并分析结果，最后撰写课程设计报告
六、完成后应上交的材料
上交的成果的内容必须由以下四个部分组成，缺一不可。
1．上交源程序：学生按照课程设计的具体要求所开发的所有源程序（应该放到一个文件夹中）。
2．上交程序的说明文件：（保存在.txt中），在说明文档中应该写明上交程序所在的目录，上交程序的主程序文件名，如果需要安装，要有程序的安装使用说明。
3．课程设计报告电子文档：（保存在word 文档中，文件名要求 按照“学号姓名算法分析课设报告.doc”起名，如文件名为“200300109张三算法分析课设报告.doc” ），按照课程设计的具体要求建立的功能模块，每个模块要求按照如下几个内容认真完成：
其中包括：
（1）需求分析：
在该部分中叙述每个模块的功能要求等。
（2）概要设计
在此说明每个部分的算法设计说明（可以是描述算法的流程图），每个程序中使用的存储结构设计说明（如果指定存储结构请写出该存储结构的定义。
（3）详细设计
各个算法实现的源程序，对每个题目要有相应的源程序（可以是一组源程序，每个功能模块采用不同的函数实现）。
源程序要按照写程序的规则来编写。要结构清晰，重点函数的重点变量，重点功能部分要加上清晰的程序注释。
（4）调试分析
包括测试数据，测试输出的结果，时间复杂度分析，和每个模块设计和调试时存在问题的思考（问题是哪些？问题如何解决？），算法的改进设想。
（5）课设总结
总结可以包括 ：课程设计过程的收获、遇到问题、遇到问题解决问题过程的思考、程序调试能力的思考、对算法设计与分析这门课程的思考、在课程设计过程中对《算法设计与分析》课程的认识等内容。
4．课程设计报告打印稿。
七、推荐参考资料
教 材：
《算法设计与分析》 Anany Levitin 著 潘彦译 清华大学出版社，2007。
《算法设计与分析》 宋 文 等编 重庆大学出版社，2001。
参考书：[1] 《算法设计与分析》 周培德 电子工业出版社，2000。
[2] 《算法设计与分析》 王晓东 电子工业出版社，2004

指导教师 签名日期 年 月 日

系 主 任 审核日期 年 月 日

I

目 录
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

10
利用贪婪法实现多种实际问题

引言
为了满足人们对大数据量信息处理的渴望,为解决各种实际问题,计算机算法学得到了飞速的发展,线性规划、动态规划、贪婪策略等一系列运筹学模型纷纷运用到计算机算法学中,产生了解决各种现实问题的有效算法。虽然设计一个好的求解算法更像是一门艺术，而不像是技术，但仍然存在一些行之有效的能够用于解决许多问题的算法设计方法，可以使用这些方法来设计算法，并观察这些算法是如何工作的。一般情况下，为了获得较好的性能，必须对算法进行细致的调整。但是在某些情况下，算法经过调整之后性能仍无法达到要求，这时就必须寻求另外的方法来求解该问题。
目前常用的算法设计技术有分治法、回溯法、贪婪法、动态规划算法、分支限界法等。其中分治法、回溯法主要用于设计非数值问题的算法,而贪婪法、动态规划算法、分支限界法则主要用于设计数值最优化问题的算法。贪婪法是一种求最优解问题的最直接的设计技术，它不是对所有问题都能得到整体最优解，但对许多问题可能产生整体最优解。
2贪婪算法的概述
2.1 什么是贪婪算法
贪婪算法是一种对某些求最优解问题的更简单、更迅速的设计技术。用贪婪法设计算法的特点是一步一步地进行，常以当前情况为基础根据某个优化测度作最优选择，而不考虑各种可能的整体情况，它省去了为找最优解要穷尽所有可能而必须耗费的大量时间，它采用自顶向下,以迭代的方法做出相继的贪心选择,每做一次贪心选择就将所求问题简化为一个规模更小的子问题, 通过每一步贪心选择,可得到问题的一个最优解，虽然每一步上都要保证能获得局部最优解，但由此产生的全局解有时不一定是最优的，所以贪婪法不要回溯。
贪婪算法是一种改进了的分级处理方法。其核心是根据题意选取一种量度标准。然后将这多个输入排成这种量度标准所要求的顺序，按这种顺序一次输入一个量。如果这个输入和当前已构成在这种量度意义下的部分最佳解加在一起不能产生一个可行解， 则不把此输入加到这部分解中。这种能够得到某种量度意义下最优解的分级处理方法称为贪婪算法。
对于一个给定的问题，往往可能有好几种量度标准。初看起来，这些量度标准似乎都是可取的，但实际上，用其中的大多数量度标准作贪婪处理所得到该量度意义下的最优解并不是问题的最优解，而是次优解。因此，选择能产生问题最优解的最优量度标准是使用贪婪算法的核心。
一般情况下，要选出最优量度标准并不是一件容易的事，但对某问题能选择出最优量度标准后，用贪婪算法求解则特别有效。最优解可以通过一系列局部最优的选择即贪婪选择来达到,根据当前状态做出在当前看来是最好的选择，即局部最优解选择，然后再去解做出这个选择后产生的相应的子问题。每做一次贪婪选择就将所求问题简化为一个规模更小的子问题，最终可得到问题的一个整体最优解。
2.2贪婪算法的特性
贪婪算法及贪婪算法可解决的问题通常大部分都有如下的特性:
（1） 有一个以最优方式来解决的问题。为了构造问题的解决方案,有一个候选的对象的集合：比如不同面值的硬币。
（2） 随着算法的进行,将积累起其它两个集合：一个包含已经被考虑过并被选出的候选对象,另一个包含已经被考虑过但被丢弃的候选对象。
（3） 有一个函数来检查一个候选对象的集合是否提供了问题的解答。该函数不考虑此时的解决方法是否最优。
（4） 还有一个函数检查是否一个候选对象的集合是可行的,也即是否可能往该集合上添加更多的候选对象以获得一个解。和上一个函数一样,此时不考虑解决方法的最优性。
（5） 选择函数可以指出哪一个剩余的候选对象最有希望构成问题的解。
（6） 最后,目标函数给出解的值。
为了解决问题,需要寻找一个构成解的候选对象集合,它可以优化目标函数,贪婪算法一步一步的进行。起初,算法选出的候选对象的集合为空。接下来的每一步中,根据选择函数,算法从剩余候选对象中选出最有希望构成解的对象。如果集合中加上该对象后不可行，那么该对象就被丢弃并不再考虑；否则就加到集合里。每一次都扩充集合，并检查该集合是否构成解。如果贪婪算法正确工作，那么找到的第一个解通常是最优的。
2.3贪婪算法解决问题的步骤
贪婪算法的一般解题步骤:
设计中一类非常重要的问题。每一个最优化问题都包含一组约束条件和一个优化函数，满足约束条件的问题求解方案称为问题的可行解，使优化函数取得最优值的可行解称为问题的最优解。贪婪算法是解决最优化问题的一种基本方法。它采用逐步构造最优解的思想，在问题求解的每一个阶段，都做出一个在一定标准下看上去最优的决策；决策一旦作出，就不可再更改。制定决策的依据称为贪婪准则。使用贪婪算法解决问题，通常需要做好以下几个方面的工作：
1、明确问题的求解目标。
2、分析问题所包含的约束条件。
3、建立优化函数。优化函数通常可以通过综合分析问题的求解目标及约束条件归纳出来。
4、制定贪婪准则。清楚问题的求解目标、所包含的约束条件及优化函数之后，就可以着手制定一个可行的贪婪准则。贪婪准则的制定是用贪婪算法解决最优化问题的关键，它关系到问题能否得到成功解决及解决质量的高低。
2.4贪婪算法的优缺点
贪婪算法是一种重要的算法设计策略,而且其效率高。贪婪算法并不从整体最优考虑,它所做出的选择只是在某种意义上的局部最优选择,即在当前看来最好的选择。希望通过每次所做的贪婪选择导致最终结果是问题的一个最优解。贪婪算法具有良好的爬坡能力，一般情况下该算法都可以较快地求出满足计算精度要求的近似最优解，当算法不能在限定的计算时间内找到满足问题要求的近似最优解时，给出一个可行解及计算误差，作为决策参考。但是随着问题规模和复杂度的不断提升，单一的算法在其收敛性和求解速度等方面已经表现出局限性。即使贪婪算法的效率很高，它也只适用于少量的实例。
假设某职工的工资为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<fi。如果选择了课程i，则它在半开时间区间[si,fi]内占用资源。若区间[si,fi]与区间[sj,fj]不相交，则称课程i与课程j是相容的。也就是说，当si>=fj或sj>=fi时，课程i与课程j相容。
设A是所要求安排的课程的m个最大相容课程子集，即用A[i][j]存储对最小教室所选择的课程，A[i][m]存储对最大教室所选择的课程。若课程i在集合A[i][x]中(x=1,2,… …,m)，则A[i][x]必为true(存入其课程序号)。变量J(x)用以记录最近一次加入到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’)。不考虑顶点,边所代表的具体含义,显然,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)否则,修改矩阵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<min,更新布线代价和最小值min,及其对应的布线方案x[1:n]
(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 装入背包多次,也不能只装入部分的物品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 改进的贪婪算法策略
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 ] ; / / 目标函数
　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 总结
贪婪算法解决优化问题, 在复杂的多目标规划问题, 工农业生产中的配管、配线问题, 以及机器学习, 图象识别等问题中都有应用,并且是比较有效的方法之一,虽然贪婪算法在许多优化问题中都有成功的应用, 但其本身也存在许多不足。例如只进行局部的优化 ,只着眼于眼前的问题考虑,将来的发生的情况不考虑。对于一些复杂的问题不能很好的解决。从而导致算法的收敛性能差, 需要很长时间才能找到最优解, 这些阻碍了贪婪算法的推广应用。如何改善贪婪算法使其更好地应用于实际问题的解决中, 是诸多学者探索的一个主要课题。
贪婪算法在应用方面的丰硕成果, 使人们对它的发展前景充满信心。其主要应用领域在于机器人学(移动机器人路径规划, 关节机器人运动轨迹规划, 细胞机器人的结构优化等) , 控制(瓦斯管道控制, 布线控制等) , 规划(生产规划, 并行机任务分配等) ,设计(通信网络设计等) , 组合优化(背包问题, 图分划问题等) , 图象处理,信号处理等方面.它的应用将涉及更多的方面。
贪婪算法可将一个问题的解决方案视为一系列决策的结果。在贪婪算法中,每用一次贪婪准则便做出一个不可撤回的决策,个最优子序列。当一个问题具有最优子结构时,我们会想到存在着更简单、有效的方法,只要我们总是做出当前看来最好的选择就可以了。贪婪算法所作的选择可以依赖于以往所作过的选择,但决不依赖于将来的选择,也不依赖于子问题的解,这使得算法在编码和执行的过程中都有着一定的速度优势。如果一个问题可以同时用几种方法解决,贪婪算法应该是最好的选择之一。但是贪婪算法并不是对所有的问题都能得到整体最优解或最理想的近似解,与回溯法等比较,它的适用区域相对狭窄许多,因此正确地判断它的应用时机十分重要，贪婪算法的优点结合其他算法的应用将是以后研究的方向。
参考文献
[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],北京:清华大学出版社
- 9 -