曼哈顿网络

最小曼哈顿网络问题是复旦大学计算机学院朱洪教授给自己指导的本科生们所开设的题目。自2007年起，还是大一新生的郭泽宇，就开始和项目导师孙贺一起致力于最小曼哈顿网络问题算法和复杂性的研究。去年6月，郭泽宇受到复旦大学本科生学术研究资助计划“莙政学者”项目的资助，在朱洪教授、博士研究生孙贺两位项目指导老师的指导下开展学术研究。最小Manhattan网络问题是近年来受到广泛关注的计算几何和组合最优化问题。在大规模集成！电路（VLSI）设计、分布式算法、计算生物学、网络设计、城市规划等领域发挥着越来越大的作用。

简介

曼哈顿网络

复旦大学计算机学院三年级学生郭泽宇破解了一个猜想——根据曼哈顿城市地图抽象出来的数学问题：最小曼哈顿网络问题。他的论文被计算几何界最高层次的学术会议——第25届计算几何国际会议录用，同时作为最佳论文被会议特刊约稿。

理论内容

给定平面上的一个点集，构造总长度。最小的网络，使得任意两点之间都有长度最短的路径相连——学者们给它起名“最小曼哈顿网络问题”。这十多年来，因证明计算极其复杂，这个“最小”只是猜想。

应用

最小曼哈顿网络问题在城市规划、网络路由、大规模集成电路设计以及计算生物学等众多领域有着很好的应用，但它是国际计算几何领域没有解决的“猜想”。

解释

给定平面上一个点集T，其Manhattan网络由水平和垂直线段组成，并满足T中任意两点间在网络中存在Manhattan路径。可知 Manhattan网络即为L1-范数下给定点集的一个1-spanner。更一般概念称作geometric spanner或k-spanner，因为具有良好的性质，应用十分广泛，包括邻近问题（proximity problems）的求解与机器人的运动规划及通信网络的可靠性等等。在本问题中，要求Manhattan网络中线段总长度最短，即以最小的代价构造给定点集的Manhattan网络。此外，F. Lam 等人在生物序列比对问题中应用了Manhattan网络的近似算法，显著减小了搜索空间。这一问题研究无论在理论还是实际中都有十分重要的意义。

郭泽宇关于“最小曼哈顿网络问题”的论文被第25届计算几何国际会议录用，文章同时作为了最佳论文之一被邀请投稿到会议特刊DiscreteandComputationalGeometry(DCG)。这意味着计算几何领域Decades重要猜想被这位年仅20岁本科生成功解决。计算几何国际会议是计算几！何领域最高级别的会议，这一会议，中国内地数学家已经阔别了整整十八年。

曼哈顿网络-由于郭泽宇同学在香港大学的出色表现，钱玉麟教授对复旦大学的莙政学者计划给出了很高的评价。他希望郭泽宇同学在下个学期继续在香港大学作交流学生，与孙贺一起进行更加深入的研究。

这样的做法无论在香港大学，还是在复旦大学；无论是交流学生，还是莙政学者的培养方式；都是没有先例的。钱玉麟教授在前一阶段为郭泽宇能够留在香港大学作交流学生作了最大的努力，并且排除了郭泽宇留在香港大学的障碍。钱玉麟教授也与孙贺谈，希望以香港大学工程学院副院长的身份向复旦大学的有关领导写一封正式的邀请信，以表明香港大学官方的诚意和对这件事情的关心。

曼哈顿网络-曼哈顿网络的复杂度的研究取得重大进展

复旦停电检修线路刚结束，我来到实验室，打开电脑，就收到孙贺从香港发来的电子邮件。他向我报告，郭泽宇在香港大学的工作很出色，他和郭泽宇对曼哈顿网络的复杂度的研究取得重大进展。自曼哈顿网络的复杂度问题于1999年提出至今，没有人知道问题的答案。因而使得对这一问题的研究成为计算几何中最为重要的几个未解决问题之一。在过去的半个月里，经过他们和钱玉麟教授的仔细分析、检验证明，确信他们在国际上首先解决了这个难题。整个证明过程经过了反复检查，论文正在撰写中，并准备投稿到计算几何的顶级会议SoCG中。

思考探索

经过200多个日夜的思考和探索，这个十年未决的数学难题，竟然真的被郭泽宇和导师所破解。2008年11月末，郭泽宇和导师孙贺一起将论文投稿到由美国ACM学会主办的第25届计算几何国际大会中。

This year2月13日清晨，大会程序委员会传来喜讯：他们的论文在近170篇文章中脱颖而出，并作为最佳论文之一受邀向世界顶级期刊《离散与计算几何》投稿。This year6月，在位于丹麦奥胡思大学湖岸剧院的第25届计算几何国际大会上，郭泽宇代表论文作者做了报告

具体内容

简介

最小Manhattan网络问题是近年来受到广泛关注的计算几何和组合最优化问题。在大规模集成电路（VLSI）设计、分布式算法、计算生物学、网络设计、城市规划等领域发挥着越来越大的作用。

在该问题里，要求Manhattan网络里线段总长度最短，即以最小代价构造给定点集的Manhattan网络。此外，F. Lam等人在生物序列比对问题中应用Manhattan网络的近似算法，显著减小搜索空间。显示最小Manhattan网络问题在计算生物学中的应用。由此可见，这一问题的研究无论在理论还是实际中都具有十分重要的意义。

提出

最小Manhattan网络问题由J. Gudmundsson, C. Levcopoulos和G. Narasimhan于1999年最早提出。之后，许多学者研究并提出这一问题多项式时间近似算法。之前通过组合方法设计了最佳近似算法（3-近似）由M. Benkert等人在2004年提出。2005年，V. Chepoi等人给出基于线性规划的2-近似算法，是所知关于这一问题的最好近似度。

2009年6月复旦大学计算机学院大三学生郭泽宇关于“最小曼哈顿网络问题”的论文被第25届计算几何国际会议录用，文章同时作为最佳论文之一被邀请投稿到会议特刊DiscreteandComputationalGeometry(DCG)。这意味着计算几何领域Decades的重要猜想被这位年仅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-近似算法。

在第一阶段的研究中，一方面在已知的最好近似算法基础上，对问题的性质进行更细致地分析以尝试改进；另一方面对近似算法的设计进行系统的学习，探索其他的算法设计思路。

研究问题所属的复杂性类

尽管在过去的近十年里，最小曼哈顿网络问题受到许多西方计算机科学家的重视，但是到目前为止，人们还不清楚这一问题是否存在多项式时间算法。人们猜想这一问题是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多个日夜的思考和探索，这一难题终于被他找到突破口。

项目

据悉，计算几何国际会议是计算几何领域最高级别的会议，这一会议，中国内地数学家已经阔别了整整十八年。

该课题在城市规划、网络路由、大规模集成电路设计以及计算生物学等众多领域有着很好的应用前景。不过自曼哈顿网络的复杂度问题于1999年提出至今，没有人知道问题的答案，从而使得对这一问题的研究成为计算几何中最为重要的几个未解决问题之一。

在郭泽宇的项目申请书中，中国科学院院士陆汝钤作为推荐老师，对本科生学术研究资助计划给予了充分的肯定，他认为通过这一方式使许多学生脱颖而出，走上了从事科学研究的道路。记者了解到，1998年，在李政道先生倡导和设立的“莙政基金”支持下，复旦大学开始开展资助优秀本科学生尽早接触学术研究的计划，并逐渐形成了一个层次分明、申请时间灵活、申请形式多样的本科生学术研究资助平台，即复旦大学本科生学术研究资助计划。

领域

从1998年到2008年，共有1556位学生获得资助开展研究，其项目学科涵盖了医学、工学、理学、文学、教育学等多个领域。另据不完全统计，在2008年，参加复旦大学本科生学术研究资助计划资助项目的同学在国内外期刊发表论文30篇，其中第一作者文章20篇。