prolog - 使用约束在 ECLiPSe Prolog 中修剪对称解决方案

Question

这是我目前正在研究的约束满足问题的一个子问题，因此，我省略了应用于变量的额外约束。

假设我们有一个包含 5 个变量的列表，并且说 vars 可以取 1 到 3 之间的值。对称性是这样定义的：假设我们要对所有变量进行 2 个完全赋值。我们还假设对于这些完整分配中的每一个，我们计算具有相同值的变量集。如果我们能找到一种方法，使第一个分配的每个集合在第二个分配中都可以有一个相等/相同的集合，那么这两个分配将是对称的。

这是一个让事情更清楚的小例子：让我们做以下两个作业：

L1 = [ 1, 2, 1, 1, 3 ]
L2 = [ 2, 1, 2, 2, 3 ]

这两个是对称的。让我们也采取以下一个：

L3 = [3, 1, 3, 3, 2]

这也与 L1 和 L2 对称。

我正在尝试修剪所有对称分配。我如何在约束中表达这一点？

到目前为止，我已经尝试使用约束来找到第一个没有赋值的变量，并且基本上用 #=/2; 锁定它的值。对于每个可能的域值，这都会发生一次。我的代码出现实例化错误，但我不确定我的努力是否真的是解决此问题的有效方法。

:-lib(ic).

getNth(0, [ H | T], H, T).
getNth(Count, [ _ | T], Target, Others):-
    NewCount is Count - 1,
    getNth(NewCount, T, Target, Others).

assigned(_, [], TruthVal, TruthVal).
assigned(Var, [Val | OtherVals], CurTruthVal, TruthVal):-
    UpdatedTruthVal #= (CurTruthVal and (Var #\= Val)),
    assigned(Var, OtherVals, UpdatedTruthVal, TruthVal).

firstUnassigned(_, [], _, _, _, _).
firstUnassigned( CurP, [Var | OtherVars], PrevVals, Found, CurCount, Index):-
    assigned(Var, PrevVals, 1, TruthVal),
    (TruthVal and (Found #\= 1)) => ((Index #= CurCount) and (Var #= CurP) and (NewFound #= 1)),
    Found => (NewFound #= Found),
    NewCount is CurCount + 1,
    firstUnassigned(CurP, OtherVars, PrevVals, NewFound, NewCount, Index).

symmetryConstraints(CurP, NP, _, _):-
    CurP > NP.

symmetryConstraints(CurP, NP, L, PrevVals):-
    CurP =< NP,
    firstUnassigned(CurP, L, PrevVals, 0, 0, Index),
    getNth(Index, L, _, NextL),
    NewP is CurP + 1,
    symmetryConstraints(NewP, NP, NextL, [CurP | PrevVals]).

start(L):-
    L = [ Var1, Var2, Var3 ],
    L #:: 1..2,
    length(L, N),
    symmetryConstraints(1, N, L, []),
    search(L, 0, most_constrained, indomain, complete, []).

标签： prologeclipse-clpconstraint-satisfaction