法國亞眠大學李初民教授應邀作學術報告

更新:2017-08-24 10:08:10 閱讀:人次

713號下午3點,法國亞眠大學李初民教授應華中科技大學計算機學院何琨教授的邀請在南一樓423會議廳作了題爲Incrementality in Exact NP-hard Problem Solving的學術報告。

李初民教授的報告主要講述了漸增式方法在求解NP難問題中的應用。經典的NP難問題求解擁有億個變元的工業問題時,計算代價非常高。完備算法在可接受時間內很難找到問題的解。漸增式求解方法通過累積求解過程中,可用的中間計算結果,以達到有效地縮短計算時間的目標。李初民教授首先以經典的SAT問題求解方法--沖突驅動子句學習技術爲例。提出對表示沖突搜索中間結果的學習子句進行文字優化,消除非決定性原因的文字,從而引導搜索樹更加緊湊。接著,李教授介紹了漸增式方法在最大團問題中的應用。提出將搜索分支下的候選圖頂點依次添加到K個(最大團的當前最優解)獨立集中,直至頂點不能添加爲止。未進入到獨立集中的頂點將是後續分支的候選頂點。爲了提高獨立集的質量,進而提出漸進式MaxSAT推理方法。在當前最大團最優解的基礎上,計算當前待搜索的空間,並使用漸進式MaxSAT推理,逐步縮小上界,提高了搜索的效率。最後,李教授和同學們一起探討了漸增式方法使用的時機,優化方法等問題。

李初民教授是1983年于华中理工大学计算机系获工学學士學位,1985年和1990年于法國貢比涅大學(Universityof Technology of Compiegne)計算機系分別獲工學碩士和工學博士學位。現任法國皮卡第儒勒-凡爾納大學(University of Picardie Jules Verne)計算機系教授,法國科技部傑出科研獎獲得者。在國際上首次提出了能用于現實求解SAT問題的完備算法,並被後續的研究者大量引用。參與編寫著作3部。在國際學術期刊和會議上發表高水平論文100余篇,在人工智能领域的顶尖學術會議AAAIIJCAI上發表8篇學術論文,Google學術引用近3000次。

學術交流

Directory