如何用算法解决现实世界里的问题

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

您好，请问您是想知道如何用算法解决现实世界里的问题吗？