2

假设我有一个图表，并且想在图表中找到 2 个不同的派系。一个团是图顶点的一个子集，所有这些顶点都连接在一起。具有 2 个 cliques (a,b,c) 和 (b,c,d) 的 cliquesize 3 的示例图：

edge(a,b). edge(a,c). edge(b,c). edge(d,c). edge(d,b).
vertex(X;Y) :- edge(X,Y).

在此处输入图像描述

获得 2 个派系相当容易：

#const cs=3. % cliquesize
cs{clique1(X) : vertex(X)}cs.
:- clique1(X), clique1(Y), X!=Y, not edge(X,Y), not edge(Y,X).
cs{clique2(X) : vertex(X)}cs.
:- clique2(X), clique2(Y), X!=Y, not edge(X,Y), not edge(Y,X).

#show clique1/1.
#show clique2/1.

给出：

Answer: 1
clique2(d) clique1(a) clique2(b) clique2(c) clique1(b) clique1(c)
Answer: 2
clique2(d) clique1(d) clique2(b) clique2(c) clique1(b) clique1(c)
Answer: 3
clique2(a) clique1(a) clique2(b) clique2(c) clique1(b) clique1(c)
Answer: 4
clique2(a) clique1(d) clique2(b) clique2(c) clique1(b) clique1(c)
SATISFIABLE

可以解释为：

Answer 1: (a,b,c), (b,c,d)
Answer 2: (b,c,d), (b,c,d)
Answer 3: (a,b,c), (a,b,c)
Answer 4: (b,c,d), (a,b,c)

但是如何测试两个派系是否不同？我试过了

differ() :- clique1(X), clique2(Y), X!=Y.
:- not differ().

但这对输出没有影响。我如何测试两个派系是否不同？

现在我找到了这个解决方案：

differ() :- clique1(X), vertex(X), not clique2(X).
:- not differ().

它有效，但我不喜欢它需要 2 行。我如何把它放在一个约束中？

4

1 回答 1

1

我如何把它放在一个约束中？

这有点棘手，因为您基本上想要一个存在量化：“派系之间必须至少有一个顶点差异”，因此简单地插入规则推导的主体是differ/0行不通的。（因为这将是所有顶点的通用量化）

我认为以下内容符合您对单行约束的要求：

:- #count{X : clique1(X), not clique2(X)} < 1.

但是，根据您的输入图有多大，我可以想象这可能会导致性能问题。

我不确定您的确切要求，但也许您可以采取稍微不同的方法：

  • 只找一个 clique（基本上注释掉 clique2 部分）
  • 通过您从 cligo 请求的答案集数量来配置您实际想要的派系数量。

在您的情况下，那将是..$clingo -n 2 clique.asp，额外的好处是每个答案集您只能获得一个集团，以及您想要的许多（不同）集团。

于 2020-11-20T15:00:42.350 回答