算法->贪心法

发布者:caijt最新更新时间:2015-05-18 来源: 51hei关键字:算法  贪心法 手机看文章 扫描二维码
随时随地手机看文章
一、基本概念:
 
     所谓贪心算法是指,在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,他所做出的仅是在某种意义上的局部最优解。
     贪心算法没有固定的算法框架,算法设计的关键是贪心策略的选择。必须注意的是,贪心算法不是对所有问题都能得到整体最优解,选择的贪心策略必须具备无后效性,即某个状态以后的过程不会影响以前的状态,只与当前状态有关。
    所以对所采用的贪心策略一定要仔细分析其是否满足无后效性。

二、贪心算法的基本思路:
    1.建立数学模型来描述问题。
    2.把求解的问题分成若干个子问题。
    3.对每一子问题求解,得到子问题的局部最优解。
    4.把子问题的解局部最优解合成原来解问题的一个解。

三、贪心算法适用的问题
      贪心策略适用的前提是:局部最优策略能导致产生全局最优解。
    实际上,贪心算法适用的情况很少。一般,对一个问题分析是否适用于贪心算法,可以先选择该问题下的几个实际数据进行分析,就可做出判断。
 
四、贪心算法的实现框架
    从问题的某一初始解出发;
    while (能朝给定总目标前进一步)
    { 
          利用可行的决策,求出可行解的一个解元素;
    }
    由所有解元素组合成问题的一个可行解;
  
五、贪心策略的选择
     因为用贪心算法只能通过解局部最优解的策略来达到全局最优解,因此,一定要注意判断问题是否适合采用贪心算法策略,找到的解是否一定是问题的最优解。
 
六、例题分析
    下面是一个可以试用贪心算法解的题目,贪心解的确不错,可惜不是最优解。
    [背包问题]有一个背包,背包容量是M=150。有7个物品,物品可以分割成任意大小。
    要求尽可能让装入背包中的物品总价值最大,但不能超过总容量。
    物品 A B C D E F G
    重量 35 30 60 50 40 10 25
    价值 10 40 30 50 35 40 30
    分析:
    目标函数: ∑pi最大
    约束条件是装入的物品总重量不超过背包容量:∑wi<=M( M=150)
    (1)根据贪心的策略,每次挑选价值最大的物品装入背包,得到的结果是否最优?
    (2)每次挑选所占重量最小的物品装入是否能得到最优解?
    (3)每次选取单位重量价值最大的物品,成为解本题的策略。
    值得注意的是,贪心算法并不是完全不可以使用,贪心策略一旦经过证明成立后,它就是一种高效的算法。
    贪心算法还是很常见的算法之一,这是由于它简单易行,构造贪心策略不是很困难。
    可惜的是,它需要证明后才能真正运用到题目的算法中。
    一般来说,贪心算法的证明围绕着:整个问题的最优解一定由在贪心策略中存在的子问题的最优解得来的。
    对于例题中的3种贪心策略,都是无法成立(无法被证明)的,解释如下:
    (1)贪心策略:选取价值最大者。反例:
    W=30
    物品:A B C
    重量:28 12 12
    价值:30 20 20
    根据策略,首先选取物品A,接下来就无法再选取了,可是,选取B、C则更好。
    (2)贪心策略:选取重量最小。它的反例与第一种策略的反例差不多。
    (3)贪心策略:选取单位重量价值最大的物品。反例:
    W=30
    物品:A B C
    重量:28 20 10
    价值:28 20 10
    根据策略,三种物品单位重量价值一样,程序无法依据现有策略作出判断,如果选择A,则答案错误。
关键字:算法  贪心法 引用地址:算法->贪心法

上一篇:数据结构->栈(C实现)
下一篇:浅谈用单片机模拟PLC(山寨三菱系列)

推荐阅读最新更新时间:2024-03-16 14:02

日本现超高性能新型量子计算机:瞬间解析复杂算法
  据日本共同社报道,日本NTT物性科学基础研究所等11月20日宣布成功研发了超高性能的新型 量子计算机 ,可以瞬间解析以往计算机不易解开的复杂算法。研究所计划进一步优化性能,使之成为提高交通网、无线通信等各类网络效率的强力武器。下面就随嵌入式小编一起来了解一下相关内容吧。   研究所还计划27日起在网络公开该系统以便一般用户试用。   围绕 量子计算机 ,正在进行着各种不同类型的研发。此次的新型计算机类型与解析银行结算和电商交易密码的不同。   日本现超高性能新型量子计算机:瞬间解析复杂算法   计算机由该研究所首席特别研究员武居弘树等人研发。该机擅长从庞大的排列组合中找出最佳正确答案,在将2000人按关系亲疏分组的测试中
[嵌入式]
防止“手机叫喊” CSR利用HushAlert! 增强其多媒体蓝牙产品
全球领先的蓝牙连接及无线技术提供商CSR公司(伦敦证券交易所:CSR.L)宣布,Q Talk公司加入其eXtension伙伴计划,并将HushAlert! 技术整合到CSR公司最新的BlueCore5-多媒体平台。Q Talk公司的HushAlert! 设计目的,是解决在靠近他人时、通过移动电话传话的音量过大这个特定的用户问题。此项技术将使用者可以控制自己说话的音量,用户可在以前感觉不适宜通话的环境中也能够进行电话通讯,并尽量减少通话时说话音量过大所带来的不良影响。 Q Talk公司的HushAlert! 可通过预先确定的最佳音量阈值,并且持续监控移动电话使用者的音量。如果使用者的通话音量超过这个阈值,系统就会通过视觉、听觉或触觉反
[焦点新闻]
苹果调整App Store应用商店算法为自家应用排名
根据《纽约时报》的一份新报告显示,苹果App Store的软件排名一般都会将自家的iPhone和iPad应用程序排在前列且苹果经常会引导客户下载自家应用程序,而另一份报告也做出了类似的评论。 不过这种情况似乎即将迎来改变,苹果已准备针对App Store软件排名算法进行修改。   苹果公司高管菲尔·席勒(Phil Schiller)和埃迪·库伊(Eddy Cue)近日在接受《纽约时报》采访时透露,苹果公司目前已调整了App Store应用商店的算法,目的是“阻止”自己的各个应用过多地出现在搜索结果中。   苹果公司于7月份更新了自己的App Store排名算法,预计搜索结果很快将变得更加平衡。且由于苹果公司面临来自欧盟的反垄断
[手机便携]
斯坦福AI算法能预测死亡 准确率高达90%
斯坦福大学的一个研究小组通过使用人工智能算法来预测病人的死亡,希望能够改善重症患者临终关怀时机。在测试中,这个系统被证明是非常准确的,正确预测90%病例的死亡结果。但是,尽管该系统能够预测病人何时可能死亡,但它仍然无法告诉医生它是如何得出结论的。   预测死亡是非常困难的。医生必须考虑一系列复杂的因素,从病人的年龄和家族史到对药物的反应,以及疾病本身的性质。让事情变得复杂的是,医生必须与自己的自负,偏见或无意识地不愿意评估病人还有多少光景做斗争。有时候医生能准确预测,但是有些时候病人可能会推迟数月(如果不是几年的话),无论是过早还是过晚地预测死亡,都不利于临终关怀。   这给临终关怀的精确安排带来了问题
[安防电子]
foc电机控制需要几个pwm foc控制算法介绍
foc电机控制需要几个pwm FOC(Field-Oriented Control)电机控制需要使用两个PWM信号来控制电机,具体分为一般PWM和扩展PWM两种。 一般PWM用于控制电机的直流母线电压,其输出频率一般为几千赫兹,可以有效地抑制电机的噪声和震动。通过PWM的占空比来调节直流电压,从而实现对电机的调速和调转矩。一般PWM一般由开发板或者控制芯片的内置模块实现。 扩展PWM用于控制电机的电流,其输出频率的设置一般要远远低于一般PWM的频率,以保证电路的稳定性和控制精度。扩展PWM的任务是将控制算法的电流控制命令转换为电机的相电流,从而实现对电机的转矩和速度控制。在FOC控制中,扩展PWM一般需要由开发者根据自身电
[嵌入式]
日本法院或要求大型科技企业开放算法
北京时间7月5日早间消息,据报道,日本法律专家表示,一个与当地餐馆网站有关的反垄断案件可能会改变Google、Facebook和亚马逊等大型互联网平台在该国的运作方式,法院将迫使这些企业披露其秘密算法的内部运作情况。 上个月,东京一家法院在对日本最大的餐馆评论平台Tabelog的运营商Kakaku.com提起的反垄断案,法院在本案中裁定Hanryumura(一家韩式烧烤连锁店)胜诉。 Hanryumura成功地证明,Kakaku.com改变了用户评分的计算方式,从而损害了其餐厅的销售工作。虽然Kakaku.com被命令向Hanryumura支付3840万日元(28.4万美元)的“滥用优势谈判地位”的赔偿金,但这家互联网公司
[嵌入式]
Cortex--M0单片机二-十进制整数转换的快速算法
  为了提高Cortex—M0系列单片机应用系统的二进制到十进制BCD码整数转换代码的执行效率,采用除十求余数法来实现。该快速算法的核心内容是通过高效的汇编语言来实现常数除法,无论在程序代码的运行时间和存储空间上,都远胜于sprintf函数。   在单片机应用系统中,一般都需要高效快速地完成系统所需要的任务,并在任务完成后使系统进入睡眠或低功耗状态,以便最大限度地节省系统功耗,增强系统的抗干扰能力。因此,必须优化和提高系统中各个模块的运算速度,以最大限度地压缩软件运行时间。许多单片机应用系统中都需要进行二进制整数转换为十进制BCD码的操作,以便实现系统信息的显示。对于Cortex—M0系列单片机,由于其指令系统中没有十进制调整指令
[单片机]
Cortex--M0单片机二-十进制整数转换的快速<font color='red'>算法</font>
基于DSP控制的PFC变换器的新颖采样算法
摘要:为DSP控制的功率因数校正(PFC)变换器提出了一种新颖的采样算法,它能够很好地消除PFC电路中高频开关动作产生的振荡对数字采样的影响。尤其是当开关频率高于30kHz时,所提出的新颖采样算法能够更好地提高开关抗噪声性能。最后将此算法运用到一台2kW的PFC变换器中,实验结果证明了该算法对于分析、设计和调试所有含开关的数字采样电路均有实用参考价值。 关键词:数字信号处理;功率因数校正;采样算法 引言 数字信号处理器(DSP)已经被广泛应用于通信,智能控制,运动控制等许多领域中。由于具有处理速度快、灵活、精确、可靠等特点,DSP已逐渐取代了传统的模拟控制,例如开关电源中的DC/DC变换器,PFC变换器,以及高频脉宽调制(P
[嵌入式]
小广播
添点儿料...
无论热点新闻、行业分析、技术干货……
设计资源 培训 开发板 精华推荐

最新单片机文章
何立民专栏 单片机及嵌入式宝典

北京航空航天大学教授,20余年来致力于单片机与嵌入式系统推广工作。

换一换 更多 相关热搜器件
电子工程世界版权所有 京B2-20211791 京ICP备10001474号-1 电信业务审批[2006]字第258号函 京公网安备 11010802033920号 Copyright © 2005-2024 EEWORLD.com.cn, Inc. All rights reserved