学术活动
您当前的位置:>学术活动
学术活动
法国亚眠大学李初民教授应邀作学术报告
更新:2017-08-24 10:08:10阅读:1307人次

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次。