第 1 章 贪婪算法

2016-02-19 13:06 6 1 收藏

下面图老师小编要向大家介绍下第 1 章 贪婪算法,看起来复杂实则是简单的,掌握好技巧就OK,喜欢就赶紧收藏起来吧!

【 tulaoshi.com - 编程语言 】

虽然设计一个好的求解算法更像是一门艺术,而不像是技术,但仍然存在一些行之有效的能够用于解决许多问题的算法设计方法,你可以使用这些方法来设计算法,并观察这些算法是如何工作的。一般情况下,为了获得较好的性能,必须对算法进行细致的调整。但是在某些情况下,算法经过调整之后性能仍无法达到要求,这时就必须寻求另外的方法来求解该问题。
  
  本章首先引入最优化的概念,然后介绍一种直观的问题求解方法:贪婪算法。最后,应用该算法给出货箱装船问题、背包问题、拓扑排序问题、二分覆盖问题、最短路径问题、最小代价生成树等问题的求解方案。
  
  
  1.1 最优化问题 本章及后续章节中的许多例子都是最优化问题( optimization problem),每个最优化问题都包含一组限制条件( c o n s t r a i n t)和一个优化函数( optimization function),符合限制条件的问题求解方案称为可行解( feasible solution),使优化函数取得最佳值的可行解称为最优解(optimal solution)。
  
   例1-1 [ 渴婴问题] 有一个非常渴的、聪明的小婴儿,她可能得到的东西包括一杯水、一桶牛奶、多罐不同种类的果汁、许多不同的装在瓶子或罐子中的苏打水,即婴儿可得到n 种不同的饮料。根据以前关于这n 种饮料的不同体验,此婴儿知道这其中某些饮料更合自己的胃口,因此,婴儿采取如下方法为每一种饮料赋予一个满足度值:饮用1盎司第i 种饮料,对它作出相对评价,将一个数值si 作为满足度赋予第i 种饮料。
  
   通常,这个婴儿都会尽量饮用具有最大满足度值的饮料来最大限度地满足她解渴的需要,但是不幸的是:具有最大满足度值的饮料有时并没有足够的量来满足此婴儿解渴的需要。设ai是第i 种饮料的总量(以盎司为单位),而此婴儿需要t 盎司的饮料来解渴,那么,需要饮用n种不同的饮料各多少量才能满足婴儿解渴的需求呢?
  
   设各种饮料的满足度已知。令xi 为婴儿将要饮用的第i 种饮料的量,则需要解决的问题是:
  
   找到一组实数xi(1≤i≤n),使n ?i = 1si xi 最大,并满足:n ?i=1xi =t 及0≤xi≤ai 。
  
   需要指出的是:假如n ?i = 1ai t,则不可能找到问题的求解方案,因为即使喝光所有的饮料也不能使婴儿解渴。
  
   对上述问题精确的数学描述明确地指出了程序必须完成的工作,根据这些数学公式,可以对输入/ 输出作如下形式的描述:
  
   输入:n,t,si ,ai(其中1≤i≤n,n 为整数,t、si 、ai 为正实数)。
  
   输出:实数xi(1≤i≤n),使n ?i= 1si xi 最大且n ?i=1xi =t(0≤xi≤ai)。假如n ?i = 1ai
  
   在这个问题中,限制条件是n ?i= 1xi =t 且0≤xi≤ai,1≤i≤n。而优化函数是n ?i= 1si xi 。任何满足限制条件的一组实数xi 都是可行解,而使n ?i= 1si xi 最大的可行解是最优解。
  
   例1-2 [装载问题] 有一艘大船预备用来装载货物。所有待装货物都装在货箱中且所有货箱的大小都一样,但货箱的重量都各不相同。设第i 个货箱的重量为wi(1≤i≤n),而货船的最大载重量为c,我们的目的是在货船上装入最多的货物。
  
   这个问题可以作为最优化问题进行描述:设存在一组变量xi ,其可能取值为0或1。如xi 为0,则货箱i 将不被装上船;如xi 为1,则货箱i 将被装上船。我们的目的是找到一组xi ,使它满足限制条件n ?i = 1wi xi ≤c 且x i ? {0, 1}, 1 ≤i≤n。相应的优化函数是n ?i= 1xi 。
  
   满足限制条件的每一组xi 都是一个可行解,能使n ?i= 1xi 取得最大值的方案是最优解。
  
   例1-3 [最小代价通讯网络] 城市及城市之间所有可能的通信连接可被视作一个无向图,图的每条边都被赋予一个权值,权值表示建成由这条边所表示的通信连接所要付出的代价。包含图中所有顶点(城市)的连通子图都是一个可行解。设所有的权值都非负,则所有可能的可行解都可表示成无向图的一组生成树,而最优解是其中具有最小代价的生成树。
  
   在这个问题中,需要选择一个无向图中的边集合的子集,这个子集必须满足如下限制条件:所有的边构成一个生成树。而优化函数是子集中所有边的权值之和。

来源:https://www.tulaoshi.com/n/20160219/1602979.html

延伸阅读
标签: ASP
综述 MD5的全称是Message-Digest Algorithm 5(信息-摘要算法),在90年代初由MIT Laboratory for Computer Science和RSA Data Security Inc的Ronald L. Rivest开发出来,经MD2、MD3和MD4发展而来。它的作用是让大容量信息在用数字签名软件签署私人密匙前被"压缩"成一种保密的格式(就是把一个任意长度的字节串变换成一定长的大整数)。...
第2章 可控游戏类2.4 梭 哈 游 戏(1) 第2章 可控游戏类2.4 梭 哈 游 戏(1) 游戏说明“梭哈游戏”是一种扑克游戏,5张牌比大小,同花顺最大。由于此游戏简单,既含有技巧也有很大的运气成分,所以流传非常广泛。游戏的时候单击“增加”按钮开始下注,然后再单击“开始”按钮,就会随机的产生五张牌,选择将要保留的牌,再单击“开始”按钮,如...
标签: 游戏动漫
《失落的星球2》狩猎之旅第1章 美味!巨大山椒鱼 《失落的星球2》中文主题站 | 《失落的星球2》讨论专区 《失落的星球2》狩猎攻略第1章 | 第2章  | 第3章  | 第4章(上)  | 第4章(下) | 第五章 | 第六章(上) | 第六章(下) ()   《失落的星球2》上市至今一周,相...
这一位网名:太美丽,poluoluo官方群会员 http://www.toomo.com/zsj/ 很不错的作品. 手绘的这个不错 石子儿 上海的一位设计师,不清楚专业是什么,但似乎是位优秀的网页设计师,FLASH做得不错,也象是插画师,也弄弄工业设计的东西.不论是做什么,他的博客设计得实在太漂亮了,猫猫把他拼了起来. http://pinnawhite.com/weblog ...
标签: 游戏动漫
《生化危机启示录》流程攻略 第1章_3DS攻略操作方式一览 A 吃药草(有的前提下) B 取消 Y 开门 X 使用副武器 R 瞄准 摇杆 角色移动 L+左摇杆 平行移动 摇杆下+X 快速转身 方向...

经验教程

700

收藏

39
微博分享 QQ分享 QQ空间 手机页面 收藏网站 回到头部