复旦大学 。孙贺。郭泽宇 。曼哈顿网络
作者 陈怀临 | 2009-06-26 16:43 | 类型 专题分析 | 10条用户评论 »
|
最近，复旦大三本科学生破解“最小曼哈顿网络问题”猜想的消息轰动了全国。笔者认为那些记者们估计对什么是曼哈顿网络都是第一次听说。但这好像不妨碍记者们的妙笔生花。 这倒是首先证明了目前中国记者这个行业的低劣。 这个新闻源自第25界计算几何年会（Proceedings of the 25th annual symposium on Computational geometry）的一篇来自中国的学术论文。这篇题目为“Minimum Manhattan Network is NP-Complete”的文章获得了最佳论文奖。论文的作者是三位，其中第二和第三作者分别为来自复旦大学计算机系的郭泽宇与孙贺。这篇论文题目的中文翻译是：最小曼哈顿网络问题是一个NP完全问题。第一作者为香港大学计算机系的教授Francis Y. L. Chin。Francis于1996年就被评为IEEE的院士（Fellow）。 本文试图从科普的角度简单介绍一下曼哈顿网络问题和孙贺与郭泽宇的工作。 为什么说简单介绍？因为，笔者花了2天的时间，基本上没有看懂其数学证明。自古英雄出少年呀！中国最不缺的就是人才。不知道缺的是什么。 最小曼哈顿网络问题，是1999年提出的一个计算几何重要猜想。由J. Gudmundsson, C. Levcopoulos和G. Narasimhan最早提出。其大概意思是：在一个二维的平面中，有n个离散的点。你现在要构造一个网络，从而任意的两点之间要能够存在一条路。这条路我们叫做曼哈顿路径。这个网络叫做曼哈顿网络。关于这个路有一个限制条件，其要么是水平的（线段），要么是垂直的（线段）。用北京的路来说，就是，要么是南北向的，要么是东西向的。你不能是南方小城中的那种斜路，更不要是周庄的那种小歪路了。在定义了这些条件之后，最小曼哈顿网络（Minimum Manhattan Network)问题是：你如何找出一个算法，从而对于任何的n个点，你能构造出一个总长度最小的曼哈顿网络。下图是曼哈顿网络的一个图解示例：
图一所示的就是一个10个节点的曼哈顿网络图。请注意，连接任何节点的道路（曼哈顿路径）要么是水平的线段要么就是垂直的线段。图二解释的是在曼哈顿网络中，两个节点之间的曼哈顿路径长度的计算是 |x1-x2| + |y1-y2|(笔者注：对于这个没有明白的读者，请报考补习初二的平面几何。)。其中节点1的坐标是（x1,y1);节点2的坐标是（x2,y2)。图2的左边的图不是曼哈顿网络或路径，为什么？路都是斜的连接。 读者立刻可以联想到，这个很有用。例如城市道路规划，芯片布线设计等等。。。其实笔者认为基本上没有用，其实就是数学家和计算几何学者们冬天在家YY时的题目。反正歇着也是歇着：-）在工程实践中，次优解往往是最好的方案。 那么郭泽宇同学和孙贺同学等的工作贡献是什么？ 是证明了，最小曼哈顿网络算法是一个NP完全问题。 NP什么意思？简单的讲，指的是，这个算法是可解的，但是，算法复杂性不是一个多项式时间，而是一个指数级别的复杂性问题。例如，流行的人肉搜索就应该是一个NP问题。 在该论文中，严格证明了这个问题不仅仅是NP Hard问题，而且是NP完全问题。NP完全的意思是：如果这个问题有多项式复杂度的求解方案，天下所有的NP问题都可以通过多项式时间复杂度的映射得出其多项式求解方案。用通俗的化讲，就是最难的问题。如果这个问题可以被多项式时间的算法来求解，天下所有的可解的问题都没有问题。那么NP就等于P了。NP等于P又是什么意思？基本上不能往下讲了。基本上就超出弯曲评论的范畴了。 那么是如何证明最小曼哈顿网络问题是NP完全问题的呢？ 是通过非常漂亮的数学技巧，利用经典的NP完全问题3-SAT，通过构造一个多项式复杂度的映射（归纳），产生MMN（最小曼哈顿网络）算法，从而可以得出，MMN是NP-Complete，即NP完全问题。笔者自己基本上看不懂其证明。当然，笔者并不惭愧，确实很难：-） 从复旦大学透露的相关资料，两位同学应该是在香港大学计算机系Francis教授的指导下开展的最后攻关工作，并完成的论文。笔者感觉郭同学是做出了突破的那个人。Francis不用说，是指导老师，而且应该是论文的主要起草者。郭同学当然是聪慧过人，但以一个大三学生能把一个高水平的英文论文写好，除非他是复旦大学外语学院的，而非计算机系的。孙贺同学是郭泽宇的直接指导老师和合作者，也是一个主要贡献者。其在复旦大学计算机系有主页，看了一下 ，相当的优秀。孙贺，1984年1月出生,2002年世界数学家大会十五分钟报告人，当时，其年仅18岁（！！！）。2002年进入复旦。目前复旦大学计算机系的博士生。这里是年仅25岁的孙贺同学的主页。 最小曼哈顿问题本身不算是计算理论，或者计算复杂性领域的重大问题，但是计算几何方面的一个突出问题。 这次对MMN是NP完全的证明，确实是一个突破，是一个很漂亮的证明。 我个人认为，这篇重量级文章的面试，基本上是复旦大学计算机系在理论研究方面的里程碑。可以说北有清华，南有复旦。 有兴趣的读者可以参阅发表的英文论文： Minimum Manhattan Network is NP-Complete | |
   (3个打分， 平均：3.67 / 5) |
雁过留声
“复旦大学 。孙贺。郭泽宇 。曼哈顿网络”有10个回复
感谢陈先生讲的公道话。
我讲的公道话？？咔咔，咔咔。我可没有替人买单：-）。讲的是事实而已。
挺好的。我个人认为数学发展程度是自然科学发展程度的一个很重要的指标。
这件事情对清华姚期智等一定是个大触动。Andrew一定会为中国年轻一代而自豪。当然，清华要加油了：-）
在理论方面，基本上地位已定：北清华，南复旦。无人能增锋了。当然，在系统软件方面，我大宋是全线崩溃。国无良将。
这篇文章的确是计算几何学上的一个重要结论，就这一句话就够了：The decision problem version of MMN is NP-complete.
此文不是理论计算上的重大突破。基本上证明一个NP问题是NP-complete问题的方法都是从经典的NP-complete问题，比如3-SAT或者traveling salesman着手找映射。文章在方法论上没有提出新东西。但是使用各种gadget来找这个映射的过程的确漂亮——数学的魅力也在于此。
记者们的报道其实为此成果减色不少。就看记者们写的“什么是最小曼哈顿网络问题”一章，就让人悲哀莫名——哪怕稍微格物致知一点，记者们写的东西就不会这个样子。
冷板凳还是有大有作为的
受教
以前在某杂志上看过孙贺的介绍
现在变得这么厉害
system方面复旦的PPI实验室还是很不错的。近两年来有过OSDI和ISCA，都是顶级的会议。至于这个结果能触动Yao，作者还是夸张了点。两边实力差很多了好吧。他们那边之前的Xi Chen， Pinyan Lu都做了非常好的工作。Xi Chen和Xiaotie Deng做的2-player mixed Nash Equilibrium is PPAD-completeness那个结果比这个是重要多了。
一点看法：
1。理论的文章常常是以姓氏的字母顺序排名的，所以不好看出谁的贡献更大。
2。这篇文章是否获得最佳论文奖，有待考证。一般计算机会议的一些质量较好的文章被邀请投到杂志上。这些杂志有的不一定最好，可是这个过程比较快，避免有审稿人作难，所以有些作者就顺手修改一下投到推荐的杂志上。这篇文章被邀请投到Discrete and Computational Geometry(DCG)杂志上。上次2008年同样会议有8篇文章发表在这个杂志上，另外有些文章推荐到Computational Geometry: Theory and Applications 上。我不是研究计算几何学的，但是知道第二个杂志，读过里面的文章，对第一个杂志不熟悉。
3。复旦的理论计算机，尤其是算法研究是不错的。姚先生在清华是这几年的事，以前中国作算法的，复旦的朱洪是中国做算法的屈指可数的几个之一。这两个复旦的学生都是受朱洪指导的。现在朱好像在华东师大。
4。现在看来，复旦的算法理论研究与清华差距太远了。说南有复旦还是太早了。如果复旦出了STOC以后还可以谈一谈。不过这也是很不错的一个起步。尤其是孙贺跟香港那边联系挺多，是不错的。
孙贺现在近况如何 在德国读博士后吗？