基本介紹中文名:最小曼哈頓網絡問題由j .古德蒙德松、c .列夫科普洛斯和g .納拉西姆漢提出:1999？適用範圍:簡述網絡設計和城市規劃，歷史、背景、問題、解決方案、困難、進展和成就，簡述給定平面上的壹個點集T，其曼哈頓網絡由水平和垂直線段組成，滿足T中任意兩點之間的網絡中存在曼哈頓路徑的要求，已知曼哈頓網絡是L1-範數下給定點集的1-扳手。更壹般的概念叫做幾何扳手或k型扳手。由於其良好的性質，其應用非常廣泛，包括其鄰近問題的解決、機器人運動規劃、通信網絡的可靠性等。在這個問題中，要求曼哈頓網絡中線段的總長度最短，即以最小的代價構造給定點集的曼哈頓網絡。此外，F. Lam等人在生物序列比對問題中應用了曼哈頓網絡的近似算法，顯著縮小了搜索空間。這說明了最小曼哈頓網絡問題在計算生物學中的應用。因此，對這壹問題的研究具有重要的理論和實踐意義。史上最小曼哈頓網絡問題是1999提出的世界級計算幾何的重要猜想。在1999年，j .古德蒙德松、c .列夫科普洛斯和g .納拉西姆漢首先提出了最小曼哈頓網絡問題。此後，許多學者研究並給出了該問題的多項式時間近似算法。用組合方法設計的最佳逼近算法(3-逼近)是M. Benkert等人在2004年給出的。2005年，V. Chepoi等人提出了基於線性規劃的2-近似算法，這是目前已知的最佳近似。2009年6月，復旦大學計算機學院大三學生郭澤宇因“最小曼哈頓網絡問題”論文被第25屆國際計算幾何大會錄用。同時，作為最佳論文之壹，該論文被邀請為會議特刊《離散計算幾何》(DCG)投稿。意味著計算幾何中來自十年的重要猜想被這個20歲的本科生成功解決。計算幾何國際會議是計算幾何領域最高級別的會議，距離中國大陸的數學家離開已經過去了18年。最小背景曼哈頓網絡問題是1999提出的世界級計算幾何的重要猜想。在1999年，j .古德蒙德松、c .列夫科普洛斯和g .納拉西姆漢首先提出了最小曼哈頓網絡問題。此後，許多學者研究並給出了該問題的多項式時間近似算法。用前面的組合方法設計的最佳逼近算法(3-逼近)是M. Benkert等人在2004年給出的。2005年，V. Chepoi等人提出了壹種基於線性規劃的2-近似算法，這是已知的該問題的最佳近似。2009年6月，它被上海復旦大學20歲的本科生郭澤宇成功解決。他關於“最小曼哈頓網絡問題”的論文被第25屆計算幾何國際會議接受，並作為最佳論文之壹，被邀請向會議特刊《離散與計算幾何》(DCG)投稿。給定平面上的點集T的曼哈頓網由水平和垂直線段組成，它滿足T中任意兩點之間存在曼哈頓路，已知曼哈頓網是給定點集在L1-範數下的1-扳手。更壹般的概念叫做幾何扳手或k型扳手。由於其良好的性質，它有著廣泛的應用，包括鄰近問題的解決、機器人的運動規劃、通信網絡的可靠性等。在這個問題中，要求曼哈頓網絡中線段的總長度最短，即以最小的代價構造給定點集的曼哈頓網絡。此外，F. Lam等人在生物序列比對問題中應用了曼哈頓網絡的近似算法，顯著縮小了搜索空間。這說明了最小曼哈頓網絡問題在計算生物學中的應用。解決方法是設計壹個逼近度更好的逼近算法。近似算法的設計方法主要有:局部搜索法、線性規劃法、原對偶法等。已知的該問題的近似算法可分為兩類:壹類是將全局最優網絡問題化簡為局部最優網絡問題，然後通過局部網絡的組合達到全局最優解，如M. Benkert等人提出的3-近似算法。在這壹方法的運用上，郭澤宇取得了國際領先的成果。另壹種是基於線性規劃方法，如文獻中V. Chepoi等人提出的2-逼近算法。在研究的第壹階段，壹方面，在已知最佳逼近算法的基礎上，詳細分析問題的本質，試圖對其進行改進；另壹方面，系統研究近似算法的設計，探索其他算法設計思路。問題復雜性的研究雖然最小曼哈頓網絡問題在過去的十年裏吸引了許多西方計算機科學家的註意，但目前尚不清楚該問題是否存在多項式時間算法。人們懷疑這個問題是NP完全的，但至今沒有人給出壹個有效的證明。壹般來說，證明壹個問題是NP完全的基本方法是把壹個已知的NP完全問題化簡為所研究的問題。在這方面，已知的NP完全計算幾何和組合優化問題的約簡過程將有很大的參考價值。例如V. Chepoi在論文中提到的RSA問題與最小曼哈頓網絡問題頗為相似，W.Shi和C. Su已經給出了從Planar-3-SAT問題到這個問題的歸約，從而證明了這個問題是NP完全的。所以郭澤宇通過多讀計算幾何中NP-完全問題規範的文章，掌握了各種復雜的技巧。本文試圖對最小曼哈頓網絡問題給出壹個類似的約簡方法，從而證明這個問題是NP完全的。難度最小的曼哈頓網絡問題是否是NP- hard還是未知數，其非近似性也不明確。因此，研究這壹問題的復雜性範疇將具有重要的理論意義和實用價值。郭澤宇要解決最小曼哈頓網絡算法復雜度的NP-hard問題是不現實的，但提高現有解的效率或提高近似度是可行的研究方向。郭澤宇的結果是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-hard尚無明確結論，對曼哈頓網絡問題的研究主要集中在近似算法上。郭澤宇之前在導師的指導下對現有的2-逼近算法進行了改進，使其時間復雜度達到O(n2)(原算法為O(n8))。該課題具有良好的研究基礎，有望獲得進壹步的創新成果。最小曼哈頓網絡問題——郭澤宇如何解決最小曼哈頓網絡問題？2008年6月，郭澤宇申請了復旦大學本科生學術研究資助項目“鄭錚”項目。最小曼哈頓網絡問題是計算機學院的朱宏教授給他的本科生出的題目。郭澤宇大膽地選擇了這個問題作為課題的研究對象。這不僅讓朱宏教授和博士生孫鶴兩位項目導師高興，也讓“鄭錚”學者的專家們捏了壹把汗。基於鼓勵本科生創新，支持年輕人創業的考慮，最終資助了郭澤宇。經過200多個日日夜夜的思考和探索，他終於在這個難題上找到了突破口。據悉，計算幾何國際會議是計算幾何領域最高級別的會議，已遠離中國數學家18年。在郭澤宇的項目申報中，中科院院士盧如謙作為推薦教師，對本科生學術研究資助方案給予了充分肯定。他相信很多學生通過這種方式脫穎而出，走上了科研之路。記者了解到，1998在李政道先生發起並設立的“鄭錚基金”的支持下，復旦大學開始資助優秀本科生盡快接觸學術研究，並逐步形成了壹個定義明確、申請時間靈活、申請形式多樣的本科生學術研究資助平臺，即復旦大學本科生學術研究資助計劃。從1998到2008年，資助了* * 1556名學生開展研究，他們的項目學科涵蓋了醫學、工程、科學、文學、教育等多個領域。據不完全統計，2008年參加復旦大學本科生學術研究資助項目的學生在國內外期刊上發表論文30篇，其中第壹作者20篇。