许可
主要从事算法与计算复杂性、数据挖掘和网络测量、分析与建模等方面的研究工作。
个性化签名
- 姓名:许可
- 目前身份:
- 担任导师情况:
- 学位:
-
学术头衔:
博士生导师, 教育部“新世纪优秀人才支持计划”入选者
- 职称:-
-
学科领域:
计算机软件
- 研究兴趣:主要从事算法与计算复杂性、数据挖掘和网络测量、分析与建模等方面的研究工作。
许可,男,1971年8月生,教授,博士生导师。分别于1993年7月和2000年3月在北京航空航天大学飞行器设计与应用力学系和计算机科学与工程系获学士和博士学位。现工作于北京航空航天大学计算机学院软件开发环境国家重点实验室。2002年获"全国百篇优秀博士论文"奖。2005年和2007年分别入选北京市科技新星计划和教育部新世纪优秀人才支持计划。主持或作为学术骨干参与了国家自然科学基金、973和国家攀登计划等科研项目。其中,所负责的一项国家自然科学基金项目在结题时被基金委评为特优。现任《中国科学F辑:信息科学》编委、973项目首席科学家助理和项目专家组成员。主要从事算法与计算复杂性、数据挖掘和网络测量、分析与建模等方面的研究工作。在NP完全问题相变现象的研究中提出并研究了具有精确相变和难解实例的RB模型,系列研究成果在Journal of AI Research、Theoretical Computer Science和Artificial Intelligence等国际期刊上发表。研究成果被来自世界十多个国家的学者引用两百多次,其中包括来自手册(Handbook)、百科全书(Encyclopedia)和专著的引用。RB模型已被包括国际著名学者在内的国际同行进一步发展和推广,并多次被其他学者在论文中用专节论述和分析。以RB模型为基础所构造的算法测试集被广泛地下载,并应用于SAT、CSP、PB和MAX-SAT等国际算法竞赛。部分成果被美国加州大学圣地亚哥分校、明尼苏达大学和加拿大阿尔伯塔大学等十多所国外大学分别用于算法和人工智能等课程的教学工作。
-
主页访问
1352
-
关注数
0
-
成果阅读
114
-
成果数
3
【期刊论文】Exact Phase Transitions in Random Constraint Satisfaction Problems
许可, Ke Xu, Wei Li
Journal of Artifieial Intelligence Research 12(2000)93-103,-0001,():
-1年11月30日
In this paper we propose a new type of random CSP model, called Model RB, which is a revision to the standard Model B. It is proved that phase transitions from a region where almost all problems are satisfiable to a region where almost all problems are unsatisfiable do exist for Model RB as the number of variables approaches infinity. Moreover, the critical values at which the phase transitions occur arc also known exactly. By relating the hardness of Model RB to Model B, it is shown that there exist a lot of hard instances in Model RB.
-
45浏览
-
0点赞
-
0收藏
-
0分享
-
76下载
-
0评论
-
引用
【期刊论文】Many hard examples in exact phase transitions☆
许可, Ke Xu∗, Wei Li
Theoretical Computer Science 355(2006)291-302,-0001,():
-1年11月30日
This paper analyzes the resolution complexity of two random constraint satisfaction problem (CSP) models (i.e. Model RB/RD) for which we can establish the existence of phase transitions and identify the threshold points exactly. By encoding CSPs into CNF formulas, it is proved that almost all instances of Model RB/RD have no tree-like resolution proofs of less than exponential size. Thus, we not only introduce new families of CSPs and CNF formulas hard to solve, which can be useful in the experimental evaluation of CSP and SAT algorithms, but also propose models with both many hard instances and exact phase transitions. Finally, conclusions are presented, as well as a detailed comparison of Model RB/RD with the Hamiltonian cycle problem and random 3-SAT, which, respectively, exhibit three different kinds of phase transition behavior in NP-complete problems.
Constraint satisfaction problem (, CSP), , Random problems, Resolution complexity, Phase transitions, SAT
-
34浏览
-
0点赞
-
0收藏
-
0分享
-
112下载
-
0评论
-
引用
【期刊论文】Random constraint satisfaction: Easy generation of hard (satisfiable) instances
许可, Ke Xu a, ∗, , Frédéric Boussemart b, Fred Hemery b, Christophe Lecoutre b
Artificial Intelligence 171(2007)514-534,-0001,():
-1年11月30日
In this paper, we show that the models of random CSP instances proposed by Xu and Li [K. Xu, W. Li, Exact phase transitions in random constraint satisfaction problems, Journal of Artificial Intelligence Research 12 (2000) 93-103; K. Xu, W. Li, Many hard examples in exact phase transitions with application to generating hard satisfiable instances, Technical report, CoRR Report cs.CC/0302001, Revised version in Theoretical Computer Science 355 (2006) 291-302] are of theoretical and practical interest. Indeed, these models, called RB and RD, present several nice features. First, it is quite easy to generate random instances of any arity since no particular structure has to be integrated, or property enforced, in such instances. Then, the existence of an asymptotic phase transition can be guaranteed while applying a limited restriction on domain size and on constraint tightness. In that case, a threshold point can be precisely located and all instances have the guarantee to be hard at the threshold, i.e., to have an exponential tree-resolution complexity. Next, a formal analysis shows that it is possible to generate forced satisfiable instances whose hardness is similar to unforced satisfiable ones. This analysis is supported by some representative results taken from an intensive experimentation that we have carried out, using complete and incomplete search methods.
Phase transition, Constraint network, Hard random instances
-
35浏览
-
0点赞
-
0收藏
-
0分享
-
137下载
-
0评论
-
引用