Prolog 条款的绑架

Question

我有一个带标记节点和边的有向有根图的规范。该规范描述了哪些节点可以连接到哪些其他节点，以及根据顶点的属性描述图结构的各个方面。

例如：

每个 A 节点都必须连接到边类型为 B 的 B 节点，B 节点通过任何边类型连接到 D 节点，并且根节点必须有到至少 2 个其他节点的路径。

followsSpec(Root) :- 
    edge(Root, _, A), 
    edge(Root, _, B), 
    A != B, 
    edge(A, edgeTypeB, C), 
    node(C, nodeTypeC), 
    edge(C, _, D),
    node(D, nodeTypeD).

我想说

node(root, typeA)
followsSpec(root)

并推导出使 followsSpec 为真的图表的其他可能元素：

node(b, typeB)
node(c, typeC)
edge(root, some_arbitrary_edge_type, b)
edge(root, some_other_arbitrary_edge_type, c)
edge(b, edge_type_b, c)

有没有办法在 Prolog 中做到这一点？

特别担心效率问题，因为实际上规范比较复杂，至少有100个节点。

编辑：试图形式化：可溯源谓词是 edge/3（其中三个变量对应于源、目标和转换类型）和 node/2（其中两个变量对应于节点标识符和节点标签）。
我从一个事实开始 node(root, rootLabel))。我的观察：遵循 Spec(root)，其中

followsSpec(X) :- "x is connected in a particular way to other nodes through edges"

我想观察的是：那些其他节点和边是什么使得 followsSpec(root) 为真。

Answer 1

您可以使用假设推理来找到溯因解决方案。假设你有一个理论 T，并且想为一些观察找到解释 E：

 T, E |- O

假设推理有一个特殊的运算符，称为嵌入蕴涵（assumez）。您可以使用此蕴涵来验证溯因式解决方案，将溯因推理转化为演绎：

 T |- assumez(E, O).

assumez/2 的简单实现是：

assumez(E,O) :-
   assertz(E),
   O,
   retract(E).

但是上面的内容将无法保留，因此您需要一个落后于 assertz/1 和 retract/1 的 Prolog 系统。如果您不想使用 CHR 或 ASP，您可以使用 Jekejeke Prolog 中更简单的库 (minimal/hypo)。

Prolog 条款的绑架

Abduction of Prolog clauses

graph-theory

prolog

constraint-programming