魔方吧·中文魔方俱乐部

 找回密码
 注册
搜索
热搜: 魔方
查看: 1125528|回复: 30

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

透魔

米糕咪够咯。。。。。。

Rank: 6Rank: 6

积分
6923
帖子
1462
精华
4
UID
52005
性别
发表于 2009-6-26 12:44:38 |显示全部楼层
( 以下信息整理于网络新闻。 )

上海复旦大学计算机学院的一名大三学生近日竟然破解了世界级猜想的消息,在全国引起了很大的轰动。
这个引起全世界最出色的数学家、计算机学家惊叹的天才大学生,名叫郭泽宇,是河北省邢台市人,今年只有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 编辑 ]
已有 1 人评分经验 收起 理由
sokoban + 10 有点意思

总评分: 经验 + 10   查看全部评分

Rank: 2

积分
318
帖子
317
精华
0
UID
95902
性别
保密
发表于 2009-6-26 12:49:04 |显示全部楼层
沙发。。顺便说句强!!!!!中国人确实非常聪明!

使用道具 举报

红魔

噗噜噜

Rank: 4

积分
1290
帖子
1110
精华
0
UID
59598
性别

两年元老 四年元老 十年元老

发表于 2009-6-26 13:00:16 |显示全部楼层
非常 强大啊



天下大乱
闭市中..

使用道具 举报

红魔

All Blue

Rank: 4

积分
1196
帖子
999
精华
2
UID
38845
性别
发表于 2009-6-26 13:06:10 |显示全部楼层
很強,頂,為中國爭光了
只是看不懂是最大遺憾
公式D F2 U L2 U B2 U R2 U R' F2 R L U L' R' U R L' U L U L U2 L' U' L U2 L'
数列11121131221231321332223233311

使用道具 举报

Rank: 4

积分
1029
帖子
158
精华
0
UID
59021
性别
保密
发表于 2009-6-26 13:15:59 |显示全部楼层
太強
問題都看不明白...
有人解釋一下嗎- -

使用道具 举报

透魔

有空了学学4D二阶

Rank: 6Rank: 6

积分
5924
帖子
3936
精华
0
UID
1290
兴趣爱好
结构
理论

魔方破解达人 八年元老

发表于 2009-6-26 13:20:09 |显示全部楼层
呵呵顶一个!为国争光了啊~~

使用道具 举报

粉魔

成都千奇百怪的助手

Rank: 5Rank: 5

积分
3240
帖子
2645
精华
5
UID
25456
性别

六年元老

发表于 2009-6-26 13:31:24 |显示全部楼层
这个问题不是一般人能看懂的啊,头晕了
千奇百怪润智QQ群39440516。四川魔方群15545617。
点击进入我的视频:http://u.youku.com/xdgtzsyyj
http://shop34170148.taobao.com/

使用道具 举报

Rank: 2

积分
309
帖子
308
精华
0
UID
97095
性别
发表于 2009-6-26 13:55:01 |显示全部楼层
真强大~!骄傲~!!!

使用道具 举报

Rank: 2

积分
299
帖子
248
精华
1
UID
98716
性别
保密
发表于 2009-6-26 14:11:20 |显示全部楼层
句强!!!!!中国人确实非常聪明!

使用道具 举报

Rank: 1

积分
144
帖子
96
精华
0
UID
68894
性别
保密
发表于 2009-6-26 14:31:45 |显示全部楼层
厉害,厉害,佩服佩服。中华人才辈出啊

使用道具 举报

您需要登录后才可以回帖 登录 | 注册

Archiver|手机版|魔方吧·中文魔方俱乐部

GMT+8, 2024-3-29 21:15

Powered by Discuz! X2

© 2001-2011 Comsenz Inc.

回顶部