Лексикографически упорядочить два списка переменных, используя ограничения

Question

Я пытаюсь реализовать ограничение лексикографического порядка в BProlog, используя его CLP(FD).

Насколько я вижу из руководства, BProlog не предоставляет встроенного lexLeq ограничения (хотя существуют эффективные алгоритмы распространения для этого глобального ограничения), поэтому я пытаюсь написать свой собственный и выразить порядок как следующий набор двоичных ограничений:

X1 #=< Y1, (X1 #= Y1) #=> (X2 #=< Y2), (X1 #= Y1 #/\ X2 #= Y2) #=> (X3 #=< Y3), ..., (X1 #= Y1 #/\ ... #/\ XN #= YN) #=> (XN+1 #=< #YN+1)

Выразить (A1 #/\ A2 #/\ ... #/\ AN) => AN+1 ограничение, я думаю, я должен быть в состоянии овладеть Aiс, так что:

domain(B, 0, 1),
(X1 #= Y1) #<=> B

Я тогда собираю Bs и чтобы проверить, что соединение действительно, я просто делаю:

(sum(Bs) #= N) #=> AN+1

Идея приводит к следующему (возможно, очень некрасивому) коду:

lexLeq(Xs, Ys) :-
    lexLeq(Xs, [], Ys, []).

lexLeq([X|Xs], [], [Y|Ys], []) :-
    X #=< Y,
    lexLeq(Xs, [X], Ys, [Y]).
lexLeq([X|Xs], [OldX|OldXs], [Y|Ys], [OldY|OldYs]) :-
    makeAndConstr([OldX|OldXs], [OldY|OldYs], X, Y),
    lexLeq(Xs, [X,OldX|OldXs], Ys, [Y, OldY|OldYs]).
lexLeq([], _, [], _).


makeAndConstr(Xs, Ys, X, Y) :-
    length(Xs, N),
    makeAndConstr(Xs, Ys, [], N, X, Y).

makeAndConstr([X|Xs], [Y|Ys], Bs, N, X, Y) :-
    domain(B, 0, 1),
    (X #= Y) #<=> B,
    makeAndConstr(Xs, Ys, [B|Bs], N, X, Y).
makeAndConstr([], [], Bs, N, X, Y) :-
    (sum(Bs) #= N) #=> (X #=< Y).

Это частично работает:

| ?- domain([A,B,C,D,E,F], 0, 1), lexLeq([A,B,C], [D, E, F]), labeling([A,B,C,$
A = 0
B = 0
C = 0
D = 0
E = 0
F = 0 ?;
A = 0
B = 0
C = 0
D = 1
E = 1
F = 1 ?;
A = 1
B = 1
C = 1
D = 1
E = 1
F = 1 ?;
no

как вы видите, все полученные решения удовлетворяют ограничению. Проблема в том, что не все действующие решения производятся. Кажется, что ограничения, которые я описал, также как-то подразумевают, что X1 #>= X2 #>= ... #>= XN или что-то подобное, так что все переменные либо 0 или же 1в то время как вышеупомянутый запрос должен возвращать также такие решения [0,1,0] против [0,1,0] или же [0,0,0] против [0,1,0],

Итак, что-то не так с моими рассуждениями или есть ошибка в приведенных выше определениях?

Answer 1

В первом пункте makeAndConstr/6, ты используешь X для двух разных целей, что вызывает дополнительные сбои (то же самое для Y). Этот переименованный код работает:

makeAndConstr([X1|Xs], [Y1|Ys], Bs, N, X, Y) :-
    domain(B, 0, 1),
    (X1 #= Y1) #<=> B,
    makeAndConstr(Xs, Ys, [B|Bs], N, X, Y).

Вы могли бы найти это, отследив простую цель, которую вы ожидали добиться успеха, например, lexLeq([0,1],[0,1]),

Упрощенная формулировка лексикографического ограничения порядка

Я хочу поделиться с вами элегантным решением, которому я учил много лет назад мой бывший коллега Уорик Харви. Это выглядит так:

lex_le(Xs, Ys) :-
    lex_le(Xs, Ys, 1).

lex_le([], [], 1).
lex_le([X|Xs], [Y|Ys], IsLe) :-
    IsLe #<=> (X #< Y+RestIsLe),
    lex_le(Xs, Ys, RestIsLe).

что объясняется наблюдением, что IsLe 1, если

• или X<Y (и значение RestIsLe не имеет значения)
• или же X=Y а также RestIsLe это 1.

Answer 2

Хорошо, я нашел возможное, казалось бы, работающее решение:

lexLeq([], []).
lexLeq([X|Xs], [Y|Ys]) :-
    X #=< Y,
    domain(B, 0, 1),
    (X #= Y) #<=> B,
    lexLeq(Xs, Ys, [B]).

lexLeq([X|Xs], [Y|Ys], Bs) :-
    length(Bs, N),
    (sum(Bs) #= N) #=> (X #=< Y),

    domain(B, 0, 1),
    (X #= Y) #<=> B,
    lexLeq(Xs, Ys, [B|Bs]).
lexLeq([], [], _).

Это также намного проще, чем выше.

Разница в том, что в первом решении я создал новый Bs для каждого звонка makeAndConstrвместо того, чтобы повторно использовать то же самое B уже создан. Хотя я не совсем уверен, как это поможет избежать ошибки; это должно быть просто более эффективным.