• 2006-08-17

    囫囵吞枣学算法

    版权声明:转载时请以超链接形式标明文章原始出处和作者信息及本声明
    http://www.blogbus.com/dreamhead-logs/3075562.html

    因为《没有控制住》,我买了本《算法设计与分析基础》,目的就是为了对算法设计的方法有个基本认识。选择这本书的原因之一,就在于这本书的薄,正文三百多页。或许把三百页的书形容为薄有些过分,但对比于《算法导论》一千多页和《计算机程序设计艺术》的多卷本,你就知道三百页的书着实可以划到“薄”的行列中了。

    原本,我打算一边看一边做,就像去年看《自己动手写操作系统》一样。不同的是,我在这方面的基础显然要好于开发操作系统的基础,至少我学过数据结构的课程,加之我不知道以这种方式阅读自己能坚持多长时间,而且自己读书的目的是了解概貌,于是,我改变了策略,选择囫囵吞枣的方式,尽快的把书看完一遍,这样,可以达到自己最初的目的,如果有兴致,可以再对感兴趣的点进行细扣。或许这就是最近一年受研究风格的影响,先铺面,后找点:每当进入一个新的领域,前期总会找大量的相关领域资料进行阅读,快速建立知识体系,然后,选择适当的着手点,进行细致的研究。

    已经完成第一遍的阅读,这里记录一下阅读的心得。

    按照作者在前言中的说法,这本书最大的价值在于采用了一种全新的算法设计技术分类法。从前的书介绍算法会采用两种方案,一种是按问题分类,也就是常见的排序、查找、图等等,还有一种是按照算法设计技术,比如分而治之、动态规划、贪婪算法、回溯、分支界定等等。之前翻过一些算法书,基本上也没逃脱这个划分。读那些算法书总会给人一种见树木不见森林的感觉,或许通过学习,对某个算法可以比较了解,但算法为何如此设计依然云里雾里,也就是,没能理清算法设计的思路。这本书采用了一个全新的分类方法,把一些曾经不为人重视的设计策略提了出来,比如蛮力法(最直接解决问题)、减治法(减小问题规模)、变治法(把问题变为另外的问题)和时空权衡(时空互换),加上一些原有的设计技术如动态规划、贪婪算法等构成了新的分类方法,填补了算法和设计之间的鸿沟。这正是我最初注意到这本书的一个重要原因。

    一本好书,除了有好的内容,也要有好的表达。我说过,我曾经在读秀上读过这本书的前十几页。在这十几页中包含了一个求最大公约数(gcd)的例子,当然,是那个著名的欧几里德算法,连《计算机程序设计艺术》都用它开篇。这么简单的一个例子是不足以吸引人的,让我动心的是后面给出几个笨拙的gcd算法。为什么会是笨拙的算法?除非训练有素,否则,遇到问题的第一个解决方案常常会是很笨拙的,这恰恰是我遇到的问题。事实上,这样的表达方式在后面不断出现,作者不会像先知一样凭空给出一个设计精良的算法,而常常选择一个看起来很笨的方法进行介绍,然后逐步引出后面的算法,这更符合一个人的思考过程。我喜欢这种不把读者当白痴的介绍方式。不过,有些部分我读起来还是比较吃力的,比如第10章关于P、NP和NP完全问题,应该是自己在这方面的底子比较薄的原因吧!看算法时可以享受阅读的乐趣,着实不易。

    看中文版的好处之一就是快,至少我现在的英语阅读能力还远远无法与中文相提并论。在我看来,这本书的翻译还是比较流畅的,至少在阅读过程中,我很少因为让人无法理解的中文而被打断思路。当然,再好的译本也有一些瑕疵,我几乎每章都能找到一些小问题,我已经把这些问题提到了china-pub上。译者不错,对我找到的这些问题给予了积极的响应,不过,我也因此得寸进尺,发现了更多的问题。来自译者的一个消息是,他正在翻译第二版,不知道会有多少变化。喜欢对中文版吹毛求疵的人,可以选择这本书的影印版

    如果你和我有同样的需求,这本书是个不错的起点。

    分享到:
    引用地址: