附加一个带有现有变量的原子并在 clingo 中创建新的集合

Question

我是 asp 的新手，我正在学习 clingo，我对变量有疑问。我正在研究图形和图形中的路径，所以我使用了一个元组，例如 g((1,2,3))。我想要的是将新节点添加到元组序列所在的路径中。例如下面的代码会给我 (0, (1,2,3)) 但我想要的是 (0,1,2,3)。提前致谢。

g((1,2,3)).
g((0,X)):-g(X).

Answer 1

天真的修复：

g((0,X,Y,Z)) :- g((X,Y,Z)).

但是我感觉到你想将路径存储在元组中，因为它是一个列表。坏消息：与 prolog 不同，clingo 并不意味着将列表作为原子项处理（就像您的示例那样）。列表通过索引元素来处理，例如列表 [a,b,c] 将存储在像 p(1,a). p(2,b). p(3,c). 这样的谓词中。为什么？因为接地：你的目标是得到一个小的接地程序来降低求解过程的复杂性。用数字表示：假设您正在搜索包含所有 n 个节点的路径。总计 n!。对于 n=10，这是 3628800 条潜在路径，为相对较小的图引入了 3628800 个谓词。如上所述对节点进行编号将导致只有 n*n 个潜在谓词来表示路径。对于 n=10，这些只是 100，与 3628800 相比，这是一个巨大的收获。

为了了解您正在搜索的内容，运行以下示例来自 potassco 网站：

% generating path: for every time exactly one node
{ path(T,X) : node(X) } = 1 :- T=1..6. 
% one node isn't allowed on two different positions
:- path(T1,X), path(T2,X), T1!=T2. 
% there has to be an edge between 2 adjascent positions
:- path(T,X), path(T+1,Y), not edge(X,Y). 
#show path/2.

% Nodes
node(1..6).
% (Directed) Edges
edge(1,(2;3;4)).  edge(2,(4;5;6)).  edge(3,(1;4;5)).
edge(4,(1;2)).    edge(5,(3;4;6)).  edge(6,(2;3;5)).

输出：

Answer: 1
path(1,1) path(2,3) path(3,4) path(4,2) path(5,5) path(6,6)
Answer: 2
path(1,1) path(2,3) path(3,5) path(4,4) path(5,2) path(6,6)
Answer: 3
path(1,6) path(2,2) path(3,5) path(4,3) path(5,4) path(6,1)
Answer: 4
path(1,1) path(2,4) path(3,2) path(4,5) path(5,6) path(6,3)
Answer: 5
...

附加一个带有现有变量的原子并在 clingo 中创建新的集合

append an atom with exisiting variables and create new set in clingo

answer-set-programming

clingo