曼哈頓網路

最小曼哈頓網路問題是復旦大學計算機學院朱洪教授給自己指導的本科生們所開設的題目。自2007年起，還是大一新生的郭澤宇，就開始和項目導師孫賀一起致力於最小曼哈頓網路問題算法和複雜性的研究。去年6月，郭澤宇受到復旦大學本科生學術研究資助計畫“莙政學者”項目的資助，在朱洪教授、博士研究生孫賀兩位項目指導老師的指導下開展學術研究。 最小Manhattan網路問題是近年來受到廣泛關注的計算幾何和組合最最佳化問題。在大規模集成！電路（VLSI）設計、分散式算法、計算生物學、網路設計、城市規劃等領域發揮著越來越大的作用。

基本介紹

• 中文名：曼哈頓網路
• 出處：復旦大學計算機學院
• 創始人：朱洪教授
• 套用：城市規劃、網路路由

簡介

復旦大學計算機學院三年級學生郭澤宇破解了一個猜想——根據曼哈頓城市地圖抽象出來的數學問題:最小曼哈頓網路問題。他的論文被計算幾何界最高層次的學術會議——第25屆計算幾何國際會議錄用,同時作為最佳論文被會議特刊約稿。

理論內容

給定平面上的一個點集，構造總長度。最小的網路,使得任意兩點之間都有長度最短的路徑相連——學者們給它起名“最小曼哈頓網路問題”。這十多年來,因證明計算極其複雜,這個“最小”只是猜想。

套用

最小曼哈頓網路問題在城市規劃、網路路由、大規模積體電路設計以及計算生物學等眾多領域有著很好的套用,但它是國際計算幾何領域沒有解決的“猜想”。

解釋

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

郭澤宇關於“最小曼哈頓網路問題”的論文被第25屆計算幾何國際會議錄用，文章同時作為了最佳論文之一被邀請投稿到會議特刊DiscreteandComputationalGeometry(DCG)。這意味著計算幾何領域Decades重要猜想被這位年僅20歲本科生成功解決。計算幾何國際會議是計算幾!何領域最高級別的會議，這一會議，中國內地數學家已經闊別了整整十八年。

曼哈頓網路-由於郭澤宇同學在香港大學的出色表現，錢玉麟教授對復旦大學的莙政學者計畫給出了很高的評價。他希望郭澤宇同學在下個學期繼續在香港大學作交流學生，與孫賀一起進行更加深入的研究。

這樣的做法無論在香港大學，還是在復旦大學；無論是交流學生，還是莙政學者的培養方式；都是沒有先例的。錢玉麟教授在前一階段為郭澤宇能夠留在香港大學作交流學生作了最大的努力，並且排除了郭澤宇留在香港大學的障礙。錢玉麟教授也與孫賀談，希望以香港大學工程學院副院長的身份向復旦大學的有關領導寫一封正式的邀請信，以表明香港大學官方的誠意和對這件事情的關心。

曼哈頓網路-曼哈頓網路的複雜度的研究取得重大進展

復旦停電檢修線路剛結束，我來到實驗室，打開電腦，就收到孫賀從香港發來的電子郵件。他向我報告，郭澤宇在香港大學的工作很出色，他和郭澤宇對曼哈頓網路的複雜度的研究取得重大進展。自曼哈頓網路的複雜度問題於1999年提出至今，沒有人知道問題的答案。因而使得對這一問題的研究成為計算幾何中最為重要的幾個未解決問題之一。在過去的半個月裡，經過他們和錢玉麟教授的仔細分析、檢驗證明，確信他們在國際上首先解決了這個難題。整個證明過程經過了反覆檢查，論文正在撰寫中，並準備投稿到計算幾何的頂級會議SoCG中。

思考探索

經過200多個日夜的思考和探索，這個十年未決的數學難題，竟然真的被郭澤宇和導師所破解。2008年11月末，郭澤宇和導師孫賀一起將論文投稿到由美國ACM學會主辦的第25屆計算幾何國際大會中。

This year2月13日清晨，大會程式委員會傳來喜訊：他們的論文在近170篇文章中脫穎而出，並作為最佳論文之一受邀向世界頂級期刊《離散與計算幾何》投稿。This year6月，在位於丹麥奧胡思大學湖岸劇院的第25屆計算幾何國際大會上，郭澤宇代表論文作者做了報告

具體內容

簡介

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

在該問題里，要求Manhattan網路里線段總長度最短，即以最小代價構造給定點集的Manhattan網路。此外，F. Lam等人在生物序列比對問題中套用Manhattan網路的近似算法，顯著減小搜尋空間。顯示最小Manhattan網路問題在計算生物學中的套用。由此可見，這一問題的研究無論在理論還是實際中都具有十分重要的意義。

提出

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

2009年6月復旦大學計算機學院大三學生郭澤宇關於“最小曼哈頓網路問題”的論文被第25屆計算幾何國際會議錄用，文章同時作為最佳論文之一被邀請投稿到會議特刊DiscreteandComputationalGeometry(DCG)。這意味著計算幾何領域Decades的重要猜想被這位年僅20歲的本科生成功解決。計算幾何國際會議為計算幾何領域最高級別的會議，這一會議，中國內地數學家已經闊別了整整十八年。

背景

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

2009年6月，被上海復旦大學僅20歲的本科生郭澤宇成功解決。他的關於“最小曼哈頓網路問題”的論文被第25屆計算幾何國際會議錄用，文章同時作為最佳論文之一被邀請投稿到會議特刊Discrete and Computational Geometry(DCG)。

問題

給定平面上一個點集T，其Manhattan網路由水平和垂直線段組成，並滿足T中任意兩點間在網路中存在曼哈頓路徑。可知曼哈頓網路即為L1-範數下給定點集的一個1-spanner。更一般的概念稱為geometric spanner或k-spanner，因其具有良好的性質，套用十分廣泛，就有鄰近問題（proximity problems）的求解、機器人運動規劃、通信網路的可靠性等等。

在本問題中，要求曼哈頓網路中線段總長度最短，即以最小的代價構造給定點集的曼哈頓網路。此外，F. Lam等人在生物序列比對問題中套用了曼哈頓網路的近似算法，顯著減小了搜尋空間。這顯示了最小曼哈頓網路問題在計算生物學中的套用。

解決

設計出具有更優近似度的近似算法

近似算法的設計方法主要包括：局部搜尋，線性規劃方法，原始對偶（primal-dual）方法等。本問題已知的近似算法可以分為兩類：一類方法是將全局最優網路問題規約為局部最優網路問題，再通過局部網路的組合達到全局的較優解，如M. Benkert 等人提出的3-近似算法。在這一方法的使用中，郭澤宇已取得了國際領先的成果。另一類則基於線性規劃方法，如V. Chepoi等人在文獻提出的2-近似算法。

在第一階段的研究中，一方面在已知的最好近似算法基礎上，對問題的性質進行更細緻地分析以嘗試改進；另一方面對近似算法的設計進行系統的學習，探索其他的算法設計思路。

研究問題所屬的複雜性類

儘管在過去的近十年里，最小曼哈頓網路問題[1]受到許多西方計算機科學家的重視，但是到目前為止，人們還不清楚這一問題是否存在多項式時間算法。人們猜想這一問題是NP-完全的，但到目前為止還沒有人給出有效的證明。

一般來講，證明一個問題是NP-完全的基本方式是將一已知的NP完全問題歸約到所研究的問題上。這方面，已知的NP-完全的計算幾何和組合最最佳化問題的歸約過程將具有很大參考價值。例如V. Chepoi在論文中提到的與最小曼哈頓網路問題相當類似的RSA問題，已經由W.Shi 和C. Su給出了從Planar-3-SAT問題到該問題的歸約，從而證明了該問題為NP-完全的。

因此，郭澤宇通過閱讀更多的計算幾何學NP-完全問題規約的文章，掌握各種複雜的技巧。試圖給出最小曼哈頓網路問題的類似的歸約方式，從而證明這一問題是NP-完全的。

困難

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

郭澤宇提出解決最小曼哈頓網路的算法複雜性NP難問題是不太現實的，但改善現有解決方案的效率或提高近似度是可行的研究方向，郭澤宇的結果是2-近似O(n2)時間複雜度。能否將效率提高到O(nlogn)，與3-近似方法相同？或提出1.5-近似的新方法是亟待解決的新問題。

進展

復旦大學2009年6月21日傳來訊息，該校計算機學院大三學生郭澤宇關於最小曼哈頓網路問題的論文被美國ACM學會主辦的第25屆計算幾何國際會議錄用，文章同時作為最佳論文之一被邀請投稿到會議特刊(DCG)。

這意味著計算幾何領域十餘年來未決的重要猜想被這位年僅20歲的本科生成功解決。

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

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

成就

在算法研究領域，人們最重視的是那些長期懸而未決的問題。“曼哈頓網路問題”就是這樣一個不清楚它是否是P還是NP的問題。已經有近似度為2的近似算法，但是複雜度為O(n^8)。而郭澤宇把算法改造。使之加快到O(n^2)，是值得讚許的工作。所以被接受為國際會議大會報告，反映了同行對它的重視程度。

曼哈頓網路問題是計算機理論界研究的重要課題，郭澤宇對最小曼哈頓網路的算法複雜性進行研究，有理論意義和套用價值。鑒於曼哈頓網路問題是否NP問題尚無明確的結論，對曼哈頓網路問題的研究都集中在近似算法的研究。郭澤宇在導師指導下的前期工作對已有的2-近似算法進行改進，使其時間複雜度達到O(n2)(原算法為O(n8))，課題有很好的研究基礎，有望得到進一步的創新成果。

最小曼哈頓網路問題-郭澤宇怎么解決最小曼哈頓網路問題？

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

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

項目

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

該課題在城市規劃、網路路由、大規模積體電路設計以及計算生物學等眾多領域有著很好的套用前景。不過自曼哈頓網路的複雜度問題於1999年提出至今，沒有人知道問題的答案，從而使得對這一問題的研究成為計算幾何中最為重要的幾個未解決問題之一。

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

領域

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