转载

图灵访谈：《算法的乐趣》作者王晓华：“玩”过就是收获（图灵访谈）

王晓华是一位热衷于算法研究的程序员，他是CSDN算法专栏的超人气博主，也是《算法的乐趣》一书的作者。他2005年毕业于华中科技大学，目前在中兴通讯上海研发中心从事光纤接入网通讯设备开发，担任EPON（以太网无源光网络）业务软件开发经理，参与开发的PON设备在全球部署过亿线，为数亿家庭提供宽带接入服务。

王晓华最大的乐趣就是用程序解决生活中的问题。当年为了方便使用Visual Studio 6.0开发软件，他特意编写了一个tabbar插件，并随后开源了这个软件。为了文档安全，他开发了一个基于layerFSD技术的透明文件加密系统，在朋友圈内广为流传。后来他在使用Source Insight软件的时候，又以外挂的形式为Source Insight开发了TabSiPlus插件，受到了很多程序员朋友的欢迎。

问：你从什么时候开始迷上了算法？

这个要从上大学时候说起了。像我这样的懒人觉得拼音输入法太繁琐，于是就去学“表形码”（当然，因为笨的原因，现在还在用拼音输入法）。资深一点的游戏玩家都还记得，那个时候为了玩中文DOS游戏，很多人都装了UCDOS中文环境，UCDOS没有表形码，但是支持通过码表文件增加自定义输入法。我研究了Windows上的表形码码表文件（老师给的，适用于Windows 3.x版本）和UCDOS码表文件的格式，发现二者有一定的相似性：都是文本文件，有固定的格式，每一行由一组编码和一个字或词组成一个编码对。二者的区别仅仅在于一个文件是编码在前，对应的字或词在后面，另一个刚好相反，字或词在前，对应的编码在后面。码表文件有十几万行，手工修改是不可能了，刚好当时在上C语言课，就决定写个程序来做这个事情。

第一次运行我写的程序，十几秒钟都没有结束，我觉得程序挂了，于是我就“Ctrl+Break”了，因为我之前写的C语言作业，从来没有哪个程序运行时间超过1秒钟的。但是分析代码又觉得没有问题，看了遗留在磁盘上的码表文件，发现转换了几千行，并且内容是对的。于是再次运行程序，等了2－3分钟，程序结束了。我急不可待地将得到的码表文件导入UCDOS，发现可以用，当时就感觉非常有成就感。这是我第一次为解决一个实际的问题编写算法，尽管当时还没有算法、软件的概念，但是隐隐约约就觉得这东西有用，不是只用于完成作业，还可以解决实际的问题。后来就是接触更多的有用算法以及各种算法竞赛，一直到现在，写个程序解决问题几乎成了一种习惯。

问：《算法的乐趣》这本书在内容的设计上和其他同类型的书相比，最大的特点是什么？

在我学习算法的过程中，兴趣是最大的推动力，兴趣来自于我觉得这东西能解决问题，对自己有用。但是在我写《算法专栏》博客的时候，网上能看到的博客都是对各种竞赛题目的解答，这些竞赛题目虽然有趣，但是对很多人来说依然抽象，与程序员们日常的工作关系不大，难以提起大多数人的兴趣来学习。于是我就想，如过能通过一些现实中普遍应用的算法做切入点，通过这些例子让大家觉得算法是有用的，并通过这个来吸引大家关注算法，学习算法，从而达到提高能力的作用，岂不是个很好的主意？

在策划《算法的乐趣》这本书的时候，我依然沿用了这种思想。选取的例子都是大家生活中没有在意，但是却处处都会遇到的算法，希望以此来“鼓动”起大家学习算法的兴趣。所以本书只用了很少的章节介绍算法的本质和设计算法的常用思想，把主要内容放在介绍这些生活中的趣味算法的解决过程，并在这个过程中给出各种算法设计中常用的模式、技巧和思想，提醒读者在阅读过程中不仅关注本题的解决，更要关注解决这个问题过程背后的思想，既培养了兴趣，又提高了解决问题的能力。

问：算法学习是一条并不简单的路，请问你是否有其他优秀的算法书愿意推荐给读者们？阅读这些书的顺序和注意事项是什么？

就我的经验而言，在计算机上学习算法首先需要熟悉编程语言和数据结构，关于编程语言和数据结构有很多经典的书籍，我就不多介绍了。但就算法而言，我看过的书有Cormen的《算法导论》、Knuth的《计算机程序设计艺术》、Weiss的《数据结构与算法分析》、Levitin的《算法设计与分析基础》、Kleigberg的《算法设计》等等。想参加算法竞赛的同学可以参考刘汝佳等人编写的《算法艺术与信息学竞赛》，以及《ACM国际大学生程序设计竞赛题解》。因为时间过去太久了，已经不记得看这些书的顺序了，只记得最早看的是《算法导论》，关于顺序实在没有什么经验可谈。

至于如何读这些算法的经典书籍，我倒是有一些经验和大家分享。不管哪一本书，都不要泛泛地看一遍就觉得看懂了，而是要把书中的每一个例子算法都用程序写出来，这样才能留下深刻的印象。如果遇到看不懂的地方，不要停下来，跳过去看其他算法，过几天在回头来看，如果还看不懂就再过几天再回头来看。千万不要在一个地方停下来，否则你很可能就此失去兴趣，恐怕永远也看不完这本书了。

问：有哪些学习算法的网站值得推荐？

有很多游戏开发相关的算法介绍：

http://www.gamedev.net

http://theory.stanford.edu/~amitp/GameProgramming

http://www.gamasutra.com

http://www.sudoku.com

俄罗斯方块游戏的算法网站：

http://gforge.inria.fr/projects/mdptetris http://colinfahey.com/tetris/tetris.html

leetcode，最近很火的算法网站：

http://www.leetcode.com

Topcoder，也很经典，每周都有竞赛，有奖金的：

http://community.topcoder.com/tc

晋中教育网的“信息学竞赛辅导”：

http://www.jzsyz.jzedu.cn/xxjs/suanfa/index.html

很多大学也有自己的竞赛题库，比如：

北大： http://poj.org/

杭电： http://acm.hdu.edu.cn/

华中科技大学： http://acm.hust.edu.cn/vjudge/toIndex.action

问：很多人都认为“学习算法很难”，你是否知道有哪些方法可以降低学习算法的难度？

许多算法是有难度的，理论很复杂，不容易理解和掌握，这是客观存在的现实。但是我们可以通过提高自身分析问题和解决问题的能力来相对地降低学习难度。从基础来讲，要深入理解数据结构，至少要非常熟练地掌握一种排序算法，各种线性表的插入、删除算法，树的遍历和插入、删除算法，图的遍历算法等等。然后要多学习，掌握一些常见问题的解决模式，比如穷举算法如何应用，动态规划算法如何应用等等。最后要勤思考，对应已经掌握并解决的算法，要想想为什么用这种方法解决，有没有其他方法，类似的问题怎么办，提高举一反三的能力。

问：想学好计算机算法，是否需要重新学数学?

这个问题无法回避，数学的重要性不在于算法中用了哪些公式或数学原理，其重要性在于一种思维方式的培养。当我们遇到一个新的问题的时候，通常有两种解决问题的方式，一种方式是创造一种新的方法来解决这个问题，另一种方式是将新问题分解、转化成已知问题，然后用已知的方法解决这个问题。这两种方式都很需要抽象思维能力，现实生活中很少有机会锻炼抽象思维能力，而学习数学是一种很好地培养这种能力的方法。我强调数学学习的目的不是说要学好算法就必需成为数学大咖，而是通过学习数学促进抽象思维能力的提高。

问：背算法和理解算法是一般算法学习者都能够做到的，但是很多人会在设计算法的过程中遇到困难，请问算法设计为什么那么难？如何能完成从“输入”到“输出”的转化？

参加算法竞赛其实是一件很痛苦的事情，要经过大量的训练，很多人会选择背一些算法或整理一些算法模板，到时候可以直接套用。在理解算法的基础上熟记一些经典的算法实现其实也是一件无可厚非的事情，我上学的时候也参加过一些比赛，通常在比赛之前也会突击训练一两个月，并背很多东西，基本上也是事后一个月就全忘了。

比赛的题目一般都有特定的套路，但是现实生活中的算法往往就事而论，有可能只有你遇到过，没有现成的经验，需要自己从无到有来解决问题。我在书中强调算法设计有三个方面：模型的建立、演化算法和输入、输出的转换。这三个方面中模型的建立是关键，很多情况下，模型建好了，演化算法和输入、输出的转换就水到渠成。

建立模型的基础是数据结构。当一个问题的数据存在先进先出的特性时，你要想到队列。当一个问题的数据需要频繁查找操作时，你要想到有序表、hash、map。当一个问题的数据需要频繁的插入、删除操作时，你要想到链表。当一个问题中的数据包含父子关系时，你要想到树。当一个问题中的数据中既有节点又有路径什么的，你要想到图。这些都和使用数据结构的经验有关，只要多练习就能掌握。

建立模型还需要抽象的逻辑思维能力，简单地说，就是运用抽象的逻辑思维，抓住问题的主要因素，忽略次要因素，建立问题的框架。算法设计之难体现在思维方式的转换和模型的建立，前面说过，这需要有抽象思维能力，缺乏这种能力，连问题都很难想明白，更不用说设计解决问题的算法了。幸运的是这种能力是可以培养的，学好数学，多研究一些算法，积累些经验，都是很好的提高抽象思维能力的方法。

问：算法在大数据领域有着广泛的应用，《算法的乐趣》的推荐者王益和黄鑫也都是机器学习方面的专家，请问编程算法和数据挖掘涉及的算法有什么区别和联系吗？

编程算法应该只是算法的一种表达形式，我们还可以用表格或流程图来表达算法。数据挖掘领域涉及的算法和其他领域的算法并无本质的区别，只是问题域不同。数据挖掘和机器学习常用的方法，比如决策树、贝叶斯学习、神经网络、遗传算法等等，在其他领域也都是有应用的。神经网络、遗传算法作为启发性搜索算法在人工智能和最优化求解领域也得到了广泛应用，本书中就介绍了遗传算法，只不过所举的例子是用来解决0-1背包问题，有点“大材小用”。贝叶斯学习在一些电子邮件应用程序中也有应用，主要用于垃圾邮件的识别。在人工智能领域或各种专家系统中，决策树算法也是常用算法。各种算法之间的联系还是很普遍的，在不同的领域扮演着不同的角色，本质上没有区别。

问：在日常生活中，我们有机会见到越来越多的推荐算法，请问你对现在流行的推荐算法是否有一些研究？要做好推荐算法，有哪些问题需要特别注意？

确实是这样，我曾经想买一个佳能镜头，于是用了一下百度，想了解几种镜头的评价，结果一连几天，只要登录京东或淘宝，首页都会给我推荐与数码相机有关的配件或镜头信息。

因为工作领域的原因，我对推荐算法没有深入的研究，这种算法应该主要是建立在大数据上的数据分类、筛选和过滤吧。不过就我对算法的理解来说，目前的推荐算法还是有改进的余地的，比如要能区分同一台计算机的不同使用者，不要在我用电脑的时候向我推荐女式内衣和化妆品，那是我老婆关注的东西。

问：除了书中介绍的很多经典算法，你是否在工作或生活中发现其他让您印象深刻的算法？

应该说，在我的工作和生活中也是处处都有算法。说到网络协议，TCP协议中的“滑动窗口算法”也是很经典的算法。路由器和交换机中为了避免出现端口环路，都会使用最小生成树算法。在接入网设备中，通常语音报文的优先级高于视频报文，视频报文的优先级又高于一般的数据报文，当一大波各种报文来临时，设备如何处理？这个算法也很经典，就是用多个队列加上一个调度算法，简单说就是六个字：分分类，排排队。

随着宽带的普及，现在几乎家家都有路由器，很多人都会在路由器上给各个端口配置带宽，这就会用到带宽分配算法，令牌算法和Max-Min Fairness带宽分配算法都是经典的带宽分配算法。网络传输的数据报文出了错码怎么办？那就要纠错，Reed-Solomon编码和解码算法就是这样的经典纠错算法，除此之外，Reed-Solomon编码和解码算法还用于光盘、磁盘的数据纠错。