1

拥有 Prolog 的背景，我正在努力将这个DLV（它具有内置谓词来处理类似于 Prolog 的列表）程序转换为CLINGO.

path(X,Y,[X|[Y]]) :- rel(X,Y).
path(X,Y,[X|T]) :- rel(X,Z), path(Z,Y,T), not #member(X,T).

rel(X,Y) :- edge(X,Y).
rel(X,Y) :- edge(Y,X).

edge(a,b).
edge(a,c). 
edge(b,a). 
edge(b,c).
edge(e,c).

到目前为止，我设法实现了这一点：

path(X,Y,cons(X,cons(Y,empty))) :- edge(X,Y).
path(X,Y,cons(X,L)) :- edge(X,Z), path(Z,Y,L), not member(X,path(Z,Y,L)).

member(X,path(X,T,cons(X,Y))) :- path(X,T,cons(X,Y)).
member(X,path(S,X,cons(S,L))) :- path(S,X,cons(S,L)).
member(X,path(S,T,cons(S,cons(Z,L)))) :- member(X,path(Z,T,cons(Z,L))).

% same edges

但我得到了错误unsafe variables in in file - at line 7 and column 1-72，我不完全明白为什么。我想知道是否有人可以提供帮助。

4

1 回答 1

0

你从未定义过 S 可能是什么。

添加edge(S,Z)到第 7 行的规则正文以消除该错误。或者，如果您想定义一个顶点谓词，您也可以使用vertex(S)。

所以我用 cons-lists 修复了你的代码。这种方法很不寻常，因为列表不是 asp 中的关键特性，就像它们在 prolog 中一样。好的，这是我的解决方案（适用于有向图）：

edge(a,b).
edge(a,c). 
edge(b,c). 
edge(c,a). 
edge(c,d). 
edge(d,b).

node(X) :- edge(X,_). % get nodes
node(X) :- edge(_,X). % get nodes
num(N):- {node(X)} == N. % count nodes
step(1..N) :- num(N). % mark possible steps

path(X,Y,2,cons(X,cons(Y,empty))) :- edge(X,Y).
path(A,C,NN+1,cons(A,L)) :- edge(A,B), path(B,C,NN,L), step(NN+1).

member(X,path(X,Y,N,cons(X,L))) :- path(X,Y,N,cons(X,L)).
member(Y,path(X,Y,N,cons(X,L))) :- path(X,Y,N,cons(X,L)).   
member(M,path(S,T,NN+1,cons(S,cons(Z,L)))) :- member(M,path(Z,T,NN,cons(Z,L))), path(S,T,NN+1,cons(S,cons(Z,L))).   

track(Y,Z,N,L):- {member(X,path(Y,Z,N,L)):node(X)} == N, path(Y,Z,N,L).

#show track/4.

首先你需要知道所有的顶点来计算它们的数量。我还介绍了谓词step来验证路径的深度。path现在也有一个深度计数器作为第三个参数。所有可能的路径都存储在 内path/4，允许循环。member/2生成谓词以显示 a 中的所有成员顶点path/4。track/4在最后一步中，当且仅当不同成员顶点的数量等于路径长度时，所有路径都被转发到谓词。由于不会计算重复项，因此此条件确保仅转发没有循环的路径。请注意，以上所有步骤都是强制的。每个图表都有一个答案集。

因此，让我们看一下更类似于 ASP 的解决方案。通常你会问一个特定的问题（'从 a 到 b 的路径，长度为 n'）而不是一个通用的问题（'从所有节点到所有可能长度的所有节点的所有可能路径'）。以下代码需要有一个开始节点 ( start/1) 和一个结束节点 ( end/1)。该程序通过为 predicate 中的每个顶点精确分配一个索引号来强制执行（随机）顺序order/2。order只要索引不大于结束节点 ( path(S,N):- order(S,N), maxZ(Z), S<=Z.)的索引，谓词就会被复制到路径谓词中。唯一的限制是在路径顺序内，每 2 个相邻顶点都与一条边相连。约束线读作不可能存在路径内位置N上的节点S1和路径内位置N+1上的节点S2并且从S1到S2没有边的情况。

edge(a,b).
edge(a,c). 
edge(b,c). 
edge(c,a). 
edge(c,d). 
edge(d,b).

start(a).
end(d).

node(X) :- edge(X,_). % get nodes
node(X) :- edge(_,X). % get nodes
num(N):- {node(X)} == N. % count nodes
step(1..N) :- num(N). % mark possible steps
order(1,A):- start(A). % start has index 1
maxZ(Z):- end(E), order(Z,E), step(Z). % end has index maxZ

{order(S,N):node(N)} == 1 :- step(S). % exactly one assignment per step
{order(S,N):step(S)} == 1 :- node(N). % exactly one assignment per node

path(S,N):- order(S,N), maxZ(Z), S<=Z. % copy order when index is not largter than end node index
:- path(N, S1), path(N+1, S2), not edge(S1,S2). % successing indices are connected through edges
        
#show path/2.
于 2020-11-25T20:27:49.070 回答