Лексикографически упорядочить два списка переменных с помощью ограничений

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 

Я тогда собирать 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].

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

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

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

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

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

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

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