神马文学网大公網
来源：百度文库 编辑：神马文学网 时间：2024/04/28 20:38:36
年僅20歲的復旦大學大三學生郭澤宇和25歲的博士研究生孫賀共同完成的關於「最小曼哈頓網絡問題算法和複雜性」的論文，近日被第25屆計算幾何國際大會（SCG）錄用，並受邀出席大會並報告。這意味著計算幾何領域這十年未決的重要問題，由這兩位年輕人成功解決。而此前，中國大陸研究機構闊別SCG大會講台也已經18年。【本報記者張帆上海二十二日電】
在位於丹麥奧胡思大學湖岸劇院的第25屆計算幾何國際大會上，郭澤宇代表論文作者做了大會報告，報告題目是最小曼哈頓網絡是NP-C。「給定平面上的一個點集，構造總長度最小的網絡，使得任意兩點之間都有長度最短的路徑相連」，這一根據曼哈頓城市地圖而抽象出來的數學問題，被稱作「最小曼哈頓網絡問題」，該問題在城市規劃、網絡路由、大規模集成電路設計以及計算生物學等眾多領域有著很好的應用。
上世紀90年代，西方學者Levcopoulos等人提出了最小曼哈頓網絡設計的三個重要問題，而其中最為關鍵的即是確定這一問題的計算複雜性類。
鼓勵支持年輕人「闖勁」
在是次大會上，面對全世界最出色的數學家、理論計算機科學家和圖像處理的專家，以及11年前提出這一難題的Levcopoulos，郭澤宇用僅有的20分鐘展現了他們解決這一世界難題的證明輪廓。
來自復旦大學的資料顯示，自2007年起，郭澤宇和孫賀就開始致力於「最小曼哈頓網絡問題算法和複雜性」的研究。當時，國際主流數學家對這個難題沒有找到有效的解決途徑，沒有人相信這兩位年輕人會攻克這一難題，但基於鼓勵本科生創新和支持年輕人「闖勁」的考慮，郭澤宇最終得到了「莙政學者」的資助，並批准在讀博士生孫賀擔任其導師，這開了莙政基金和此類大學生學術資助項目的先河。
從去年4月到10月，整整200天。無論在導師孫賀的辦公室內，在貴陽暑期學校的散步中，還是在赴香港大學共同訪問的火車上，這一問題無不縈繞在兩個人的腦海中。「經常是兩個人各自拿一張紙，只是想著解決辦法，四個小時下來兩人一言不發」，孫賀這樣回憶到，這一國際難題陪伴他們度過了無數深夜。
論文脫穎而出被錄取
漫長的思考換來了靈感的閃現，經過200多個晝夜的思考和探索，這十年未決的難題終於被他們所破解。他們將所有的證明細節重新整理，並繪製證明中所需要的每一幅插圖。
到去年11月底，他們將論文投稿到第25屆計算幾何國際大會，最終，兩位年輕人不負眾望，他們的論文在近170篇文章中脫穎而出，被大會錄取，並作為最佳論文之一應邀投稿到世界頂級期刊《離散與計算幾何》中。而在「莙政學者」的項目結題書中，評審專家們這樣評價道：該項目達到了「莙政學者」資助項目中非常高的水平。當時，他們分別只有19歲和24歲。