硕果累累的算法大师

cyan

1986年图灵奖由康乃尔大学机器人实验室主任约翰·霍泼克洛夫特(John Edward Hopcroft) 和普林斯顿大学计算机科学系教授罗伯特·塔扬(Robert Endre Tarjan)共享，而塔扬曾是霍 泼克洛夫特的学生。这师生两人由于在数据结构和算法的分析和设计方面的许多创造性 贡献而共同获此殊荣，在业界传为美谈。 <br /><br />霍泼克洛夫特1939年10月7日生于西雅图。1961 年在西雅图大学获得电气工程学士学位以后，进入斯坦福大学研究生院深造，1962年获 得硕士学位，1964年获得博士学位，也就是说只用了3年时间他就拿下了2个学位，霍 泼克洛夫特的勤奋和聪颖由此可见。学成以后，霍泼克洛夫特曾先后在普林斯顿大学、 康乃尔大学、斯坦福大学等著名学府工作，也曾任职于NSF(美国科学基金会)和NRC(美 国国家研究院)，从事对科学研究的规划和行政管理工作，但时间不长。 <br /><br />霍泼克洛夫特成为著名的计算机科学家起源于一个 十分偶然的机会。霍泼克洛夫特学习的专业是电气工程，原先对计算机科学没有多少知 识，只学过一门“开关电路和逻辑设计”算多少有些关系。因此他原打算毕业后去西海 岸的一所大学执教电气工程方面的课程。但就在毕业以前，有一次他偶然经过他的导师、 研究神经网络的先驱和著名学者威德罗(Bernard Widrow)办公室的门口，当时，普林斯顿 大学的麦克卢斯基教授(Edward McCluskey，曾任IEEE计算机协会主席)正为筹建数字系 统实验室打电话给威德罗，请他推荐博士生去那里工作。威德罗一眼瞥见从门口走过的 霍泼克洛夫特，觉得勤奋好学，悟性又高的这位得意门生正是一个值得推荐的人才，当 即把霍泼克洛夫特叫进办公室，并把电话听筒递给了他。霍泼克洛夫特在电话里听了麦 克卢斯基对普林斯顿大学拟建数字系统实验室的情况介绍，以后又前去面谈了一次，实 地了解一番以后，对这一新的学科产生了兴趣，欣然接受了普林斯顿的聘任，从而改变 了他一生的道路。 <br /><br />年青的霍泼克洛夫特来到普林斯顿之后接受的第一 项任务是开设一门新课：自动机理论。这对他来说是富有挑战性的，因为他之前并未接 触过这个课题。面对挑战，他以极大的热情收集、钻研和消化了大量有关材料，加以分 析、综合和比较。这样，在霍泼克洛夫特的努力下，有关自动机理论的一些分散、复杂 的材料第一次被全面地条理化、系统化，因此他的讲课理所当然地受到了学生极大的欢 迎。后来，霍泼克洛夫特和厄尔曼(J.D.Ullman)又合作编写了《形式语言及其与自动机的 关系》(《Formal Language and Their Relation to Automata》，Addison-Wesley,1969)一书，这 本书被认为是自动机理论中有代表性的一部著作。 <br /><br />然而，霍泼克洛夫特更感兴趣的课题是算法。当时， 算法复杂性理论虽已由哈特马尼斯(J.Hartmanis)、斯坦恩斯(R.Stearns,这两人是1993年图灵 奖获得者)和布鲁姆(M.Blam，1995年图灵奖获得者)等人奠定了基础，但对具体算法的效 率和优劣的判断尚未建立起客观和明确的准则，因此，往往出现下述情况：有人公布了 一个算法，给出对若干样本问题的执行时间；过了一段时间，另外一个人发布“改进算 法”，给出对相同样本问题的执行时间(当然比前者少)。而实际上，这很可能是由于机器 性能提高或(和)语言改进所致，所谓“改进算法”其实不见得比原算法高明。霍泼克洛夫 特对这种情况很不满意，决心加以解决。经过反复研究，他终于提出了一种称为“最坏 情况渐近分析法”(Worst-case asymptotic analysis of algorithm)，这种方法先确定问题和大小 尺度，然后把计算时间当作问题大小尺度的一个函数去算出计算时间的增长率，以此衡 量算法的效率和优劣。这个方法由于与机器性能及所用语言无关，成为测量算法好坏的 数学准则，被学界所广泛认同和接受。 <br /><br />但是导致他和塔扬共同获得图灵奖的最主要贡献则 是他们解决了图论算法中的一些难题。1970年，霍泼克洛夫特在康乃尔大学获得一年休 假(他是1967年被另一图灵奖获得者哈特马尼斯招至麾下的)。他决定回母校斯坦福大学 到克努特(D.Knuth)教授名下做研究，因为克努特虽然只比他年长一岁，但因在1967年和 1968年连出两卷《计算机程序设计的艺术》(《The Art of Computer Programming》)而已名 满天下，成为算法领域的权威。克努特知道霍泼克洛夫特对算法感兴趣并有独到见解， 就把他和自己的得意门生、研究方向也是算法的塔扬安排在一个办公室，为他们的合作 创造了条件。他们选择了图论中与实际应用有很大关系的图的连通性和平面性测试难题 进行攻关。拿平面图来说，它对印刷电路板设计这样一类问题有十分重要的意义。学过 图论的人都知道，平面图的判断问题，在数学上已由波兰数学家库拉托夫斯基(Kuratowski) 于1930年解决。库拉托夫斯基的判据原理看似简单，但实现起来很难。对于有100个顶 点的图，用普通的算法，计算机需要1万亿步才能确定其是否为平面图&#33;因此，寻找高效 的平面图测试算法成为摆在当时计算机科学家面前的一大难题。霍泼克洛夫特和塔扬都 是富有创造性的人，又都善于合作共事，因此当两朵智慧的火花碰在一起时，就很快迸 发出耀眼的光芒&#33;在解决这个难题的过程中，霍泼克洛夫特首先提出了一种新的思路、新 的算法，经过塔扬的反复推敲和完善，一种适于解这类问题的新的算法终于诞生了，这 就是“深度优先搜索算法”(depth-first search algorithm)。利用这种算法对图进行搜索时， 结点扩展的次序是向某一个分枝纵深推进，到底后再回溯，这样就能保证所有的边在搜 索过程中都经过一次，并且只经过一次，从而大大提高了效率。新算法的运行时间是线 性的，也就是说时间与图的大小成正比关系，大小翻一倍，解问题所需的时间也只翻一 倍。相比之下，若用库拉托夫斯基判断的老算法，那么当图的大小翻一倍时，所需时间 要增加60倍以上。利用他们创造的新算法，塔扬用Algolw为一个包含900个结点和2694 条边的图编制了一个测试其平面性的程序，程序只有500行，在IBM 360/67上运行，只 用了12秒就得到了结果。霍泼克洛夫特和塔扬把他们的研究成果写成论文在《Journal of the ACM》上发表，引起学术界很大的轰动。而他们创造的深度优先算法则被推广到信息 检索、国际象棋比赛程序、专家系统中的冲突消解策略等许多方面。在霍泼克洛夫特和 塔扬获得图灵奖的授奖仪式上，当年的计算机象棋程序比赛的优胜者就说，他的程序中 使用了霍泼克洛夫特和塔扬所发明的深度优先搜索算法，这是他的程序所以能出奇制胜 的关键。 <br /><br />在取得辉煌成功之后，霍泼克洛夫特和塔扬并不满足，他们致力于开发效率更高的算法。不久，他们又提出了一种新的数据结构叫“双堆 栈叠”（pile of twin stacks），这种新的数据结构被深度优先搜索算法的优点更加发扬光 大。塔扬的一个学生用这种新的数据结构和算法编写了一个Algolw程序，只有250行， 在IBM 370/168上测试有8000个结点的图的平面性只用了8秒钟。 <br /><br />霍泼克洛夫特除了和塔扬合作取得上述成果外，在数 据结构和算法方面还有其他一系列创造。比如常用于索引组织的著名数据结构B树(B-tree) 是一种平衡的多分树，由于对查找、插入、删除等操作能始终保持动态平衡，具有高效 的特性。霍泼克洛夫特在对B树进行深入研究以后，为了进一步提高其操作效率和空间 利用率，提出了它的一种变形叫2-3树，这种树的每个结点有2个键，每个键都有2-3个 儿子。 <br /><br />霍泼克洛夫特著述颇丰，除前面已经提到过的他的处 女作以外，还有以下多部著作问世： <br /><br />《计算机算法的设计与分析》、《数据结构和算法》 、 《自动机理论，语言和计算的导论》和《计算机科学 ：成就与机遇》。 <br /><br />霍泼克洛夫特最近的兴趣集中在机器人学方面，这从 他现任康乃尔大学机器人实验室主任这一点上可以看出。 <br /><br />罗伯特·塔扬1948年4月30日生于加里福尼亚州的波莫纳(Pomona)。塔扬从小就是一个富于幻想、追求新鲜事物的人。他幼时对天文学很感 兴趣，梦想成为第一个登上火星的人。小学七年级时他又开始读《科学美国人》(《Scentific American》，这是美国最著名的科普杂志之一)，尤其对著名数学家马丁·加德那(M.Gardner) 开设的趣味数学专栏深感兴趣(马西·加德那所著的《啊哈&#33;灵机一动》由上海科技出版社 于1981年译成中文出版，被中国科学家评为“20世纪科普佳作”之一而进行推介)。1964 年，塔扬参加一个中学生科学夏令营，第一次接触计算机，立即被神奇的计算机所吸引。 因此，当他上加州理工学院时，虽然学的专业是数学，但同时还辅修了当时学校开设的 所有有关计算机的课程。1969年他取得学士学位以后，进入斯坦福大学研究生院，师从 著名的计算机科学家、后来在1974年荣获图灵奖的克努特。1970年，在克努特的有意安 排下，他与到斯坦福来度学术假的康乃尔大学教师霍泼克洛夫特在一个办公室开始了对 图论算法的共同研究。他们的这个课题实际上是在有“人工智能之父”之称的麦卡锡 (J.McCarthy)的建议下进行的。当时塔扬正选修麦卡锡开设的“符号处理”(Symbolic processing)课程，学习由麦卡锡开发的第一个人工智能语言Lip。作为作业，麦卡锡让学 生编写程序以验证给定的图是否是平面的，并建议学生们在程序中使用库拉托夫斯基条 件。塔扬虽然一开始就意识到这样得出的算法效率太低，考虑“另起炉灶”，但不知从 何入手。这时霍泼克洛夫特提出的新思路、新算法启发了他，他仔细考虑了它，并力图 使霍泼克洛夫特的算法中的原则更加严密、更加完善，终于使深度优先搜索算法完美实 现，取得成功。 <br /><br />1992年，塔扬以平面图测试的高效算法为题完成了 博士论文，以优异成绩通过论文答辩取得博士学位，这时离他取得硕士学位刚刚一年。 学成以后，塔扬先是跟随霍泼克洛夫特去了康乃尔大学，以后又先后在加州大学伯克利 分校、母校斯坦福大学以及贝尔实验室工作过，其主要兴趣和研究方向仍是和生产、生 活有密切联系的一些算法问题和发现新的数据结构。塔扬到康乃尔大学后研究和解决的 第一个问题是所谓“合并-搜索问题”。这也是图论算法中的一个问题。在许多图论算法 中，要将图的结点分成若干不同的组，叫做“分区”(Partition)。在算法过程中，不同的分 区有时需要合并成较大的分区，这是合并搜索问题中的“合并”操作。算法中也经常需 要判断两个结点是否属于同一分区，这是合并搜索问题中的“搜索”操作。为了提高效 率，搜索操作应尽可能地编短搜索路径，这叫“路径压缩”(Path compression)。这个问题 看似简单，其实不然，包括一些知名学者在内的人在研究和分析这个问题的时候都犯了 这样那样的错误。塔扬深入研究了这个问题，最后利用阿克曼函数(Ackermann function， 这是数学家阿克曼在1928年找到的一个可计算、但不是原始递归的函数)成功地解决并分 析了“合并-搜索问题”。 <br /><br />在研究合并-搜索问题的过程中，塔扬还提出了所谓 “分摊”算法的概念。分摊(amortization)这个词是塔扬从财会术语中借用过来的，因为塔 扬发现，有时虽然单个操作可能很费时间，但通过路径压缩却可以大大减少以后查找操 作所需的时间，这就是说，一个查找操作额外做的工作可以“分摊”给从中受益的多个 查找操作，因此从整体上看是提高了效率。分摊的概念将对算法的注意力从关注单个操 作的时间转向关注整个操作的平均时间，在算法设计与分析中引起了一场革命。 <br /><br />1975年，塔扬和他的学生在斯坦福研究对于天然气 和石油管道运输这类问题有很大意义的最大网络流问题。这个问题由于对经济和交通、 通信的巨大实际意义而吸引了许多学者。福特(L.Ford)和富尔克森(D.Falkerson)早在1956 年就提出了解决这个问题的第一个计算机算法，但是某些情况下效率不高，甚至无法找 到正确答案。十年后埃德蒙多(J.Edmcnds)和卡泼(R.Karp，1985年图灵奖获得者)改进了这 个算法，使之有更高的效率。塔扬发现，最大网络流问题的关键不在乎算法本身而在于 数据结构。经过艰苦探索，塔扬和他的学生终于发明了一种称为“动态树”(dynamic tree) 的新的数据结构，在此基础上他们开发成功了前所未有的最大网络流高效算法，获得了 广泛采用。1980年，塔扬在贝尔实验室继续研究这一课题，将他以前提出的分摊的概念 用于网络流问题，发现如果不集中于最坏情况，而去关注平均时间，也就是说不追求在 最坏情况下的有效，而是追求在分摊的情况下有效，可以使最大网络流问题获得更好的 结果。循着这一方向，塔扬和他的学生提出了“自调整”(self-adjusting)数据结构的概念， 并发明了一种有着良好特性的新的数据结构——“八字形树”(splay tree)。目前，在算法 设计中利用塔扬提出的分摊来提高效率已成为重要的方法之一。 <br /><br />80年代初，塔扬一方面在贝尔实验室工作，一方面 在纽约大学当兼职教授。他和纽约大学的几个研究生开始了一项新的研究——研究能够 长期保存信息的数据结构，即利用这种数据结构不但可以跟踪其最近的信息，还可以跟 踪其过去的信息，塔扬称他们设计出来的这种数据结构为“持久性数据结构”(persistent data structure)。利用塔扬的持久性数据结构访问其当前信息的速度和通常的数据结构几乎一样 快，而要获得过去的信息只需要程序付出一点点额外的代价。持久性数据结构已经在计 算几何和并行处理中获得应用，但其更重要的应用领域是时态数据库(temporal database)， 尤其是历史性数据库(historical database)。 <br /><br />塔扬由于他的一系列创造性工作而获得许多荣誉。除 了图灵奖以外，1983年他被国际数学会IMU授予以著名数学家内兰林那命名的信息科学 奖(Neranlinnal prize in Information Science)，1984年美国科学院授予他研究创新奖(National Academy of Science Award for Initiatives in Research)。1987年和1988年他先后当选为美国科 学院院士和美国工程院院士。 <br /><br />在接受图灵奖时，霍泼克洛夫特和塔扬分别发表了演 说，前者的演说题为“计算机科学：作为一门学科的出现”(Computer science：the Emergence of a Discipline)，后者的演说题为“算法设计”(Algorithm Design)。两人还联合接受了记者 卡伦·弗兰克尔(Karen A.Frenkel)的采访。两篇演说及与记者的对话刊于《Communications of ACM》，1987.3.，197-222页。颁奖典礼是在德克萨斯州的达拉斯举行的1986年秋季 联合计算机会议期间举行的。

5810034

好~