魔方吧·中文魔方俱乐部

标题: 【^_^】复旦学生历时两年多破解11年“最小曼哈顿网络问题”--2009-06-24 [打印本页]

作者: migl 时间: 2009-6-26 12:44:38 标题: 【^_^】复旦学生历时两年多破解11年“最小曼哈顿网络问题”--2009-06-24

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

上海复旦大学计算机学院的一名大三学生近日竟然破解了世界级猜想的消息，在全国引起了很大的轰动。
这个引起全世界最出色的数学家、计算机学家惊叹的天才大学生，名叫郭泽宇，是河北省邢台市人，今年只有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等人在生物序列比对问题中应用了曼哈顿网络的近似算法，显著减小了搜索空间。这显示了最小曼哈顿网络问题在计算生物学中的应用。
示意图：（个人感觉这个图不是很标准。）
最小曼哈顿网络问题.jpg

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

附件: 最小曼哈顿网络问题.jpg (2009-6-26 12:44:38, 20.74 KB) / 下载次数 69
http://bbs.mf8-china.com/forum.php?mod=attachment&aid=NTY3OTh8NzBiMWEzMDJ8MTcyNjg5NjEzMXwwfDA%3D

作者: doris5200 时间: 2009-6-26 12:49:04

沙发。。顺便说句强！！！！！中国人确实非常聪明！

作者: bhw19930503 时间: 2009-6-26 13:00:16

非常强大啊

作者: 骰迷 时间: 2009-6-26 13:06:10

很強，頂，為中國爭光了
只是看不懂是最大遺憾

作者: jackytsz 时间: 2009-6-26 13:15:59

太強
問題都看不明白...
有人解釋一下嗎- -

作者: Cielo 时间: 2009-6-26 13:20:09

呵呵顶一个！为国争光了啊~~

作者: xdgtzsyyj 时间: 2009-6-26 13:31:24

这个问题不是一般人能看懂的啊，头晕了

作者: 漂流逆境 时间: 2009-6-26 13:55:01

真强大~！骄傲~！！！

作者: 曾吴昊 时间: 2009-6-26 14:11:20

句强！！！！！中国人确实非常聪明！

作者: ppowers 时间: 2009-6-26 14:31:45

厉害，厉害，佩服佩服。中华人才辈出啊

作者: my_ming3232 时间: 2009-6-26 14:43:10

虽然看不懂不过还是顶一下

作者: superacid 时间: 2009-6-26 14:51:37

好！顶一下！

作者: vanadium 时间: 2009-6-26 17:38:09

虽然水准有限
看不大懂
不过还是一个字：顶
为中国人骄傲

作者: kexin_xiao 时间: 2009-6-26 18:58:45

这个研究的意义非常重大

作者: kexin_xiao 时间: 2009-6-26 18:59:49

在算法研究领域，人们最重视的是那些长期悬而未决的问题。“曼哈顿网络问题”就是这样一个不清楚它是否是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篇。

作者: 骰迷 时间: 2009-6-26 20:13:11

前面的婁說中國人確非常聰明，怎麼我們就看不懂。。。。

作者: 浪迹萍踪 时间: 2009-6-27 08:08:15

呃滴神啊！太强了

作者: zhang197695 时间: 2009-6-27 10:58:53

中国的越来越强大，体现在各个方面。

作者: yq_118 时间: 2009-6-27 14:58:23

好强

他是怎么做到的

作者: putibenwushu1 时间: 2009-6-27 15:26:42

很遗憾，看不懂，不过支持中国。

作者: splendidrex 时间: 2009-6-27 15:43:14

俺们学校的。。。

作者: ggglgq 时间: 2009-6-28 17:21:36

　　


好资料，加精！希望本文对解决魔方最少步问题有所借鉴！


　　

作者: littlehua 时间: 2009-6-29 22:45:54

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

作者: conwood 时间: 2009-6-30 00:55:27

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

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

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

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

作者: migl 时间: 2009-6-30 09:26:47

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

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

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

作者: Lonely_7X 时间: 2009-6-30 09:45:25

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

作者: sokoban 时间: 2009-7-5 20:34:32 标题: 回复 24# 的帖子

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

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

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

作者: ting12377 时间: 2009-7-14 13:19:03

不明白

HELP= =

作者: wyy1998 时间: 2011-3-3 21:10:22

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

作者: aadxd 时间: 2011-3-3 21:12:48

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

作者: ZJY 时间: 2011-3-3 22:16:24

表示连题目都看不懂

欢迎光临魔方吧·中文魔方俱乐部 (http://bbs.mf8-china.com/)