回答集程序设计 理论、方法、应用与研究.doc

回答集程序设计_理论、方法、应用与研究.doc回答集程序设计:理论、方法、应用与研究崔仲毅,程渤(北京邮电人学网络与交换技术国家重点实验室)摘要:冋答集程序设计(Answersetprogramming,ASP)是一种面向复杂搜索的声明型程序设计方法。ASP是综合非单调推理、演绎数据库和逻辑程序设计方法的一项研究成果,适合于解决知识密集型问题。ASP语法结构与Prolog类似,但其计算机制不同,主要借助于高效的命题逻辑可满足求解器进行计算。本文对ASP的语法、语义、程序设计方法以及应用分别进行了阐述。最后,对ASP的未来研究方向进行了讨论。关键词:回答集程序设计;声明型程序设计方法;非单调推理中图分类号:请查阅《中国图书馆分类法》AnswerSetProgramming:Theories,Techniques,ApplicationsandResearchesZhaiZhongyi,ChengBo(workingandSwitchingTechnology,munications)Abstract:Answersetprogramming(ASP),deductivedatabaseandlogicprogramming,,,weintroducethesyntaxandsemanticofASPprograms,themethodfordevelopingASPprogramsandtheapplicationofASP・Finally,wediscussthefuturedirectionofASP・Keywords:Answersetprogramming;DeclarativeProgramming;NonmonotonicReasoningo引言基于经典逻辑的程序设计语言对于实现智能化起到了基础性作用。但经典逻辑的推理方式是单调的,当加入新的知识时只能增添新的结论,而不能否定以前的结论。为了用机器模拟人类的智能化思维,非单调推理显得至关重要⑴。20世纪70年代提出了缺省逻辑(DefaultLogic)⑵、自认知逻辑(Auto-epistemicLogic)⑶、划分理论(Circumscription)^]等几种非单调推理方法,由于缺少高效的开发工具和不具备模块化程序设计,这儿种推理方法并没育得到广泛应用。Gclfond和LifschitzI*1988年提出了—种稳定模型语义(StableModelScmantic)[5],其在非单调推理下成功地解释了失败即否定(NotasFailure)。以稳定模型为基础,90年代末形成了一种新的逻辑程序设计方法一冋答集程序设计方法[