【^_^】复旦学生历时两年多破解11年“最小曼哈顿网络问题”--2009-06-24

migl

（ 以下信息整理于网络新闻。 ）

上海复旦大学计算机学院的一名大三学生近日竟然破解了世界级猜想的消息，在全国引起了很大的轰动。
这个引起全世界最出色的数学家、计算机学家惊叹的天才大学生，名叫郭泽宇，是河北省邢台市人，今年只有20岁。

“利用给定平面上的一个点集，构造总长度最小的网络，使得任意两点之间都有长度最短的路径相连。”
——这一根据曼哈顿城市地图抽象而出的“最小曼哈顿”难题于1999年提出至今，已在全球数学界求解11年。
最小曼哈顿网络问题(the minimum manhattan network problem)，是近年来受到广泛关注的计算几何和组合最优化问题。其在城市规划、网络路由、大规模集成电路设计，以及计算生物学等众多领域都有着很好的应用前景。
日前，复旦大学大三本科生郭泽宇和25岁的博士研究生孙贺成功解题，受到全球学界瞩目。

根据曼哈顿城市地图抽象出来的数学问题——最小曼哈顿网络问题，已在全球数学界求解11年，曾让无数顶级学者无果而终。
而作为本科学生的郭泽宇，又是如何破解成功的呢？

最小曼哈顿网络问题是复旦大学计算机学院朱洪教授给自己指导的本科生们所开设的题目。
自2007年起，还是大一新生的郭泽宇，就开始和项目导师孙贺一起致力于最小曼哈顿网络问题算法和复杂性的研究。
2008年6月，郭泽宇受到复旦大学本科生学术研究资助计划“莙政学者”项目的资助，在朱洪教授、博士研究生孙贺两位项目指导老师的指导下开展学术研究。

经过200多个日夜的思考和探索，这个十年未决的数学难题，竟然真的被郭泽宇和导师所破解。
2008年11月末，郭泽宇和导师孙贺一起将论文投稿到由美国ACM学会主办的第25届计算几何国际大会中。
今年2月13日清晨，大会程序委员会传来喜讯：他们的论文在近170篇文章中脱颖而出，并作为最佳论文之一受邀向世界顶级期刊《离散与计算几何》投稿。
今年6月，在位于丹麦奥胡思大学湖岸剧院的第25届计算几何国际大会上，郭泽宇代表论文作者做了报告。

阔别18年后，中国大陆数学家重返计算几何国际大会（SCG）舞台
6月24日，复旦大学传出消息，该校计算机学院两位学生关于最小曼哈顿网络问题算法和复杂性的论文，近日被第25届计算几何国际大会（SCG）录用，两人应邀出席大会并作相关报告。
两位作者分别为年仅20岁的复旦大学计算机学院大三本科生郭泽宇和年仅25岁的博士研究生孙贺。
这是25年来，中国大陆研究机构的学者第二次应邀在这一世界最高级别会议上报告自己的工作成果，而这个看似平常的讲台，中国大陆数学家已经阔别整整18年。
参加这一盛会的，不仅有全世界最出色的数学家、理论计算机科学家，还有11年前提出这一难题的Levcopoulos。
在他们面前，郭泽宇用仅有的20分钟时间，展现了解决这一世界难题的证明轮廓。
他不仅以流利的英语、清晰的表达能力给代表留下了极为深刻的印象，更让人惊叹其对问题罕见的洞察力和巧妙的证明能力

=========================

★ 数学、算术趣题 ★ 版块 没有相关报道。
我整理一下，就算是作个补充报道吧。

=========================

最后，补充一些百度百科词条：
最小曼哈顿网络问题
http://baike.baidu.com/view/2563949.htm
曼哈顿网络
http://baike.baidu.com/view/2571401.htm
有兴趣的，可以看看。

我这里只截个题目来让大家看看。

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


[ 本帖最后由 migl 于 2009-6-26 14:51 编辑 ]

ZJY

表示连题目都看不懂

aadxd

虽然不懂，但要绝对支持！！希望多出现这样的人才！

wyy1998

给中国人争了口气啊，顶一个！

ting12377

不明白
HELP= =

sokoban

conwood 兄说的中肯，这个问题主要还是一个算法设计问题。用“破解”一次的确不当。

另外新闻中的“阔别18年后，中国大陆数学家重返计算几何国际大会（SCG）舞台”
一句话中“阔别”、“重返...舞台”等字眼我感觉用得也不合适，有点怪怪的。



[ 本帖最后由 sokoban 于 2009-7-5 20:42 编辑 ]

Lonely_7X

這個看不太懂啊 不過感覺華人的智商在世界上還是相當有知名度的哦

migl

“破解”这个词用得确实不合适，确切而言应该是“取得重大突破”。
从多方面的资料来看，中国人是站在了前辈们的肩膀上取得了又一“突破”。

===============

也不知道他们对魔方的感觉如何。
如果他们研究“最少步问题”的话，也许能取得轰动魔坛的成果。

conwood

“破解”这个词用的不合适。

下面这个pdf应该是郭的最新进展。
http://www.madalgo.au.dk/socg200 ... bstracts/4_Chin.pdf

从摘要上看，他们证明了“最小曼哈顿网络问题”是强NP-完全问题。从欣然爹的帖子来看，似乎在这之前，郭还给出了一个效率更高的近似算法。当然，最有意义的还是NP-完全性的证明。

摘要上说是把3-SAT问题规约到了这个问题，目前还没找到论文的全文，不过可以想象的是，那一定是个非常美妙的规约。

littlehua

图论  图论  图论呀！！！！！！！