打破30年困局！澳大這在線匹配研究可用於滴滴拼車

澳門大學學者一項關於在線匹配的研究提出了一個可廣泛應用於現今社會的新模型，如滴滴拼車、房東租客匹配等，成爲過去30年來有關問題的唯一突破性進展。研究獲國際計算機協會的ACM期刊刊登，是過去十年澳門地區發表於該期刊的第一篇文章。

澳大科技學院電腦及資訊科學系助理教授及智慧城市物聯網國家重點實驗室成員吳曉偉的論文《全面線上配對》（Fully Online Matching）發表在最新一期的ACM期刊。該期刊只登載那些對計算機科學有深遠影響的論文，過去十年總收錄文章不足400篇，其中15篇來自中國（包括港澳台）地區，是公認的理論計算機科學領域中最頂尖的期刊。

是次研究考慮了計算機圖靈獎獲得者Karp等人於1990年計算理論研討會發表的文章，是當中提出的二分圖在線匹配問題的一個擴展。吳曉偉將經典KVV模型拓展到任意（非二分）圖中並且允許所有點在綫出現，找出了能應用於現今社會、可產生廣泛應用的新模型，如滴滴拼車、房東租客匹配等不適用於KVV模型的場景；研究還提出了該問題的數個理論保障，成爲過去30年來關於Karp等人提出的任意圖在綫匹配問題的唯一突破性進展。

吳曉偉於2015年獲得香港大學計算機科學博士學位，及後於維也納大學擔任博士後研究員。他的研究方向主要是計算機科學理論、在線算法、近似算法、動態數據結構、城市大數據與智能技術等。

更多精彩內容：

編輯：李巧雲

~歡迎轉載‧註明出處~