如何使用答案集编程从图中提取树？
How do I extract the trees from a graph using Answer Set Programming?
There is an undirected graph (V,E), weights on the edges w : E → N, a
target k ∈ N, and a threshold O ∈ N. Find a k-vertices tree of the
graph of weight less than the threshold. In other words, select k
vertices and k - 1 edges from V and E respectively such that they
constitute a tree, and the sum of the weights of the selected edges
are less than O.
Write an ASP program that takes V , E, w, k, and O as input, and finds
a selection of edges satisfying the constraints, or outputs
‘unsatisfiable’ if the constraints cannot be satisfied. Selecting the
edges implicitly induces a selection of the vertices, so there is no
need for the selected vertices to be explicitly displayed.
An instance to this problem is provided through predicates vertex/1,
weight/3, target/1, and threshold/1. All edges have weights, so
statements of the form weight(a, b, 10). can be used to declare the
existence of an edge between vertices a and b at the same time as
declaring their weight, and there is no need for any redundant edge/2
predicate.
我尝试了以下方法：
% instance
vertex ( v1 ). vertex ( v2 ). vertex ( v3 ).
vertex ( v4 ). vertex ( v5 ). vertex ( v6 ).
vertex ( v7 ). vertex ( v8 ). vertex ( v9 ).
weight ( v1 , v2 ,3). weight ( v1 , v3 ,3).
weight ( v2 , v4 ,1). weight ( v2 , v5 ,5).
weight ( v3 , v4 ,3). weight ( v3 , v6 ,4).
weight ( v4 , v5 ,4). weight ( v4 , v7 ,1).
weight ( v5 , v7 ,7).
weight ( v6 , v7 ,2). weight ( v6 , v8 ,2).
weight ( v7 , v9 ,3).
weight ( v8 , v9 ,2).
target (4).
threshold (4).
% encoding
(P-1) {select(X, Y) : weight(X, Y, Z)} (Q-1) :- target(P), target(Q).
sum(S) :- S = #sum {W,X,Y : select(X,Y), weight(X,Y,W); W,X,Z : select(X,Z), weight(X,Z,W) }.
:- sum(S),threshold(M), S > M.
:- select(A,B), select(C,D), A == C ; A == D ; B == C ; B == D.
#show select/2.
我得到以下输出：
clingo version 5.5.0
Reading from stdin
Solving...
Answer: 1
select(v2,v4) select(v4,v7) select(v6,v7)
Answer: 2
select(v2,v4) select(v4,v7) select(v6,v8)
Answer: 3
select(v2,v4) select(v4,v7) select(v8,v9)
SATISFIABLE
Models : 3
Calls : 1
Time : 0.013s (Solving: 0.00s 1st Model: 0.00s Unsat: 0.00s)
CPU Time : 0.000s
我只是期待
select(v2,v4) select(v4,v7) select(v6,v7)
因为其他的明显不是tress
我认为这是因为有问题的行：
:- select(A,B), select(C,D), A == C ; A == D ; B == C ; B == D.
我该如何纠正？
好吧，这很复杂。我很确定我的解决方案并不完美，我也是初学者。
开始写代码之前，我们再核对一下问题：要求select k个节点和k-1个边。如果您稍微考虑一下，这可以形成两种模式：一个连接的树或至少有一个循环的多个非连接图。因此，如果您确保没有循环，您将获得一棵相连的树。
我在事实中添加了一些节点来检查是否形成了树或者是否找到了便宜的未连接循环，为此我不得不将 target 和 threshold 更改为更高的值.
1
#const n = 5.
vertex ( v1; v2; v3; v4; v5; v6; v7; v8; v9 ).
vertex ( m1; m2; m3 ).
weight ( v1 , v2 ,3). weight ( v1 , v3 ,3).
weight ( v2 , v4 ,1). weight ( v2 , v5 ,5).
weight ( v3 , v4 ,3). weight ( v3 , v6 ,4).
weight ( v4 , v5 ,4). weight ( v4 , v7 ,1).
weight ( v5 , v7 ,7).
weight ( v6 , v7 ,2). weight ( v6 , v8 ,2).
weight ( v7 , v9 ,3).
weight ( v8 , v9 ,2).
weight ( m1 , m2 ,0).
weight ( m2 , m3 ,0).
weight ( m3 , m1 ,0).
target (n).
threshold (6).
现在是代码，后面是解释。
% select subset of nodes and vertices
(P) {select(X) : vertex(X)} (P) :- target(P).
(P-1) {select(X, Y) : weight(X, Y, Z)} (Q-1) :- target(P), target(Q).
% postion does not matter in an undirected graph.
directed(A,B):-select(A,B).
directed(B,A):-select(A,B).
% for every selected edge all nodes are selected
:- directed(A,_), vertex(A), not select(A).
% for every selected node there exists at least one edge
:- select(A), {directed(A,B):vertex(B)}0.
% select a direction for each selected edge
{dir(A,B);dir(B,A)}==1 :- select(A,B).
% force them in an order
{ found(X,1..n) } == 1 :- select(X).
{ found(X,N):select(X) } == 1 :- N = 1..n.
% reject if one edge does not follow the order
:- found(X,NX), found(Y,NY), dir(X,Y), NY<NX.
% reject if 2 different edges end in the same vertex
:- dir(X,Z), dir(Y,Z), X!=Y.
:- threshold(M), M < #sum {W,X,Y : select(X,Y), weight(X,Y,W); W,X,Z : select(X,Z), weight(X,Z,W) }.
#show select/2.
解释：
- 为了方便我，我在
select/1 谓词中添加了 selected 顶点。
- 由于处理无向图总是需要检查两个位置，所以我添加了
directed/2 谓词，它是 selected 边的有向图版本。
- 接下来我确保每个 selected 顶点都有一个 selected 边，反之亦然。
- 现在是复杂的部分：检测周期。为此，我使用谓词
dir/2 强制每个 selected 边沿其两个方向之一。在有向图中测试树更容易。
- 接下来我对顶点下了一个命令
found/2。有向边 dir/2 只允许按照此顺序进行。这会强制循环到某种行为。
- 现在循环破坏者来了：如果 selected 图有一个循环，那么来自
dir/2 的两条边将终止于同一个顶点。拒绝。如果这只是 clingo 的一个不幸猜测，那么它会找到一个更幸运的猜测来满足这个标准。
- 总和的计算是您复制粘贴的。
输出16倍
select(v2,v4) select(v4,v7) select(v6,v7) select(v6,v8)
重复的原因是 found/2 中顶点的顺序可能不同，但仍会得到相同的结果。
There is an undirected graph (V,E), weights on the edges w : E → N, a target k ∈ N, and a threshold O ∈ N. Find a k-vertices tree of the graph of weight less than the threshold. In other words, select k vertices and k - 1 edges from V and E respectively such that they constitute a tree, and the sum of the weights of the selected edges are less than O.
Write an ASP program that takes V , E, w, k, and O as input, and finds a selection of edges satisfying the constraints, or outputs ‘unsatisfiable’ if the constraints cannot be satisfied. Selecting the edges implicitly induces a selection of the vertices, so there is no need for the selected vertices to be explicitly displayed.
An instance to this problem is provided through predicates vertex/1, weight/3, target/1, and threshold/1. All edges have weights, so statements of the form weight(a, b, 10). can be used to declare the existence of an edge between vertices a and b at the same time as declaring their weight, and there is no need for any redundant edge/2 predicate.
我尝试了以下方法：
% instance
vertex ( v1 ). vertex ( v2 ). vertex ( v3 ).
vertex ( v4 ). vertex ( v5 ). vertex ( v6 ).
vertex ( v7 ). vertex ( v8 ). vertex ( v9 ).
weight ( v1 , v2 ,3). weight ( v1 , v3 ,3).
weight ( v2 , v4 ,1). weight ( v2 , v5 ,5).
weight ( v3 , v4 ,3). weight ( v3 , v6 ,4).
weight ( v4 , v5 ,4). weight ( v4 , v7 ,1).
weight ( v5 , v7 ,7).
weight ( v6 , v7 ,2). weight ( v6 , v8 ,2).
weight ( v7 , v9 ,3).
weight ( v8 , v9 ,2).
target (4).
threshold (4).
% encoding
(P-1) {select(X, Y) : weight(X, Y, Z)} (Q-1) :- target(P), target(Q).
sum(S) :- S = #sum {W,X,Y : select(X,Y), weight(X,Y,W); W,X,Z : select(X,Z), weight(X,Z,W) }.
:- sum(S),threshold(M), S > M.
:- select(A,B), select(C,D), A == C ; A == D ; B == C ; B == D.
#show select/2.
我得到以下输出：
clingo version 5.5.0
Reading from stdin
Solving...
Answer: 1
select(v2,v4) select(v4,v7) select(v6,v7)
Answer: 2
select(v2,v4) select(v4,v7) select(v6,v8)
Answer: 3
select(v2,v4) select(v4,v7) select(v8,v9)
SATISFIABLE
Models : 3
Calls : 1
Time : 0.013s (Solving: 0.00s 1st Model: 0.00s Unsat: 0.00s)
CPU Time : 0.000s
我只是期待
select(v2,v4) select(v4,v7) select(v6,v7)
因为其他的明显不是tress
我认为这是因为有问题的行：
:- select(A,B), select(C,D), A == C ; A == D ; B == C ; B == D.
我该如何纠正？
好吧，这很复杂。我很确定我的解决方案并不完美，我也是初学者。
开始写代码之前，我们再核对一下问题：要求select k个节点和k-1个边。如果您稍微考虑一下，这可以形成两种模式：一个连接的树或至少有一个循环的多个非连接图。因此，如果您确保没有循环，您将获得一棵相连的树。
我在事实中添加了一些节点来检查是否形成了树或者是否找到了便宜的未连接循环，为此我不得不将 target 和 threshold 更改为更高的值.
#const n = 5.
vertex ( v1; v2; v3; v4; v5; v6; v7; v8; v9 ).
vertex ( m1; m2; m3 ).
weight ( v1 , v2 ,3). weight ( v1 , v3 ,3).
weight ( v2 , v4 ,1). weight ( v2 , v5 ,5).
weight ( v3 , v4 ,3). weight ( v3 , v6 ,4).
weight ( v4 , v5 ,4). weight ( v4 , v7 ,1).
weight ( v5 , v7 ,7).
weight ( v6 , v7 ,2). weight ( v6 , v8 ,2).
weight ( v7 , v9 ,3).
weight ( v8 , v9 ,2).
weight ( m1 , m2 ,0).
weight ( m2 , m3 ,0).
weight ( m3 , m1 ,0).
target (n).
threshold (6).
现在是代码，后面是解释。
% select subset of nodes and vertices
(P) {select(X) : vertex(X)} (P) :- target(P).
(P-1) {select(X, Y) : weight(X, Y, Z)} (Q-1) :- target(P), target(Q).
% postion does not matter in an undirected graph.
directed(A,B):-select(A,B).
directed(B,A):-select(A,B).
% for every selected edge all nodes are selected
:- directed(A,_), vertex(A), not select(A).
% for every selected node there exists at least one edge
:- select(A), {directed(A,B):vertex(B)}0.
% select a direction for each selected edge
{dir(A,B);dir(B,A)}==1 :- select(A,B).
% force them in an order
{ found(X,1..n) } == 1 :- select(X).
{ found(X,N):select(X) } == 1 :- N = 1..n.
% reject if one edge does not follow the order
:- found(X,NX), found(Y,NY), dir(X,Y), NY<NX.
% reject if 2 different edges end in the same vertex
:- dir(X,Z), dir(Y,Z), X!=Y.
:- threshold(M), M < #sum {W,X,Y : select(X,Y), weight(X,Y,W); W,X,Z : select(X,Z), weight(X,Z,W) }.
#show select/2.
解释：
- 为了方便我，我在
select/1谓词中添加了 selected 顶点。 - 由于处理无向图总是需要检查两个位置，所以我添加了
directed/2谓词，它是 selected 边的有向图版本。 - 接下来我确保每个 selected 顶点都有一个 selected 边，反之亦然。
- 现在是复杂的部分：检测周期。为此，我使用谓词
dir/2强制每个 selected 边沿其两个方向之一。在有向图中测试树更容易。 - 接下来我对顶点下了一个命令
found/2。有向边dir/2只允许按照此顺序进行。这会强制循环到某种行为。 - 现在循环破坏者来了：如果 selected 图有一个循环，那么来自
dir/2的两条边将终止于同一个顶点。拒绝。如果这只是 clingo 的一个不幸猜测，那么它会找到一个更幸运的猜测来满足这个标准。 - 总和的计算是您复制粘贴的。
输出16倍
select(v2,v4) select(v4,v7) select(v6,v7) select(v6,v8)
重复的原因是 found/2 中顶点的顺序可能不同，但仍会得到相同的结果。