[转载]用算法解决现实问题—访图灵奖获得者罗伯特·塔扬教授
罗伯特·塔扬（Robert Tarjan）教授是世界知名计算机学家，他的研究领域主要包括图论、算法和数据结构设计。罗伯特教授是许多图论算法的发明者，比如树中最近共同祖先离线算法、Splay trees、Fibonacci heaps、平面性检测（Planarity testing）等。1986年，他与John Hopcroft因为在算法及数据结构的设计和分析中所取得的成果而荣获图灵奖。他于1982年获得首届奈望林纳奖（Nevanlinna Prize），现为美国科学院院士、美国计算机协会（ACM）院士、美国普林斯顿大学教授。
2012年4月12日，罗伯特·塔扬教授到访中国，会见了清华大学副校长袁驷教授，并做客“清华海外名师讲堂”第119讲，在清华大学信息技术大楼多功能厅，他讲述了《搜索树之谜》的特邀报告。同日，在惠普中国研究院里，罗伯特·塔扬教授与王敏院长和惠普中国研究院的研究员们齐聚一堂，全面解释了他对算法的睿智见解。
<老骥伏枥 志在千里>
Q：您的一生取得了非凡的成就，在您看来，这些成就是天赋还是机遇？ Robert：我还是先做个自我介绍吧。我在13岁读初中的时候，美国掀起了数学教学改革试验的浪潮，也就是以更加形式化的方式来传授数学这门课程。非常不幸的是，新运动失败了。但我恰恰成为新数学教学改革的受益者之一，也因此出现了一大批我这样的人。我对数学有很浓的兴趣，如果你们看过我的资料，会知道我经常读一些科幻小说。在孩童时期，我的梦想就是成为第一个登上火星的人。我当时非常喜欢读的一本杂志就是《SCIENTIFIC AMERICAN（环球科学）》。此外，当时我对天文学也非常感兴趣，这也成为我日后非常重视数学学习的原因。读到高中的时候，我在暑假期间参加了某个研究中心的活动，有机会接触了当时最老式的计算机，那时的计算机还是打孔式的，后来又有机会使用IBM计算机，和最初的编程语言。所以在很小的时候，我就有机会和计算机打交道。当时我就已经对编程产生了浓厚的兴趣。到了大学本科的时候，我在加州理工大学学习。当时我主修数学，而我几乎选修了所有有关计算机科学方面的课程。读博士时，我去了斯坦福大学，选择的专业方向是计算机科学，也正是在那里，我遇见了我的导师Donald Knuth。当我本科毕业时，我选择的研究方向其实是人工智能。但是，那时候的人工智能还处于早期阶段，整个研究领域都是非常模糊的状态。在Donald Knuth的指导之下，我最后锁定了我的研究领域是计算机算法，主攻数据结构这一方向。从那个时候一直到现在，我都坚持了这个研究方向。
接下来回答你刚才提出的问题。天赋当然是重要的，但还有一个非常重要的成功元素，那就是你要在合适的时间，出现在合适的地方。回顾我的一生，我就是在合适的时机，选择了适合我的研究方向。对于计算机算法而言，我是把它作为数学对象来研究，来对待的。从这个角度出发，去开发计算机的算法，同时把它用于一些实际问题中。我有几位非常好的导师，他们给我提出了一些非常好的课题。还有一个成功的元素我认为应该是毅力，以及坚持不懈的学习和培训，不管你的天赋有多高，我认为还需要努力地工作、努力地学习。如果你研究的领域是和数学相关的，研究过程中失败是不可避免的，你可能会觉得懊恼，甚至会用头撞墙，但是你一定要坚持下去。如果一个问题总是找不到答案，你可以换一个课题去研究，然后过一段时间再来攻克这个难题。不管你有多么聪明，多么有天赋，我认为毅力，以及不断的学习都是非常重要的。谈到计算机科学，我认为计算机科学这个领域充满着机会。回顾计算机科学的历史，已经有75年了。这个领域让人非常的惊喜，因为它不断地给我们提供新的机会。今年是阿兰.麦席森.图灵诞辰百年，各地举行了盛大的庆典，大家以各种方式来纪念他。图灵是在20世纪30年代，也就是二战期间，提出了计算机的概念和想法，那时的计算机，还处于非常简单的阶段。
Q：您现在的梦想是什么呢？ Robert：非常感谢你这么问。我有幸来到中国惠普研究院，看到现在搞计算机科学的人都很年轻。而且我也去过很多创业型的公司，那里的人也都很年轻。计算机科学这个研究领域还很年轻，不过我已经老了。因此，我现在唯一的梦想，就是尽量多的去攻克那些现实的技术课题。我希望在我有生之年，只要还可以在智力上跟得上那些年轻人，我就一直持续的工作和研究下去。
算法是计算机领域的管道工
Q：1986年的时候，您跟您的合作者赢得了图灵奖，这是一个非常伟大的成就。对于这个成就，现在看来，它产生了很大的影响。那么，对人类的生产与生活带来了哪些改变？ Robert：当时之所以获得了图灵奖，是因为算法以及数据结构方面的成就。我认为谈到计算机算法和数据结构，它其实相当于计算机领域中“管道工”的角色。正是有了这些算法和数据结构，我们才可以把一些看似不可能找到解决方案的问题解决，而且能够让计算机的运转速度更快。如果说它对于人类的生产力、生活带来了怎样的影响，我无法具体的谈及某一个领域，它遍布了计算机行业整个领域。你看，不管是数据库还是电脑系统中，基本上都有算法以及数据结构的存在，它是一个很普遍的东西。谈到这个成就本身，我想再补充一点，它被很好地运用到了目前的教育体系中。为什么这么说呢？现在很多的理论都用到了课堂的教材中。学生们可以在课堂上学到这些，比如说对于一个课题，如何找到并研发出它的解决方案，然后又把它从一个学术的东西用到实践当中。我想这能帮助学生们学习到一些新的点子和思路。
Q：在大多数人眼里，您所从事的这项工作又枯燥又没有乐趣，但是您总能创造出新的办法或者发现新的结构，我不知道影响您的动力是什么？乐趣又是什么？ Robert：在我看来，数学是一件非常美丽的事物。数学可以运用到计算机科学中，而计算机科学又很好地帮助人们解决了现实生活的一些问题。Donald Knuth的名著《计算机程序设计艺术》将程序设计称为艺术，算法实际上跟建筑的艺术是一样的，只不过它的这种结构是你看不见的，是存在于人们的头脑中的，是大脑编成的各种各样的美丽的建筑。这让我想起了我弟弟，非常有意思，他曾经是国际象棋大师。虽然他最后放弃了这个职业，但是我想说，可能在我的家族中，数学就是一种DNA，它真的是一件美丽的事物。我喜欢很多数学游戏。儿童时期，除了对天文学感兴趣之外，我还喜欢一些棋盘游戏，比如Martin Gardner的游戏（《环球科学》中的数学游戏专栏），还有一些拼图游戏。
寻找课题的方向 Q：您是如何找到研究课题的方向的？ Robert：我的研究生涯非常长，我的建议是，你可以尝试去解决那些基础性的问题，而且是能够有一些具体应用的问题。大家可能先有一个具体的问题，然后要可以从中看到，或抽象出一个用数学这个工具能够解决的问题。所以我对一个课题的研究通常都要花很长时间，有的甚至几年。有时这个研究做几年，然后再隔一段时间，之后回头再去研究。这样，我们才可以把自己称为一个解决问题的人。通过解决一些基础性的问题，我从多年的科研中总结提炼出了一些理论和方法。所以，我积累了很多具体的计算机算法技巧，还有分析方面的一些技巧。在这里我必须说，和产业界保持联系是非常好的一件事情，因为如果你能够为他们具体的问题找到方案的话，回报也会很好。这也会是让你持续把这件事情做下去的原因。
Q：那么刚才谈到人工智能，上世纪不大成熟，但是到了这个世纪您还有兴趣再继续对人工智能进行研究吗？ Robert：我现在年纪太大了，没有足够的时间再去重新学习一个新的领域，但我还在持续关注人工智能这个领域。我有一些惠普的同事，他们正在试图找到一些计算数学方面的方法，还有统计学方面的方法，去更好的完善计算机学习的能力。我相信随着数学的进步，随着计算机本身技术的进步，人们在人工智能方面真正能够迈出有意义的一步。再补充一点，我还有一个梦想，如果有下辈子，我会研究人的意识，人的思想是怎么产生的。如果能够研究清楚这个课题的话，人工智能也就解决了。事实上我特别想研究人的意识、思维到底是怎么产生的。我觉得可能机器可以帮助人们解决某些问题，但是最根本的问题是，意识是怎么产生的。大家对这个问题好像比较有争议。研究这个问题我也是门外汉，因为我既不是神经学科方面的专家，也不是哲学家。
Q：我想问一下您和您的导师在相识之后，进行了一些共同的研究，那么在这个研究过程中，发生了哪些比较有趣的事？ Robert：我到斯坦福攻读博士学位的时候，第一年就全部修完了博士学位所需要的基本学分，通常这些学分需要两年才能赚到。当时我学的是图形算法，我和我的博士导师（Donald Knuth）交换了很多观点。在我第一年学期结束的夏季，我遇见了跟我一起获奖的John Hopcroft教授（康奈尔大学教授，当时在斯坦福进行学术休假）。所以你看，在合适的时间，出现在合适的地点是多么的关键，斯坦福的环境确实太棒了。当时我选择的一门叫做符号编程语言的课，我们要试图解决的一个问题是：如何把一个图形内嵌到一个平面中。这实际上是一个数学问题，让我举一个例子：上面的3个符号中，W代表水塔，G代表天然气塔，E就是电塔，下面是三所房子，我们现在要做的是：把水、电、气分别都接到这些房子里，但是你不能让这些线有任何交叉。这就是要解决的数学问题。这是小时候我们无法解决的数学难题，关键是图的可平面性检测。电路板布线有时也会遇到这样的问题。
在研究的过程中，我参考了很多的文献，我发现其中一个算法是可以解决这个问题的，就把它用到这儿了。但是，当时那个算法做起来比较慢，解决简单的问题可以，但是复杂的就不行了。最后我们终于想出了一个办法，能够在线性时间内，解决可平面性检测。正是因为这个研究成果，让我们获得了图灵奖。
Q：您刚才提到在研究过程中，也遇到很多挫折，有时候想用自己的头去撞墙，那么在这样一个过程中，您是怎么样鼓励自己坚持把这条路走下来的？ Robert：它总是先苦后甜的。道路越曲折，那你获得成功之后的喜悦就会越大，而且在失败的过程中能学到很多的东西。我经历了很多曲折的过程，也研究了各种各样的问题。尽管计算机科学是一个年轻的科学，有很多人在其中的时间并不长。但我发现计算机科学研究方面也需要存在系统性。要解决一个问题，就要找到一个比较容易的方式，也许这个方式是最容易的，但却并不是最好的，最简单的。所以有时候，对一些已经解决的问题，我们只要回头，就可以找到更加简单，而且更加行之有效的方案。因此，我认为关键点就是一定要坚持简单、高效。因为如果你的方法不够简单的话，大家就不会想去用了。我的建议就是，千万不要害羞，一定要大胆地尝试。科研是没有边界的，要勇于去打破常规旧俗，而且我想再一次强调，一定要有毅力，而且要努力，勤奋地工作。
用算法提高业务效率 Q：您现在在惠普研究院从事哪些领域的研究？有没有一些可以介绍的成果？ Robert：我在惠普担任的高级院士是研究方面最高的头衔，我并不做任何管理的工作，惠普交给我做的唯一工作就是算法研究，我可以自由选择我的具体研究问题。
目前我们在做的一项工作是，利用算法提高业务流程的效率。现在人们经常谈到业务流程的自动化，而我现在就在与惠普负责运营方面的人员合作，希望借由算法来提高惠普内部的流程效率，从而帮助惠普内部提高效率，降低成本。如果能够在惠普内部用好的话，也许可以把它商品化成为一种产品或者一种服务。
我举个例子，一个具体在做的项目叫做人力优化。惠普收购了一家服务公司叫EDS，经常会承接很多项目。对于一个项目来说，需要有各种技能的人，而每个人又有不同的技能。已存在标准算法是：每个技能我们可以用数学的方法给它一个量化，根据这些量化数字，再做人员和项目的匹配。但是我们发现它的效果并不是很好，我们希望能够改善这个算法，能够得到更好的匹配，这样的话，就可以实现人力的优化。
我再举一个我和惠普中国研究院的例子。王敏院长以及这里的同事在研究的一个课题是网络。你们也知道，惠普收购了3COM，其中的H3C在中国是一家做得比较大的网络公司。我们正在一起合作，关注如何把算法运用于网络技术。
作为惠普的资深科学家，我也会经常去指导各地惠普研究院的技术研究方向；同时我也辅导一些年轻的研究员，担当团队技术领袖的角色。
Q：随着IT行业的发展，是否意味着企业的研究工作也要产生变化，未来的研究趋势是怎样的？此外在教育方面，您觉得应该如何培养孩子对数学着迷？ Robert：作为个人来说，时间是有限的，不可能去研究所有时髦的东西。我是做基础研究的，不管IT界怎么发展，摩尔定律仍然在发挥作用：计算机的速度、芯片的速度，仍然是每18个月要翻一翻；那么存储也要不断的增加，还有网络通讯的力量也会不断加大。所以你会看到IT的趋势和方向并没有放缓，而是在加速在往前走。但是对于研究来说，计算机本身运转的速度并不是最重要的，随着移动设备越来越多的出现，还有更多的空间，开发更有趣的应用。想想我那个时代，用的计算机像冰箱那么大，还是打孔式的，所以你就会看到这样的一种发展的空间。我相信，很快电脑设备将能够模拟人工智能。但是它底层的技术是不变的；所以我这样做基础研究的人的优势在于，这份工作是不变的。
我觉得如果你对小孩进行填鸭式的教育，他们肯定会反抗的。我个人更倾向于把孩子放在充满丰富的选择和丰富信息的环境下，让他们自己去选择。其实你看这个世界上，真正杰出的数学家是非常少的，而且世界上并不需要那么多杰出的数学家。但是这个世界正在变得越来越技术性；我们确实需要大量的能够懂数学，能够运用数学做编程的人，所以我觉得教育的方法还是应该因材施教。
Q：刚才提到遇到挫折就会撞墙，会经常这样吗？ Robert：这是一种修辞用法！否则脑袋早撞扁了。
Q：遇到的挫折多不多？ Robert：事实上，我的博士论文花了1年多的时间才找到答案。其实在一年多的时间里，研究是断断续续的。很可能会进入死角，那就搁置一会儿，再回头研究。还有一些课题，我甚至研究了10年之久。
Q：我不知道您来的2天时间里，见到的中国年轻人给你的印象如何？能不能给这些在计算机领域有天赋的年轻人一些建议，怎样才能成为像您这样大师级的人物？ Robert：惠普中国研究院的孩子们都是很好，而且都很聪明，工作非常努力，我对他们的印象非常好。我对这些年轻的有天赋的年轻人的建议是：一定要找到自己想要研究的课题，不要盲目听从别人的话依照去做。我跟这些年轻人说：不要总跟着业务部门的人做事。事实上，研究员的眼界应该比他们放得更广，要看到五年甚至以后更长久的方向。
我觉得，象惠普研究院这样做基础性研究的机构在整个产业界并不多。我们看到的互联网公司，他们做一些非常先进的编程，做一些产品或者技术的开发工作；但是基础性研究他们不做。他们觉得基础性研究应该由大学院校去做。所以，我觉得惠普研究院的机制确实很少见。因此，我最后还是回到给他们建议上：要找到自己的课题，准备好要努力工作的方向。还有一点，你要愿意和你的同事和朋友一起工作，有了成果愿意和别人分享，而且也要和别人去交流，要保持一种开放的态度！而且要有持久的耐心，设立一个长远的目标，要一步一步去实现！感谢你们花时间聆听，希望我的分享对你们有用！
