当前位置: 首页>>教学科研>>正文

我院举办“影山大讲堂”之科技创新大讲堂(总第27讲)

2019年4月1日下午,“影山大讲堂”之科技创新大讲堂(总第27讲)在7101报告厅举行,中科院软件所博士生导师蔡少伟研究员作题为《局部搜索与可满足性问题》的讲座,中科院软件所林锦坤博士作题为《大规模实例上的图着色问题求解算法》的报告。报告由数学与统计学院院长严忠权教授主持,各二级学院师生代表200余人到场聆听。

蔡少伟研究员现年32岁,是中国科学院大学岗位教授、博士生导师,中国科学院软件所杰出青年基金获得者,北京大学计算机软件与理论专业和澳大利亚格里菲斯大学应用数学专业双博士。他的主要研究领域包括:组合优化问题求解、逻辑问题求解、启发式算法、基于学习的自动算法设计等。现已发表论文52篇,其中CCF-A类26篇,10余篇论文发表在人工智能顶级期刊Artificial Intelligence (AIJ)、Journal of Artificial Intelligence Research、ACM/IEEE顶级汇刊上。Google Scholar引用约1000次,H因子为19,其中2015年发表在AIJ上的论文被AIJ评为“The most cited articles published since 2011”。他曾获得国际SAT/MaxSAT比赛多次冠军,提出的格局检测方法被国际同行广泛使用,被用于求解十多种组合优化问题。研究成果获国际学者包括多个ACM/IEEE/AAAI Fellows在论文中高度评价为“最前沿算法”“代表性算法”“最好的算法”等。设计的算法被用于MIT的新型材料研究项目,美联邦通讯委员会的频谱分配项目以及腾讯地图的语音导播项目,产生了可观经济效益。

林锦坤博士毕业于北京大学计算机软件与理论专业,他的研究领域包括组合优化问题求解、软件交互测试、图论问题求解、启发式算法等方面,现已在人工智能和软件工程顶级会议IJCAI、AAAI、ASE以及人工智能顶级期刊Artificial Intelligence、Journal of Artificial Intelligence Research上发表论文多篇。他在覆盖数组问题上所设计的算法TCA,以及针对大规模图论问题的求解算法FastColor、FastVC、FastWClq等,无论是在解质量上还是在求解时间上,都大幅度地优于当时最好的算法,算法设计经验丰富。

蔡少伟研究员在报告中介绍了求解组合优化问题的相关主要算法,并结合本次大讲堂的主题,重点讲解了局部搜索方法和相关算法的基本思想,以及若干比较有效的局部搜索技术,并结合布尔逻辑可满足性问题的求解,介绍了他提出的一种通用的局部搜索算法技术——格局检测。

林锦坤博士指出,当前互联网的快速发展,使得现实应用中所涉及的图往往具有百万甚至千万量级的顶点数量,而以往的启发式求解算法由于空间和时间复杂度太高等原因,无法有效地求解这类实例。因此,林博士以图着色问题为例,结合自身研究,重点介绍了大规模实例上的求解策略,包括高效的化简规则及交替执行化简和求解的算法框架。

蔡少伟研究员与林锦坤博士的报告深入浅出、通俗易懂,让现场师生对局部搜索算法的设计及布尔逻辑可满足性问题、大规模实例上的图着色等问题的求解有了新的认识。


32EA6



最热新闻
推荐视频
黔南民族师范学院微信平台 ×