复旦大三学生郭泽宇解决最小曼哈顿网络世界难题

数学星空

最小曼哈顿网络问题目录[隐藏]

最小曼哈顿网络问题简介
最小曼哈顿网络问题-背景
最小曼哈顿网络问题-问题
最小曼哈顿网络问题-解决途径
最小曼哈顿网络问题-困难
最小曼哈顿网络问题-最新进展
最小曼哈顿网络问题-成就




[编辑本段]最小曼哈顿网络问题简介
　　最小Manhattan网络问题是近年来受到广泛关注的计算几何和组合最优化问题。在大规模集成电路（VLSI）设计、分布式算法、计算生物学、网络设计、城市规划等领域发挥着越来越大的作用。
　　给定平面上一个点集T，其Manhattan网络由水平和垂直线段组成，并满足T中任意两点间在网络中存在Manhattan路径。可知Manhattan网络即为L1-范数下给定点集的一个1-spanner。更一般的概念称作geometric spanner或k-spanner，由于具有良好的性质，其应用十分广泛，包括邻近问题（proximity problems）的求解、机器人的运动规划、通信网络的可靠性等等。在本问题中，要求Manhattan网络中线段总长度最短，即以最小的代价构造给定点集的Manhattan网络。此外，F. Lam 等人在生物序列比对问题中应用了Manhattan网络的近似算法，显著减小了搜索空间。这显示了最小Manhattan网络问题在计算生物学中的应用。由此可见，这一问题的研究无论在理论还是实际中都有十分重要的意义。
　　最小Manhattan网络问题由J. Gudmundsson, C. Levcopoulos和G. Narasimhan于1999年最早提出。之后，许多学者研究并给出了这一问题多项式时间近似算法。之前通过组合方法设计的最佳近似算法（3-近似）由M. Benkert 等人在2004年给出。2005年，V. Chepoi [2] 等人提出了基于线性规划的2-近似算法，这是目前所知关于这一问题的最好近似度。
　　2009年6月复旦大学计算机学院大三学生郭泽宇关于“最小曼哈顿网络问题”的论文被第25届计算几何国际会议录用，文章同时作为最佳论文之一被邀请投稿到会议特刊DiscreteandComputationalGeometry(DCG)。这意味着计算几何领域十年来的重要猜想被这位年仅20岁的本科生成功解决。计算几何国际会议是计算几何领域最高级别的会议，这一会议，中国内地数学家已经阔别了整整十八年。
[编辑本段]最小曼哈顿网络问题-背景
　　最小曼哈顿网络问题，是1999年提出的世界级计算几何重要猜想。1999年，J. Gudmundsson, C. Levcopoulos和G. Narasimhan最早提出最小曼哈顿网络问题。之后，许多学者研究并给出了这一问题多项式时间近似算法。之前通过组合方法设计的最佳近似算法（3-近似）由M. Benkert等人在2004年给出。2005年，V. Chepoi等人提出了基于线性规划的2-近似算法，这是目前所知关于这一问题的最好近似度。
　　2009年6月，被上海复旦大学仅20岁的本科生郭泽宇成功解决。他的关于“最小曼哈顿网络问题”的论文被第25届计算几何国际会议录用，文章同时作为最佳论文之一被邀请投稿到会议特刊Discrete and Computational Geometry(DCG)。
[编辑本段]最小曼哈顿网络问题-问题
　　给定平面上一个点集T，其Manhattan网络由水平和垂直线段组成，并满足T中任意两点间在网络中存在曼哈顿路径。可知曼哈顿网络即为L1-范数下给定点集的一个1-spanner。更一般的概念称作geometric spanner或k-spanner，由于具有良好的性质，其应用十分广泛，包括邻近问题（proximity problems）的求解、机器人的运动规划、通信网络的可靠性等等。在本问题中，要求曼哈顿网络中线段总长度最短，即以最小的代价构造给定点集的曼哈顿网络。此外，F. Lam等人在生物序列比对问题中应用了曼哈顿网络的近似算法，显著减小了搜索空间。这显示了最小曼哈顿网络问题在计算生物学中的应用。
[编辑本段]最小曼哈顿网络问题-解决途径
　　设计出具有更优近似度的近似算法
　　近似算法的设计方法主要包括：局部搜索，线性规划方法，原始对偶（primal-dual）方法等。本问题已知的近似算法可以分为两类：一类方法是将全局最优网络问题规约为局部最优网络问题，再通过局部网络的组合达到全局的较优解，如M. Benkert 等人提出的3-近似算法。在这一方法的使用中，郭泽宇已取得了国际领先的成果。另一类则基于线性规划方法，如V. Chepoi等人在文献提出的2-近似算法。
　　在第一阶段的研究中，一方面在已知的最好近似算法基础上，对问题的性质进行更细致地分析以尝试改进；另一方面对近似算法的设计进行系统的学习，探索其他的算法设计思路。
　　研究问题所属的复杂性类
　　尽管在过去的近十年里，最小曼哈顿网络问题[1]受到许多西方计算机科学家的重视，但是到目前为止，人们还不清楚这一问题是否存在多项式时间算法。人们猜想这一问题是NP-完全的，但到目前为止还没有人给出有效的证明。
　　一般来讲，证明一个问题是NP-完全的基本方式是将一已知的NP完全问题归约到所研究的问题上。这方面，已知的NP-完全的计算几何和组合最优化问题的归约过程将具有很大参考价值。例如V. Chepoi在论文中提到的与最小曼哈顿网络问题相当类似的RSA问题，已经由W.Shi 和C. Su给出了从Planar-3-SAT问题到该问题的归约，从而证明了该问题为NP-完全的。因此，郭泽宇通过阅读更多的计算几何学NP-完全问题规约的文章，掌握各种复杂的技巧。试图给出最小曼哈顿网络问题的类似的归约方式，从而证明这一问题是NP-完全的。
[编辑本段]最小曼哈顿网络问题-困难
　　最小曼哈顿网络问题的是否NP-难问题仍属未知，其不可近似性亦不清楚。因此，研究这一问题所属的复杂性类将具有极大的理论意义和实际价值。
　　郭泽宇提出解决最小曼哈顿网络的算法复杂性NP难问题是不太现实的，但改善现有解决方案的效率或提高近似度是可行的研究方向，郭泽宇的结果是2-近似O(n2)时间复杂度。能否将效率提高到O(nlogn)，与3-近似方法相同？或提出1.5-近似的新方法是亟待解决的新问题。
[编辑本段]最小曼哈顿网络问题-最新进展
　　复旦大学2009年6月21日传来消息，该校计算机学院大三学生郭泽宇关于最小曼哈顿网络问题的论文被美国ACM学会主办的第25届计算几何国际会议录用，文章同时作为最佳论文之一被邀请投稿到会议特刊(DCG)。
　　这意味着计算几何领域十余年来未决的重要猜想被这位年仅20岁的本科生成功解决。
　　2008年6月，郭泽宇申请了复旦大学本科生学术研究资助计划的“莙政”项目。最小曼哈顿网络问题是计算机学院朱洪教授给自己指导的本科生们所开设的题目。
　　郭泽宇大胆地选择了这一问题作为项目攻克对象。这既让朱洪教授和博士研究生孙贺这两位项目指导老师感到欣喜，也让“莙政”学者评审专家们捏了一把汗。基于鼓励本科生创新和支持年轻人闯劲的考虑，郭泽宇最终得到了资助。经过200多个日夜的思考和探索，这一难题终于被他找到突破口。
[编辑本段]最小曼哈顿网络问题-成就
　　在算法研究领域，人们最重视的是那些长期悬而未决的问题。“曼哈顿网络问题”就是这样一个不清楚它是否是P还是NP的问题。现在已经有近似度为2的近似算法，但是复杂度为O(n^8)。而郭泽宇把算法改造。使之加快到O(n^2)，是值得赞许的工作。所以被接受为国际会议大会报告，反映了同行对它的重视程度。
　　曼哈顿网络问题是计算机理论界研究的重要课题，郭泽宇对最小曼哈顿网络的算法复杂性进行研究，有理论意义和应用价值。鉴于目前曼哈顿网络问题是否NP问题尚无明确的结论，目前对曼哈顿网络问题的研究都集中在近似算法的研究。郭泽宇在导师指导下的前期工作对已有的2-近似算法进行改进，使其时间复杂度达到O(n2)(原算法为O(n8))，课题有很好的研究基础，有望得到进一步的创新成果。
　　最小曼哈顿网络问题-郭泽宇怎么解决最小曼哈顿网络问题？
　　2008年6月，郭泽宇申请了复旦大学本科生学术研究资助计划的“莙政”项目。最小曼哈顿网络问题是计算机学院朱洪教授给自己指导的本科生们所开设的题目。
　　郭泽宇大胆地选择了这一问题作为项目攻克对象。这既让朱洪教授和博士研究生孙贺这两位项目指导老师感到欣喜，也让“莙政”学者评审专家们捏了一把汗。基于鼓励本科生创新和支持年轻人闯劲的考虑，郭泽宇最终得到了资助。经过200多个日夜的思考和探索，这一难题终于被他找到突破口。
　　据悉，计算几何国际会议是计算几何领域最高级别的会议，这一会议，中国内地数学家已经阔别了整整十八年。
　　在郭泽宇的项目申请书中，中国科学院院士陆汝钤作为推荐老师，对本科生学术研究资助计划给予了充分的肯定，他认为通过这一方式使许多学生脱颖而出，走上了从事科学研究的道路。记者了解到，1998年，在李政道先生倡导和设立的“莙政基金”支持下，复旦大学开始开展资助优秀本科学生尽早接触学术研究的计划，并逐渐形成了一个层次分明、申请时间灵活、申请形式多样的本科生学术研究资助平台，即复旦大学本科生学术研究资助计划。
　　从1998年到2008年，共有1556位学生获得资助开展研究，其项目学科涵盖了医学、工学、理学、文学、教育学等多个领域。另据不完全统计，在2008年，参加复旦大学本科生学术研究资助计划资助项目的同学在国内外期刊发表论文30篇，其中第一作者文章20篇。

转自：http://baike.baidu.com/view/2563949.htm

mathe

感觉这篇文章报道问题百出.
首先所谓解决这个问题的说法肯定不正确,最多不过是算法上的改善

数学星空

呵呵，你可以先搜索他发表的论文看一下嘛。。。。

mathe

对于他的论文是什么,我兴趣也不大.
这里我并不是怀疑他的论文到底有什么成就.而是这个新闻报道本身看上去实在混乱

数学星空

我想你说的也有道理,至少这篇报道不是在专业的数学网页上公布,因些并没有彻底从理论上解决,可能只是算法由复杂度为O(n^8)改造,使之加快到O(n^2)....

litaoye

O(n^8) 到 O(n^2) 确实还是很NB的。

不太清楚2-近似的含义，比上面说的3-近似效果好还是差？

感觉近几年来，中国计算机行业的人才越来越多了。相信以后会转化为生产力的。

kon3155

看不懂。。。
最小Manhattan网络的算法复杂性研究

数学星空

复旦生破解数学难题 专家称不宜过度吹捧
发布: 2009-7-08 11:14 |  作者: xiaohuhu |   查看: 313次

专家表示,这件事情的正面意义，就在于年轻人锲而不舍地研究问题、探索难题的精神。现如今，大学生更应该在本科时就沉下心去搞科研，有探索难题的勇气。这才是最重要的，而不是追求“世界级”的轰动效应。
   
    年仅20岁的复旦大学大三学生郭泽宇和25岁的博士研究生孙贺，共同完成了关于“最小曼哈顿网络问题算法和复杂性”的论文。论文近日被第25届计算几何国际大会（SCG）录用，他们也受邀出席大会作报告。一时间，“复旦学生破解世界级几何猜想”的消息被争相报道，但其中“世界级”轰动的评价，很快引来了人们的质疑。记者昨天就此采访专家，他们给出的观点可谓中肯：本科生潜心研究破解难题的精神值得倡导，但离“世界级猜想”还有距离。
   
本科生破解10年未解的数学难题
   
    在位于丹麦奥胡思大学湖岸剧院的25届计算几何国际大会报告上，郭泽宇代表论文作者做了大会报告，报告题目是最小曼哈顿网络是NP-C。这意味着：计算几何领域这一十年未决的重要问题，由两位年轻人成功解决。
   
    给定平面上的一个点集，构造总长度最小的网络，使得任意两点之间都有长度最短的路径相连。这一根据曼哈顿城市地图而抽象出来的数学问题，被称作最小曼哈顿网络问题，该问题在城市规划、网络路由、大规模集成电路设计以及计算生物学等众多领域有着很好的应用。上个世纪九十年代，西方学者Levcopoulos等人提出了最小曼哈顿网络设计的三个重要问题，而其中最为关键的，即是确定这一问题的计算复杂性类。
   
    参加这一盛会的，不仅有全世界最出色的数学家、理论计算机科学家和图像处理的专家，还有十一年前提出这一难题的Levcopoulos。在这些世界级的科学家面前，郭泽宇用仅有的20分钟展现了解决世界难题的证明轮廓。
   
    自2007年起，郭泽宇和孙贺就开始致力于最小曼哈顿网络问题算法和复杂性的研究。在去年正式立项后，整整半年多时间，这一问题一直萦绕在两个人的脑海中。漫长的思考换来了灵感的闪现，十年未决的难题终于被他们所破解。他们将所有的证明细节重新整理，并绘制证明中所需要的每一幅插图，然后将论文投稿到第25届计算几何国际大会(SCG 2009)。
   
    2009年2月13日清晨，他们得到了来自SCG程序委员会的好消息：经过4至6位专家两个半月的认真审稿，他们的论文在近170篇文章中脱颖而出，被大会录取，并作为最佳论文之一应邀投稿到世界顶级期刊《离散与计算几何》中。
   
沉下心比“轰动世界”更重要
   
    “这谈不上世界级难题，更不能说是世界级猜想，只不过是一个难题，值得关注的是年轻人静下心来搞科，而且勇于破解难题”，复旦大学计算机学院朱洪教授这样评价两个年轻人的成果。
   
    朱洪教授称，这一问题10年左右都没有人解决，但是现在本科生和博士生证明了，至少是一个进步。他认为，这件事情的正面意义，就在于年轻人锲而不舍地研究问题、探索难题的精神。“现如今，大学生更应该在本科时就沉下心去搞科研，有探索难题的勇气。这才是最重要的，而不是追求‘世界级’的轰动效应。”
   
    有关专家介绍，SCG是顶尖会议，论文收入也就四五十篇。而且在过去的50年中，并没有本科生能够到SCG会议上宣读自己的论文。更重要的是，中国内地研究机构已经阔别这个顶尖会议18年了。
   
    朱洪教授进一步解释道，所谓“最小曼哈顿网络问题”，通俗来讲就是指网络上两点之间的通讯所花的代价，人们希望能做到最小。“郭泽宇和孙贺所做的事情，就是证实了要找到最小的代价几乎是不可能的，只可以努力去寻找一个近似的最优的通讯方式。”朱洪教授表示，就像以前曾经有人试图将一个角分为三部分，很多人都在努力寻找具体做法，但是后来终于有人证明单纯用直尺和圆规是做不到的。郭泽宇和孙贺的结论，就是向人们证实了要找到精确、快速的算法是基本不可能的，所以可以降低要求来寻找一个近似的算法。
   
别让过度吹捧毁了年轻人
   
    “这是不是世界级的难题，并不是谁能说了算的，而是应该由其他人来评价。像现在这样对年轻本科生的成就过分吹捧，会给他们带来更多的副作用。”一位中科院院士这样告诉记者。
   
    这位院士称，其实数学领域的所谓难题很多，如果动不动就说破解了“世界级难题”，只会让国外专家笑话，觉得中国学者缺乏判断力。而且很多数学难题即使解决了，也仅仅是解决了一个难题而已，未必会带来什么实际影响或者实际应用。而许多人在网上发出的质疑，也都是认为乱吹捧不仅会影响年轻人，还会给科研带来负面影响。有网友直言不讳：“动不动就世界级，弄得搞科研像养鸡的农民，恨不得生了个鸡蛋就立刻送到农贸市场去。”
   
    在郭泽宇的项目申请书中，中国科学院院士陆汝钤作为推荐老师，认为应该充分肯定的是对本科生学术研究的支持，因为这一方式会使许多学生脱颖而出，走上从事科学研究的道路。

joy

～羨慕...唉～感覺自己本科白過了～

cn8888

“莙政”学者忽悠人的,都是院长或者长江学者或者院士指导的学生才可能被批准,
如果你找的是普通教授,你不可能被批准的