博文

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

已有 13679 次阅读 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岁以后用贪心算法，“尽可能做好能作的每一步”，脚踏实地登山，不失为一个可参考的启发性知识。