2

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

例如：

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

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

4

2 回答 2

3 
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生成何种约束的粗略近似值。

于 2021-06-16T12:41:04.763 回答
1

我会选择Max Ostrowskis的答案。

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

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
于 2021-06-22T13:40:53.577 回答