2009年6月22日上海市消息，復旦大學計算機學院三年級學生郭澤宇破解了一個世界級猜想——曼哈頓城市地圖抽象出來的數學問題：最小曼哈頓網絡問題。
個人簡歷
班長：宋鵬超。班主任：韓春山老師。英語老師：肖愛省。化學老師：李紅
大學：于2006年被復旦大學錄取。
郭澤宇，復旦大學學生，2009年6月21日該校傳來消息，計算機學院大三學生郭澤宇關于最小曼哈頓網絡問題的論文被美國ACM學會主辦的第25屆計算幾何國際會議錄用。
郭澤宇中學就讀于邢臺一中，曾是河北省NOI隊隊員，在NOI2005鄭州市比賽現場被復旦大學錄取。導師為李文老師。
人物事件
攻克“最小曼哈頓網絡問題”
復旦大學2009年6月21日傳來消息，該校計算機學院大三學生郭澤宇關于最小曼哈頓網絡問題的論文被美國ACM學會主辦的第25屆計算幾何國際會議錄用，文章同時作為最佳論文之一被邀請投稿到會議特刊(DCG)。這意味著計算幾何領域十余年來未決的重要猜想被這位年僅20歲的本科生成功解決。
最小曼哈頓網絡問題是計算機學院朱洪教授給自己指導的本科生們所開設的題目。
最小曼哈頓網絡問題
什么是最小曼哈頓網絡問題？
最小Manhattan網絡問題是近年來受到廣泛關注的計算幾何和組合最優化問題。在大規模集成電路（VLSI）設計、分布式算法、計算生物學、網絡設計、城市規劃等領域發揮著越來越大的作用。
給定平面上一個點集T，其Manhattan網絡由水平和垂直線段組成，并滿足T中任意兩點間在網絡中存在Manhattan路徑?？芍狹anhattan網絡即為L1-范數下給定點集的一個1-spanner。更一般的概念稱作geometric spanner或k-spanner，由于具有良好的性質，其應用十分廣泛，包括鄰近問題（proximity problems）的求解、機器人的運動規劃、通信網絡的可靠性等等。在本問題中，要求Manhattan網絡中線段總長度最短，即以最小的代價構造給定點集的Manhattan網絡。此外，F. Lam 等人在生物序列比對問題中應用了Manhattan網絡的近似算法，顯著減小了搜索空間。這顯示了最小Manhattan網絡問題在計算生物學中的應用。
由此可見，這一問題的研究無論在理論還是實際中都有十分重要的意義。
最小Manhattan網絡問題由J. Gudmundsson, C. Levcopoulos和G. Narasimhan 于1999年最早提出。之后，許多學者研究并給出了這一問題多項式時間近似算法。之前通過組合方法設計的最佳近似算法（3-近似）由M. Benkert 等人在2004年給出。2005年，V. Chepoi 等人提出了基于線性規劃的2-近似算法，這是目前所知關于這一問題的最好近似度。
在過去半年的研究中，我在朱洪教授的指導下得到了該問題的2-近似算法。這一結果被國際學術會議AAIM接受，同時獲得了審稿人的好評。在此之前，同一近似度的算法（V. Chepoi , 2005）的時間復雜度高達Ω(n^8)，而我們的算法時間復雜度僅為O(n^2)。此外，我們在這一問題的算法的設計和證明中首次應用了由D. E. 高德納和F. F. Yao 提出的動態規劃加速方法，將動態規劃過程的時間復雜度由O(n^3)降低到O(n^2)。
迄今為止，最小 Manhattan 網絡問題的是否NP-難問題仍屬未知，其不可近似性亦不清楚。因此，研究這一問題所屬的復雜性類將具有極大的理論意義和實際價值。
怎么解決最小曼哈頓網絡問題
2008年6月，郭澤宇申請了復旦大學本科生學術研究資助計劃的“政”項目。最小曼哈頓網絡問題是計算機學院朱洪教授給自己指導的本科生們所開設的題目。
郭澤宇大膽地選擇了這一問題作為項目攻克對象。這既讓朱洪教授和博士研究生孫賀這兩位項目指導老師感到欣喜，也讓“莙政”學者評審專家們捏了一把汗?；诠膭畋究粕鷦撔潞椭С帜贻p人闖勁的考慮，郭澤宇最終得到了資助。經過200多個日夜的思考和探索，這一難題終于被他找到突破口。
據悉，計算幾何國際會議是計算幾何領域最高級別的會議，這一會議，中國內地數學家已經闊別了整整十八年。
在郭澤宇的項目申請書中，中國科學院院士陸汝鈐作為推薦老師，對本科生學術研究資助計劃給予了充分的肯定，他認為通過這一方式使許多學生脫穎而出，走上了從事科學研究的道路。記者了解到，1998年，在李政道先生倡導和設立的“莙政基金”支持下，復旦大學開始開展資助優秀本科學生盡早接觸學術研究的計劃，并逐漸形成了一個層次分明、申請時間靈活、申請形式多樣的本科生學術研究資助平臺，即復旦大學本科生學術研究資助計劃。
從1998年到2008年，共有1556位學生獲得資助開展研究，其項目學科涵蓋了醫學、工學、理學、文學、教育學等多個領域。另據不完全統計，在2008年，參加復旦大學本科生學術研究資助計劃資助項目的同學在國內外期刊發表論文30篇，其中第一作者文章20篇。
參考資料 >