| 主页 | 频道首页 | 本站地图 | 论坛留言 | 合作联系 | 本站消息 | |
科技动态 技术发展 文化研究 生物生态 人的研究 生命起源 基因工程 科学普及 科学探索 专题其他

复旦学生破解最小曼哈顿网络问题

2009-06-23
最小曼哈顿网络问题,最小曼哈顿,曼哈顿难题,最小曼哈顿网络
复旦学生破解最小曼哈顿网络问题

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

复旦大三学生破解世界级几何猜想,几何领域十余年未解难题一朝攻克
2009.06.23 新闻晨报通讯员 罗 倩 记者 林颖颖

晨报讯 近日,复旦大学计算机学院大三学生郭泽宇关于最小曼哈顿网络问题的论文被美国ACM学会主办的第25届计算几何国际会议录用,这意味着计算几何领域十余年来未解的重要猜想被这位年仅20岁的本科生成功解决。据悉,计算几何国际会议是计算几何领域最高级别的会议,这一会议,中国大陆数学家已经阔别了整整十八年。

据悉,2008年6月,郭泽宇申请了复旦大学本科生学术研究资助计划中的“莙政学者”项目。最小曼哈顿网络问题是计算机学院朱洪教授给自己指导的本科生所开设的题目,在城市规划、网络路由、大规模集成电路设计以及计算生物学等众多领域有着很好的应用,郭泽宇大胆地选择了这一问题作为项目攻克对象,既让朱洪教授和博士研究生孙贺这两位项目指导老师感到欣喜,也让“莙政学者”评审专家捏了一把汗。基于鼓励本科生创新和支持年轻人的闯劲的考虑,郭泽宇最终得到了“莙政学者”的资助。经过200多个日夜的思考和探索,这个十余年未解的难题终于被他所破解。在项目结题书中,评审专家这样写道:该项目达到了“莙政学者”资助项目中非常高的水平。

记者了解到,从1998年至2008年,复旦共有1556名学生获得资助开展研究,其项目学科涵盖了医学、工学、理学、文学、教育学等多个领域。另据不完全统计,2008年参加复旦大学本科生学术研究资助计划资助项目的同学在国内外期刊发表论文30篇,其中第一作者文章20篇。郭泽宇的成功也代表着复旦大学本科生学术研究资助计划取得了更新的成果。

后记:

复旦总出些牛人,这个应该和前几年南京大学出的那个有区别的吧,记得复旦以前出了个大一学生考物理出国第一,让谢希德校长说30年一遇,但是这个的研究能力应该高于那人.

其实很多东西如果在原来的体系内奋斗,倒不如换个角度思路去反而更容易解决.

最小曼哈顿网络问题补充资料:

根据曼哈顿城市地图抽象出来的数学问题:最小曼哈顿网络问题。“利用给定平面上的一个点集,构造总长度最小的网络,使得任意两点之间都有长度最短的路径相连”———最小的网络,使得任意两点之间都有长度最短的路径相连.最小曼哈顿网络问题(the minimum manhattan network problem),是近年来受到广泛关注的计算几何和组合最优化问题。

“曼哈顿难题”不仅是一个数学领域的技术“难关”,其应用价值同样巨大,无论对城市规划、网络路由、大规模集成电路设计还是在计算生物学等众多前沿领域,都有着重要意义。在日前举行的第25届计算几何国际大会上,两位中国年轻人受邀讲解其最小曼哈顿网络问题算法和复杂性的研究。郭泽宇仅用20分钟就展现了证明轮廓,不少与会代表为其论文中所展现出的对问题罕见的洞察力、复杂巧妙的证明而惊叹。

最小曼哈顿网络问题具体是个什么问题?最小曼哈顿网络问题是什么

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

  自2007年起,郭泽宇和孙贺就开始致力于最小曼哈顿网络问题算法和复杂性的研究。去年6月,郭泽宇受到复旦大学本科生学术研究资助计划“莙政学者”项目的资助,在孙贺的指导下开展学术研究。到2008年,他们先后给出了目前为止最简单的算法。2008年11月末,他们将论文投稿到第25届计算几何国际大会中。今年2月13日清晨,大会程序委员会传来喜讯:他们的论文在近170篇文章中脱颖而出,并作为最佳论文之一受邀向世界顶级期刊《离散与计算几何》投稿。
复旦学生破解最小曼哈顿网络问题
人体内艾滋病病毒藏身处被发现
上海专家在沪育出猪万能干细胞
学术刊物收版面费刊登被指敛财
曾获诺贝尔奖百岁女科学家仍在工作
美国教授掌握水变油技术是真的吗
有钱能使科学家“推磨”吗
神经细胞内新发现纳米级滤网
千余科学家写报告警告人类生存岌岌可危
美国鸟类专家称通过卫星找到拉登的藏身地
美俄卫星太空相撞
我国科学家成功克隆人类囊胚
我国女性人文社科学者过少
改变地球的十大绿色畅想
五十年科学的魅力长青
《时代》评出2008年十大科学发现
未来20年人类“杀手”座次有变
美十大业余科学家揭晓:有望攻克癌症
科技动态1 科技动态2 科技动态

本栏目主要介绍最新科技发展动态方面,包括最新的现代科学研究成果、现代科技方向、现代科学技术动态、复旦学生破解最小曼哈顿网络问题等。特别关注有关人与文化的价值方面的研究。

『科学频道首页』 『本栏页首』 『关闭窗口』