最小曼哈顿网络问题的成就

发布网友发布时间：2022-04-28 20:59

共1个回答

热心网友时间：2022-06-23 04:32

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