一个带破圈启发方法的回答集编程系统(英文)  

An Answer Set Programming System with Cycle Breaking Heuristic

作　　者：沈榆平[1] 赵希顺[1] 

机构地区：[1]中山大学逻辑与认知研究所,广东广州510275

出　　处：《软件学报》2008年第4期869-878,共10页Journal of Software

基　　金：国家自然科学基金Nos.60573011,10410638;国家教育部基地重大招标项目No.05JJD72040122~~

摘　　要：回答集编程(answer set programming,ASP)是一种回答集语义下的逻辑编程范例,可应用于非单调推理,叙述式问题求解等领域.本文为ASP提出并实现了一种破圈启发方法与一种基部限制式前向搜索过程,所得到的系统称为LPS.实验结果显示,相对于其他经典的ASP系统,LPS能够有效地解决处于相变难区域中的逻辑程序,通常这些程序被认为是计算困难的.除此以外,通过使用被称为动态变元过滤(dynamic variable filtering,DVF)的技术,LPS可以在计算过程中极大地缩小搜索树的尺寸.Answer set programming （ASP） is a logic programming paradigm under answer set semantics, which can be utilized in the field of non-monotonic reasoning and declarative problem solving, etc. This paper proposes and implements a cycle breaking heuristic and a bottom-restricted look-ahead procedure for ASP, and the resulting system is called LPS. The experimental results show that, relative to other state-of-the-art ASP systems, LPS could efficiently solve logic programs in phase transition hard-job-regions, and these programs are generally considered difficult to compute. In addition, by applying the so-called dynamic variable filtering （DVF） technique, LPS could greatly reduce the search tree size during the computation.

关 键 词：回答集编程 启发方法 前向搜索 逻辑程序 相变 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]