Обрезка симметричных решений в ECLiPSe Prolog с использованием ограничений - PullRequest
Новая
       24

Обрезка симметричных решений в ECLiPSe Prolog с использованием ограничений

1 голос
/ 05 июня 2019

Это подзадача проблемы удовлетворения ограничений, над которой я сейчас работаю, и поэтому я пропустил дополнительные ограничения, которые я применяю к своим переменным.

Предположим, у нас есть список из 5 переменных, и указанные переменные могут принимать значения от 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, []).
...