郭澤宇[最小曼哈頓網路問題的破解者]

2009年6月22日上海訊息，復旦大學計算機學院三年級學生郭澤宇破解了一個世界級猜想——曼哈頓城市地圖抽象出來的數學問題：最小曼哈頓網路問題。

基本信息

• 中文名：郭澤宇
• 性別：男
• 民族：漢族
• 國籍：中國
• 畢業院校：復旦大學

個人簡歷

高中：2003年-2006年就讀於邢台一中高三1班。

班長：宋鵬超 。班主任：韓春山老師。英語老師：肖愛省。化學老師：李紅

大學：於2006年被復旦大學錄取。

郭澤宇，復旦大學學生，2009年6月21日該校傳來訊息，計算機學院大三學生郭澤宇關於最小曼哈頓網路問題的論文被美國ACM學會主辦的第25屆計算幾何國際會議錄用，文章同時作為最佳論文之一被邀請投稿到會議特刊(DCG)。 這意味著計算幾何領域十餘年來未決的重要猜想被這位年僅20歲的本科生成功解決。

郭澤宇中學就讀於邢台一中，曾是河北省NOI隊隊員，在NOI2005鄭州比賽現場被復旦大學錄取。導師為李文老師。

人物事件

攻克“最小曼哈頓網路問題”

復旦大學2009年6月21日傳來訊息，該校計算機學院大三學生郭澤宇關於最小曼哈頓網路問題的論文被美國ACM學會主辦的第25屆計算幾何國際會議錄用，文章同時作為最佳論文之一被邀請投稿到會議特刊(DCG)。 這意味著計算幾何領域十餘年來未決的重要猜想被這位年僅20歲的本科生成功解決。

最小曼哈頓網路問題是計算機學院朱洪教授給自己指導的本科生們所開設的題目。

最小曼哈頓網路問題

什麼是最小曼哈頓網路問題？

郭澤宇[最小曼哈頓網路問題的破解者]

最小Manhattan網路問題是近年來受到廣泛關注的計算幾何和組合最最佳化問題。在大規模積體電路（VLSI）設計、分散式算法、計算生物學、網路設計、城市規劃等領域發揮著越來越大的作用。

給定平面上一個點集T，其Manhattan網路由水平和垂直線段組成，並滿足T中任意兩點間在網路中存在Manhattan路徑。可知Manhattan網路即為L1-範數下給定點集的一個1-spanner。更一般的概念稱作geometric spanner或k-spanner，由於具有良好的性質，其套用十分廣泛，包括鄰近問題（proximity problems）的求解、機器人的運動規劃、通信網路的可靠性等等。在本問題中，要求Manhattan網路中線段總長度最短，即以最小的代價構造給定點集的Manhattan網路。此外，F. Lam [5] 等人在生物序列比對問題中套用了Manhattan網路的近似算法，顯著減小了搜尋空間。這顯示了最小Manhattan網路問題在計算生物學中的套用。

由此可見，這一問題的研究無論在理論還是實際中都有十分重要的意義。

最小Manhattan網路問題由J. Gudmundsson, C. Levcopoulos和G. Narasimhan [4] 於1999年最早提出。之後，許多學者研究並給出了這一問題多項式時間近似算法。之前通過組合方法設計的最佳近似算法（3-近似）由M. Benkert [1] 等人在2004年給出。2005年，V. Chepoi [2] 等人提出了基於線性規劃的2-近似算法，這是目前所知關於這一問題的最好近似度。

在過去半年的研究中，我在朱洪教授的指導下得到了該問題的2-近似算法。這一結果被國際學術會議AAIM接受，同時獲得了審稿人的好評。在此之前，同一近似度的算法（V. Chepoi [2], 2005）的時間複雜度高達Ω(n^8)，而我們的算法時間複雜度僅為O(n^2)。此外，我們在這一問題的算法的設計和證明中首次套用了由D. E. Knuth和F. F. Yao [3] 提出的動態規劃加速方法，將動態規划過程的時間複雜度由O(n^3)降低到O(n^2)。

迄今為止，最小 Manhattan 網路問題的是否NP-難問題仍屬未知，其不可近似性亦不清楚。因此，研究這一問題所屬的複雜性類將具有極大的理論意義和實際價值。

怎么解決最小曼哈頓網路問題

2008年6月，郭澤宇申請了復旦大學本科生學術研究資助計畫的“莙政”項目。最小曼哈頓網路問題是計算機學院朱洪教授給自己指導的本科生們所開設的題目。

郭澤宇大膽地選擇了這一問題作為項目攻克對象。這既讓朱洪教授和博士研究生孫賀這兩位項目指導老師感到欣喜，也讓“莙政”學者評審專家們捏了一把汗。基於鼓勵本科生創新和支持年輕人闖勁的考慮，郭澤宇最終得到了資助。經過200多個日夜的思考和探索，這一難題終於被他找到突破口。

據悉，計算幾何國際會議是計算幾何領域最高級別的會議，這一會議，中國內地數學家已經闊別了整整十八年。

在郭澤宇的項目申請書中，中國科學院院士陸汝鈐作為推薦老師，對本科生學術研究資助計畫給予了充分的肯定，他認為通過這一方式使許多學生脫穎而出，走上了從事科學研究的道路。記者了解到，1998年，在李政道先生倡導和設立的“莙政基金”支持下，復旦大學開始開展資助優秀本科學生儘早接觸學術研究的計畫，並逐漸形成了一個層次分明、申請時間靈活、申請形式多樣的本科生學術研究資助平台，即復旦大學本科生學術研究資助計畫。

從1998年到2008年，共有1556位學生獲得資助開展研究，其項目學科涵蓋了醫學、工學、理學、文學、教育學等多個領域。另據不完全統計，在2008年，參加復旦大學本科生學術研究資助計畫資助項目的同學在國內外期刊發表論文30篇，其中第一作者文章20篇。