生成候选解决方案以匹配 Clingo/ASP 中的人

Question

我有一个人员列表，我想将他们全部配对，然后根据偏好进行一些过滤。当我生成我的候选解决方案时，我如何避免创建重新配对人的候选解决方案。

例如：

person(a;b;c;d) .
{match(X, Y): person(Y)}1 :- person(X) .

这会生成包含 match(a,b) match(c,b) ...

的候选解决方案

我只想要不会重新匹配任何人的候选解决方案，例如：match(a,b) match(c,d) ...

我的目标是不必通过额外的限制来过滤掉重新匹配。另外，并不是每个人都需要匹配。谢谢！

Answer 1

person(a;b;c;d).
{match(A,B) : person(A), person(B), A < B}.
:- person(A), 1 < {match(A,B); match(B,A)}.

您排除了与单个人匹配超过 1 个的解决方案。

不可能在没有额外限制的情况下简单地选择一组正确的原子。由于 match(a,b) 和 match(b,c) 可以出现在不同的答案集中，因此需要创建两个变量。只有一个约束可以排除两者不出现在同一个答案集中。

另请注意您的生成器规则

{match(X, Y): person(Y)}1 :- person(X) .

已经是

的捷径

{match(X, Y): person(Y)} :- person(X).
:- person(X), 2 {match(X, Y): person(Y)}.

因此，只要您的生成器选择规则具有非平凡边界，您就已经在使用约束。

PS：使用 --stats=2 检查不同版本的约束计数，使用 --text 粗略估计生成的约束类型。

Answer 2

我会去回答。

难点之一是处理匹配谓词的属性顺序：这是一个元组，如果您的值出现在第一个或第二个位置，就会有所不同。添加规则以使谓词 commutative 应该可以解决问题，因为您不需要区分值位于第一位还是第二位。此方法不使用约束（乍一看），但它会复制生成的值，因此输出与您所需的解决方案不同。它还在代码中添加了一行。

person(a;b;c;d).
{match(X,Y): person(Y), X!=Y}1 :- person(X).
match(Y,X) :- match(X,Y).
#show match/2.

输出

Answer: 1

Answer: 2
match(c,a) match(a,c)
Answer: 3
match(b,a) match(a,b)
Answer: 4
match(c,d) match(d,c)
Answer: 5
match(b,a) match(a,b) match(c,d) match(d,c)
Answer: 6
match(b,d) match(d,b)
Answer: 7
match(c,a) match(a,c) match(b,d) match(d,b)
Answer: 8
match(b,c) match(c,b)
Answer: 9
match(d,a) match(a,d)
Answer: 10
match(d,a) match(a,d) match(b,c) match(c,b)
SATISFIABLE

生成候选解决方案以匹配 Clingo/ASP 中的人

Generating Solution Candidates For Matching People in Clingo/ASP

combinatorics

answer-set-programming

clingo