带有答案集编程的规则引擎和知识密集型处理

答案集编程（ASP）是一种软件范例，可用于表示知识并解决组合和信息密集型问题。组合搜索问题是那些被认为没有减少解决方案空间的有效方法（NP-hard）的问题，本文提供了此类示例。知识的概念非常广泛，并且非常依赖领域。它包括各种程度的信念，事实和规则，这些信念，规则和规则可用于进行推理，并且通常包括我们对世界的常识性理解。

我提出的一个编程工具可以解决这里提出的难题，该工具是由Datalog和波茨坦大学开发的ASP Clingo自由启发的。与Datalog不同，此处报告的脚本基于特定于域的语言，并且它们利用Scala的强类型编译器。本文的目的不是提供一种更有效的方式来执行ASP，而是构建用于继续进行我正在进行的项目的工具，并探索这种范例在诸如数据管理和规则等其他领域的潜力。系统。我希望传达一种认识，即该软件范例在现实情况下在弹性和完整性方面具有优势。 ASP已用于：

决策支持系统，可帮助航天飞机控制器处理因多次故障导致的紧急情况。

分类意大利电信用户的个人资料和实际需求（每天100万次呼叫），以创建个性化的客户服务体验。

产品和服务的配置要遵守铁路安全控制，旅游，汽车，计算机硬件，软件包中的复杂规则。

ASP是逻辑编程的一种形式，其中规则（或自变量）可以被视为可执行规范。 ASP程序不侦听查询，而是递归地应用所有条件，直到生成的知识不再发展为止。当没有其他可满足的条件要运行时，系统将返回结果列表，所谓的稳定模型或答案集。让我们看一个有关质数的例子。

什么是质数？数字只能被一整除。在逻辑上，为了将一条陈述评估为有效，我们必须取消任何可能的反例。如果数字是两个与一个数字不同且与它本身不同的乘积，则不是质数。从这个角度重新定义定义，我们有：

如果没有证据表明X是质数，则X是质数。

让我们通过在给定范围内生成所有可能的因子组合来获得复合（或复合）数字的列表，然后检查其模块（除法的余数）是否为零。

（“化合物” :: X :: e）：-（X：=（1至N），Y：=（2至X-1），（X％％Y）=== 0）

在前提的第一个子句中（X：=（1到N）），我只为变量X分配一个列表。在第二个子句中，每个X都有一个Y的列表，它们的对应组合是笛卡尔所有X和Y的乘积。最后一个子句将检查X的任何单个实例是否可被Y整除。如果是，则生成一个新的原子“化合物”。最后，以下参数将实例化“素数”原子：

（“ prime” :: X :: e）：-（X：=（1至N），而不是“ product” :: X :: e）

这里的新功能是称为否定失败的not关键字。它检查知识图中是否存在原子实例“ product” :: X，如果不存在则返回true。完整的程序是：

import com.sap.cxlabs.bewater.logic.asp._val N = 7val参数= Args（（“ compound” :: X :: e）：-（Z：=（1至N），Y：=（2至Z-1），X：=（Z %% Y）=== 0）（“素数” :: X :: e）：-（X：=（1到N），而不是“乘积” :: X： ：e））val结果= arguments.deduct（）

在ASP中，至少有两个主要阶段表示程序的执行：

这是一个经典的组合问题，其中通过考虑节点的颜色必须不同于相邻节点的颜色来着色图中的节点。输入图包含节点，边和给定的颜色：

val facts =新的FactBuilderfacts.node（1到6）facts.edge（1，2）; facts.edge（1，3）; facts.edge（1，4）facts.edge（2，4）; facts.edge（2，5）; facts.edge（2，6）facts.edge（3，4）; facts.edge（5，3）; facts.edge（5，4）事实.edge（5，6）; facts.edge（6，3）; facts.edge（6，5）facts.col（Seq（“ blue”，“ green”，“ red”））

在这里，为原子中存在的每个节点和每种颜色生成原子“颜色”。给定一个节点仅分配一种颜色，我们创建所有可能的排列，并指定（使用^（1）操作），在每个解决方案中，参数（1）中的字段都是唯一的。 FactBuilder是一个帮助工具，可以比上一个示例更方便地编写原子。

求解器部分将删除两个相邻节点具有相同颜色的所有解决方案：

val规则= Args（p.color（X，Y）。^（1）：-（p.node（X），p.col（Y））,: :-( p.edge（X，Y），p。 color（X，W），p.color（Y，W）））规则。扣除（事实）

如果您已经下过国际象棋，您就会知道女王是棋盘上最强大的棋子，而输掉棋子通常是失败的序言。在这个难题中，问题是要在N * N棋盘中找到所有N个皇后的配置，任何一个皇后都不能攻击其他皇后。 ASP程序将在棋盘上生成所有皇后排列，并过滤出以下所有配置：

如何检查两块是否对角线？当X轴的差与Y轴的（绝对）差相同时，它们位于同一对角线上。遵循数据和程序：

val N = 6val事实=新的FactBuilderfacts.row（1至N）facts.col（1至N）val参数= Args（（（（“ queen” :: X :: Y :: e）$$（N））： -（“ row” :: X :: e，“ col” :: Y :: e），́ :-(“ queen” :: X :: Y :: e，“ queen” :: X :: Z :: e，Y <> Z），́ :-(“ queen” :: X :: Y :: e，“ queen” :: Z :: Y :: e，X <> Z），́ :-(“ queen”： ：X :: Y :: e，“ queen” :: W :: Z :: e，！（（X === W）&&（Y === Z）），（X-W）.abs == =（Y-Z）.abs），）arguments.deduct（事实）

val f =新的FactBuilderf.x（1到9）fy（1到9）fn（1到9）val p =新的FactBuilderval参数= Args（p.cell（X，Y，Z）。^（1，2） ：-（px（X），py（Y），pn（Z）），p.subgrid（X，Y，A，B）：-（px（X），px（A），py（Y），py （B），（X-1）/ 3 ===（A-1）/ 3，（Y-1）/ 3 ===（B-1）/ 3）,: :-( p.cell（X， Y，Z），p.cell（W，Y，Z），X <> W），-：（p.cell（X，Y，Z），p.cell（X，W，Z），Y <> W），-:-( p.cell（X，Y，Z），p.cell（A，B，Z），p.subgrid（X，Y，A，B），X <> A，Y <> B ））

很遗憾，我无法向您显示该程序的任何结果。在这个难题中，这种探索性ASP引擎的局限性显而易见。解决方案的空间对于我采用的简单接地算法是不允许的。无论如何，该工具的效率和有效性不是本文的重点。相反，我邀请您在Clingo上运行等效程序。解析矩阵大约需要一秒钟的时间，怎么可能呢？好吧，多亏了惰性接地，冲突驱动的求解器，即使在逻辑编程领域也取得了一些巨大的飞跃。这种算法的发展归因于学术研究。它们是可公开访问的，并且在商业系统中对其实施没有任何限制。

在最短路径中，问题是要在图中的两个连接节点之间找到一条路径，并且是否存在一条以上的路径，请选择成本最低的路径。数据应包含“开始”和“结束”节点，以及边缘，不同节点之间的连接。原子“边缘”定义了这种连接的点和权重。该程序是：

val shortestPath = SModels（Args（p.path（X，Y，W）:-( p.start（X），p.edge（X，Y，W）），p.path（X，Z，A + B ）：-（p.path（X，Y，A），p.edge（Y，Z，B）），p.shortest（W）：-（p.end（Y），p.path（X，Y ，W），而不是p.path（X，Y，Z），W

这是ASP中递归的示例。 SModels包装器旨在返回稳定的模型，因为会为所有连接的边生成“路径”原子，并且迭代次数取决于节点的距离程度（例如，慕尼黑和东京当然是通过道路连接的，但是它们之间的距离很高）。

我认为注意到最后一个参数很有趣，该参数旨在启发最低成本：

“ W是最低成本，如果没有证据表明存在较小的成本”