Answer Set Programming 回答集编程

什么是ASP？

　　ASP，全称 Answer Set Programming 中文名叫“回答集编程”。实验室学长要我学ASP的时候，我就去百度查了ASP，结果查到了都是这个：Active Server Page，意为“活动服务器网页”。我当时就在想：“这个不对啊，这个搞网站的，应该是旁边组系统集成组的事呀”。果然，此ASP非彼ASP。
　　Answer Set Programming (ASP)提供了一种简单而强大的建模语言来解决组合问题。使用ASP，我们关注的方向就变成要解决的实际问题，而不是解决的方案。和C语言、python等语言有很大的不同，ASP是一种声明式编程，主要用于复杂的搜索问题。它基于逻辑编程的稳定模型语义。在ASP中，搜索问题被简化为计算稳定模型，并且问答集求解器（用于生成稳定模型的程序）用于执行搜索。许多问答集求解器的设计中使用的计算过程是DPLL算法的增强，并且从原理上讲，它总是终止（与Prolog查询评估不同，这可能导致无限循环））。从更一般的意义上讲，ASP包括对知识表示的回答集的所有应用程序，以及使用Prolog风格的查询评估来解决这些应用程序中出现的问题。

　　Dimopoulos，Nebel和Köhler 在1993年提出的计划方法是回答集编程的早期示例。他们的方法基于计划和稳定模型之间的关系。Soininen和Niemelä 将现在称为回答集的编程应用于产品配置问题。Marek和Truszczyński在1999年和[Niemelä1999] 发表的关于逻辑编程范例25年的论文中，将答案集求解器用于搜索被确定为一种新的编程范例。的确，Lifschitz [8]在与Marek-Truszczynski论文相同的回顾性卷中首次提出了“答案集”而不是“稳定模型”的新术语。

基本语法

　　一个简单的ASP程序包括三个部分：事实、规则、输出。事实和规则，用来描述问题；输出，用来查看结果。

一个简单例子
　　现在有烟台，北京，青岛，济南，桂林5个城市，我们现在要坐火车在这4个城市之间穿梭，已知除了北京、桂林以外，其他三个城市之间都有直达的火车，而北京只有到济南的直达火车，桂林到哪个城市都没有直达的，那么从烟台出发，我都能到达哪些城市呢？

ASP代码如下
注：后缀名：.lp

% fact
%city(yantai,beijing,qingdao,jinan,guilin).
road(beijing,jinan).
road(jinan,yantai).
road(jinan,qingdao).
road(qingdao,yantai).
%rule
road(X,Y) :- road(Y,X).
road(X,Y) :- road(X,Z),road(Z,Y).
arrive(X) :- road(yantai,X).
% Displan
#show arrive/1.

事实和规则
　　从上面的例子我们可以看出，一个ASP程序包括两个重要的部分：事实和规则。
事实：用于描述现实世界的状态。
规则：用于进行推理。
　　ASP程序里还包括了常量（例子中的城市名）；谓词（如road, arrive），每个谓词中有若干个参数，我们把带有n个参数的谓词p写作p/n；变量（例子中大写的X、Y），注意的是本质上ASP程序是不支持变量的，这里的变量仅仅是为了方便书写，在实际的求解中这些变量会被替换为程序中出现的所有常量。

输出

% fact
%city(yantai,beijing,qingdao,jinan,guilin).
road(beijing,jinan).
road(jinan,yantai).
road(jinan,qingdao).
road(qingdao,yantai).
road(guilin,jinan).
maintain(jinan,beijing).
%rule
road(X,Y) :- road(Y,X).
maintain(x,y) :- maintain(y,x).
route(X,Y) :- road(X,Y),not maintain(X,Y).
route(X,Y) :- route(X,Z),route(Z,Y).
arrive(yantai,X) :- route(yantai,X).
% Displan
#show arrive/2.