学到老Never too old to learn分享 http://blog.sciencenet.cn/u/tangchangjie

博文

人生与算法 ---研教散记之20

已有 11491 次阅读 2010-9-9 15:45 |个人分类:科普札记|系统分类:人文社科|关键词:人生,,棋,,博弈,,选择,贪心算法,最优化,| 选择, 人生, 博弈, 最优化, 贪心算法

        人生与算法  ---- 研教散记之20(唐常杰)

      读了今天发表的迟菲博文 人生如棋和马臻博文 也说人生如棋为两篇好文喝彩。笔者曾在自然计算讲座PPT中,用这些生活现象解释那里的贪心算法和模拟退火算法;现在反过来,花几十分钟,把PPT中一些材料搬过来,为两位老师的论点补充弹药,活跃讨论气氛。
   
  
贪心使目光短浅。 四维时空中的人是多元化的,平常不贪心的人,在部分场合部分时间也可能有贪心的心理或行为。当贪心得以表现时,只顾眼前最大利益。计算机科学中的贪心算法(Greedy algorithm )模拟了这一基本思想,即每一步都追求评价函数最高值。
  
贪心算法容易实现。人贪心固然不好, 但计算机科学中贪心算法是好用的,开发起来比较简易,例如,常用于快速开发简单优化程序的或游戏程序。
  不贪心的人, 在生活中用会贪心算法吗?
  
会的,且看下面的两个例子。
例1 过公路十字路口 ,拟从A到C,在图1的 条件下,70%的人会用贪心算法,选走A-->B-->C的路线。通常,哪一条路径代价低(时间及其他资源),则先过该方向,先把看得见的实际利益(这里是时间)抢到手,这也是一条启发性知识。

 

                   图1过马路十字路口 ,拟从A到C

     但是,贪心算法不总是快,如马臻博文所说,人算不如天算,设若刚刚走到B, 大量救火车南北方向通行,且持续10分钟,欲速不达,后悔者会说,早知如此,何不当初选择路径A-->D-->C? 在晋升中级职称时,有人在选择走“教学系列”,还是“研究系列”方面踌躇徘徊,与此例相近。

 例2 求职,找工资高的单位。

             

                                        图2 求职,找工资高的单位

当事人做了一个(目光较短的)探测,发现工资西高东低,决定往西走,找一个极大值点。事实上,如果目光远一些,往东走,容忍一时的下降,两落两起后,可达到全局部的最优。此例有时候也称为为盲人爬山,手里面有一个一米多的手杖,探测梯度,往梯度大的方向走,因为探测棒太短,所以没有远见。
  
  
模拟退火算法是对贪心算法的批判  图2表明,如能坚持对东方的信念,允许偶尔(按一定概率)的失败,往东穿过低谷,达到一个更高山峰的脚下,最后登上全局优化点,这就是模拟退火算法的思想。在常出现局部收敛(或早熟)的应用场合,程序员会舍“贪心”而取“退火”。现实生活中,许多伟人坚持信念,几起几落,最后终于登上顶峰。

      小姐与丫环。戏曲中,穆桂英出场之前,先有一位武艺超群,容貌漂亮的丫环亮相,给剧中的杨宗保和剧外的观众一个悬念:丫环竟如此,小姐当如仙。这种用丫环衬托小姐的方法,也用在了计算机科学的论文中,设计了一个好的算法,常常用传统的算法作丫环来比较衬托;没有丫环,也要造一个,贪心算法最好造,常常扮演丫环角色;电器制造和销售中,也用丫环机型,根本没打算卖多少,让用户有个比较,衬托厂家利润大的“小姐机型”。

     坚持信念,也是算法。人生中,有时候受条件限制,无法预见长远,有时受环境所迫,没有多少可选择机会。此时,坚持信念,尽可能做好能作的每一步,就是胜利。严格地说起来,“尽可能做好能作的每一步”,用的就是贪心算法;这是 无贪婪之心,用贪心之法;虽然慢一点,但不乏成功者;在茫茫人海中,登上一个局部优化的山峰,也是成功。。
  有人说,40岁以前可跳几次槽,40岁以后不再跳槽,这就是工程上常用的两阶段爬山法,40岁以前模拟退火算法,旨在跳出局部优化点,寻找较高山峰下的坡面,40岁以后用贪心算法,“尽可能做好能作的每一步”,脚踏实地登山,不失为一个可参考的启发性知识。

相关博文(研究生全面成长系列)

小小突发事件和研究生责任感历练
作科研要学会承受失败- 
人生中的等待和等待的魅力
在统计意义上喜欢这样的学生
人生与算法

善对论文评审意见的宽严与长短
计算机改变了我们的学习方式和记忆观
路与人,以及科研选题----节日感怀(图&文)

 

 



http://blog.sciencenet.cn/blog-287179-361233.html

上一篇:名山、名师与高徒
下一篇:防止有意的抄袭,避免无意的雷同

35 武夷山 唐凌峰 章成志 赫英 梅珍生 吴雄斌 杨秀海 周春雷 黄富强 刘钢 杨正瓴 黄晓磊 金小伟 吕乃基 王启云 蔣勁松 王鲲翔 郭桅 侯成亚 赵福垚 刘晓瑭 齐霁 马利祥 李毅伟 丛远新 姜洪洲 王永林 刘广明 高绪仁 郑皎凌 郑永军 黄锦芳 曾新林 吕腾 ffy

该博文允许注册用户评论 请点击登录 评论 (18 个评论)

数据加载中...
扫一扫,分享此博文

Archiver|手机版|科学网 ( 京ICP备14006957 )

GMT+8, 2019-12-14 15:31

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部