图灵社区的电子书没有采用专有客 户端，您可以在任意设备上，用自 己喜欢的浏览器和PDF阅读器进行 阅读。 但您购买的电子书仅供您个人使用， 未经授权，不得进行传播。 我们愿意相信读者具有这样的良知 和觉悟，与我们共同保护知识产权。 如果购买者有侵权行为，我们可能 对该用户实施包括但不限于关闭该 帐号等维权措施，并可能追究法律 责任。 （2017.1重印） 内 容 提 要 本书从一系列有趣的生活实例出发，全面介绍了构造算法的基础方法及其广泛应用，生动地展现了算 法的趣味性和实用性。全书分为两个部分，第一部分介绍了算法的概念、常用的算法结构以及实现方法， 第二部分介绍了算法在各个领域的应用，如物理实验、计算机图形学、数字音频处理等。其中，既有各种 大名鼎鼎的算法，如神经网络、遗传算法、离散傅里叶变换算法及各种插值算法，也有不起眼的排序和概 率计算算法。讲解浅显易懂而不失深度和严谨，对程序员有很大的启发意义。书中所有的示例都与生活息 息相关，淋漓尽致地展现了算法解决问题的本质，让你爱上算法，乐在其中。 本书适合软件开发人员、编程和算法爱好者以及计算机专业的学生阅读。 ◆ 著 王晓华 责任编辑 王军花 执行编辑 张 霞 责任印制 杨林杰 ◆ 人民邮电出版社出版发行 北京市丰台区成寿寺路11号 邮编 100164 网址 http://www.ptpress.com.cn 北京 电子邮件 [email protected] 印刷 ◆ 开本：800×1000 1/16 印张：26.25 字数：614千字 印数：13 801 — 14 800册 2015年 4 月第 1 版 2017年 1 月北京第 7 次印刷 定价：79.00元 读者服务热线：(010)51095186转600 印装质量热线：(010)81055316 反盗版热线：(010)81055315 广告经营许可证：京东工商广字第 8052 号 前 言 1 1 序 一 2 3 读《算法的乐趣》的乐趣超出了我的预料。 说到算法，大部分计算机专业的同学的第一反应估计是MIT出版社的经典教材《算法导论》 （Introduction to Algorithms）。这是一本由浅入深的好书，堪称“神书”——别看书挺厚，但是对 初学者来说很难弄懂的问题也娓娓道来，让人看一遍就明白；而且作者用最简单的英语词汇和句 法写书，以至于世界各地的学生们，不需要英语很好，即可读懂原版。只是看完这本大部头之后， 总有一些意犹未尽的感觉——对我们日常生活中常见的比如音乐播放器里以及电子游戏里的算 法并没有太多介绍。而这些正是《算法的乐趣》中主要的部分。 4 在Amazon上，另外两本排名靠前的经典算法教材是Jon Kleinberg的《算法设计》（Algorithm Design）和Steven S. Skiena的《算法设计手册》 （The Algorithm Design Manual）。这两本出自名家 之手的教材和很多教材一样，按照算法的类型或者背后的设计思路来组织内容。这是教材应该做 的，“授人以鱼不如授人以渔”，传授思路而不是算法本身是教材的写作目的。可是算法最有意 思的地方首先在于算法本身，因为算法是为了解决实际问题而设计的，所以让大家认识到算法奥 妙的自然顺序应该是先展示有趣的问题，再展示优雅的算法，最后归纳设计思路。而这正是《算 法的乐趣》吸引人的地方。 6 说到乐趣，总让我想起我学习和使用数学知识的经历。虽然我的学位是关于统计机器学习的， 而且毕业后一直从事相关工作，但是我从小学一年级到博士第三年都对数学毫无兴趣，因为学校 的老师和数学成绩好的同学都说不明白数学的用处，以至于我一直以为数学的作用只是锻炼和展 示自己的聪明，博得老师的表扬，成为陈景润那样为国争光的英雄。而这些对我实在没有吸引力， 而且我认为恐怕对绝大部分学生都没什么吸引力。 我认识到数学的价值，是因为在博士第三年把研究方向换到了统计机器学习。在读教材的时 候，我曾想验证“数学无用”，所以费尽心力地试图写一个程序来判断一个64×64像素的图片里 到底是数字“1”还是数字“9”，却发现无论如何也很难写一个有效的程序；可是利用教材里的 数学知识却能设计和“训练”一个数学模型，准确地识别任意字符。因为体会到了数学的用处， 我兴奋地用了一年的时间复习大学本科的数学课程，然后才读懂了人工智能的专业教材和论文。 此后才有所创新，发表论文，到博士毕业。这整个过程用了三年，而效果超过了之前19年数学教 育的效果。 5 7 8 9 10 11 12 2 序 一 在这个过程中，我自然而然地开始注意数学知识的前因（比如为什么人们会关注长度、面积， 怎么会有人考虑勾股定理这样的规律）以及后果（今天的数学知识能给物理学和机器智能带来什 么样的帮助），也开始归纳和了解各种数学系统背后的规律，能体会哥德尔定理阐述的意思。当 然，也破除了“数学是各种科学之母”之类的迷信，数学当然不是“科学之母”，而是“科学之 子”，是先有物理学、力学和天文学，才有的数学；先有应用场景后有工具，先有探索后有归纳。 算法也是如此。先有工程问题需要解决，算法是解法，设计算法是寻求解法。虽然算法作为 一门科学是归纳寻求解法的思路，但学习这种归纳法的前提是能体会各种具体算法的用处和效 果。意识到这一点，自然也就破除了诸如“学好数学才能学好算法”之类的迷信。而把算法解决 的各种有趣问题罗列出来，把算法的可爱之处展示给愿意发现和体会生活中点滴乐趣的读者们， 正是《算法的乐趣》在技术价值之外的一层社会价值。 十年前，当我们坐在课堂里学习算法的时候，我们学到的是如何用人脑寻求解法，然后把解 法写成程序，让计算机照着执行去解决问题。这是“经典算法”。最近十几年，随着Internet产业 的兴起，Internet服务在不断取代原来由人提供的服务，这就要求机器拥有一定程度上能取代人的 “智能”。在搜索引擎、推荐系统和广告系统等各个领域里，类似上述“识别数字”的问题越来 越多，而人工智能和机器学习的应用也越来越深入我们的生活。机器学习算法的设计目标和“经 典算法”不同——不是让人来想解法，而是让计算机从数据归纳知识——有了这些知识，计算机 就能自己寻求解法。 虽然经典算法和机器学习算法之间的差别大得如同一场革命，但是由经典而入机器学习的过 程却是自然而然的。比如《算法的乐趣》中介绍的曲线拟合问题，就是supervised learning（有监 督学习），而音乐播放器里常用的傅里叶变换和其他时域频域变换则是unsupervised learning（无 监督学习）的技术基础，棋类游戏算法是博弈论和reinforcement learning（强化学习）的经典例子。 我常见有朋友从读数学教材开始探索机器学习和人工智能算法，也常看到有人不堪忍受长时间缺 乏乐趣的探索以至于半途而废。如果是这样，也许不如从《算法的乐趣》开始这个探索过程。 我曾经以为从乐趣出发阐述算法的书会从西方发芽，没想到先看到了一本中文书。这真超出 了我的预料。 王益 LinkedIn高级主任分析师 图灵社区会员 ChenyangGao([email protected]) 专享 尊重版权 前 言 1 1 序 二 2 3 当图灵出版社的编辑找到我希望我为这本书写个序的时候，我和旁边的同事调侃了一句：又 一本简版的《算法导论》要诞生了。但是我还是下载了附件阅读了这本书，当翻到目录的时候， 我的兴趣就被燃起来了，转头和同事说，也许这是一本不错的书。 程序员到底需不需要学习算法？这个问题被争论的次数绝对不亚于“Java是不是最好的语 言”“VIM和Emacs谁是最好的编辑器”“程序员是不是需要学习数学”。为了避免陷入这样的争论 里，我们先对“算法”一词做个转换定义，什么是算法？下面我举几个我亲身经历的例子。 有一次我们发布了一个APP，在注册时要求用户输入自己的真实姓名，但是粗心的工程师忘 记了要求用户填写自己的性别，更可怜的是在欢迎页上面明晃晃地写着“欢迎XXX先生注册XX 网”，可是应用已经发布到了App Store，到底怎么办？有一位工程师提出了一个办法，我们根据 已有的用户姓名和性别作为训练集，来预测新用户到底是男还是女，为了让这个错误尽快得到修 复，我们使用了最简单的朴素贝叶斯分类算法，最终测试集上的预测准确率达到93%，也就是说 我们解决了93%用户的体验问题。我把这类算法称为专业类算法，也就是招聘网站上算法工程师 要求的算法，例如图像处理工程师、数据挖掘工程师等。 有一次我们有一个相似性搜索的需求，数据量不大，只有几万条的数据记录，没有必要用ES 这样的搜索引擎。例如输入“长沙市”， 也希望可以找到“我爱湖南长沙”“沙市小吃”等，且 不说这个需求是否合理，我们单纯来讨论这个问题的解决方案。工程师实现的第一版是将所有字 的组合全部列举出来，然后在数据库里做like操作，性能无法接受。于是我们提出了另一种解决 方案：将数据库中的每个词都拆成单字，做成集合，保存在缓存中。接下来只需要对集合做交集 操作，以字为单位计算词与词之间的相似性，性能问题一下就解决了。这种解题思路在《编程珠 玑》中屡见不鲜，这不足以称为具体的算法，几乎都是在梳理我们的逻辑，训练我们解决问题的 能力，我把这类算法称为逻辑类算法，或者技巧类算法。 还有一次，我们有个需求是帮助用户做旅游的行程规划，其中的情况比较复杂，因为除了地 理位置之外，还需要包含目的地的过往用户评价、所需耗时、不同城市的住宿花费等。但是如果 我们仔细分析，可以基于产品设计去拆分问题。在在线部分，我们可以去使用基于路程的最短图 路径算法，或者基于价格的贪心算法，也可以在综合排序处为用户选择使用了变形加权的最短图 路径算法。在离线部分，由于图的节点和边都较少，可以使用穷举法来为用户找到几种不同类型 的最优解。这些算法都是在《算法导论》和《数据结构》中有着详细讨论的算法，书中的每一个 4 5 6 7 8 9 10 11 12 2 序 二 算法和数据结构都是作者多年来抽象总结出的通用思路，我称之为通用类算法。 再说一个最基本的，我们做一个网站允许用户发布状态，在高峰期并发量太大，数据库不堪 重负，所以我们需要将用户的插入记录先存入到消息队列中，保证用户的正常使用，然后再落地 到MySQL数据库中。大家都会想到选择队列这样一种先入先出的数据结构，这也属于一种算法。 通过上面的几个例子，你会不会觉得你的身边处处都是算法？那么到底什么是算法？我们看 看标准的定义：能够对一定规范的输入，在有限时间内获得所要求的输出的一系列指令都叫作算 法。这个定义太抽象了，让我们简单来说，算