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

Я пытаюсь реализовать ограничение лексикографического упорядочения в 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

Затем я собираю B и, чтобы проверить правильность соединения, просто делаю:

(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].

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


list lexicographic prolog clpfd b-prolog
person Bakuriu    schedule 21.10.2015    source источник

Ответы (2)


arrow_upward
2
arrow_downward

В первом предложении 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.
person jschimpf    schedule 23.10.2015

arrow_upward
1
arrow_downward

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

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([], [], _).

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

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

person Bakuriu    schedule 21.10.2015