1

無向グラフ (V,E)、辺の重み w : E → N、ターゲット k ∈ N、しきい値 O ∈ N があります。重みがしきい値未満のグラフの k-頂点ツリーを見つけます。つまり、V と E からそれぞれ k 個の頂点と k - 1 個のエッジを選択して、それらがツリーを構成し、選択したエッジの重みの合計が O 未満になるようにします。

V、E、w、k、および O を入力として取り、制約を満たすエッジの選択を見つけるか、制約を満たさない場合は「満たされない」を出力する ASP プログラムを作成します。エッジを選択すると暗黙的に頂点が選択されるため、選択した頂点を明示的に表示する必要はありません。

この問題のインスタンスは、頂点/1、重み/3、ターゲット/1、およびしきい値/1 の述語によって提供されます。すべてのエッジには重みがあるため、式は weight(a, b, 10) になります。を使用して、頂点 a と b の間のエッジの存在を宣言すると同時に、それらの重みを宣言できます。余分なエッジ/2 述語は必要ありません。

私は次のことを試しました：

% 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)

他の人は明らかに髪ではないからです。

これは問題のある行が原因だと思います：

:- select(A,B), select(C,D), A == C ; A == D ; B == C ; B == D.

これを修正するにはどうすればよいですか?

4

1 に答える 1