1.   Wstęp

 

Constraint Logic Programming = Programowanie logiczne z użyciem ograniczeń

Ograniczenie to prosta logiczna relacja miedzy kilkoma niewiadomymi (lub zmiennymi), z których każda przyjmuje wartość z danej dziedziny. Np. „koło jest w środku kwadratu” zadaje relację między dwoma obiektami, bez precyzowania ich konkretnej pozycji (czyli ich współrzędnych). Możemy również dodać inny obiekt, powiedzmy trójkąt i stworzyć następne ograniczenie, np. „kwadrat jest po prawej stronie trójkąta”.

CLP jest używane w kilku dziedzinach:

1.      przetwarzanie języków naturalnych (konstruowanie efektywnych parserów)

2.      systemy baz danych (zapewnienie spójności danych)

3.      biologia molekularna (sekwencjonowanie DNA)

4.      inżynieria elektroniczna (lokalizacja błędów)

5.      projektowanie obwodów drukowanych

6.      sporządzanie harmonogramów (ang. scheduling)

7.      etc.

Ideą programowania CLP jest rozwiązywanie problemów poprzez zadawanie ograniczeń (warunków, własności), które muszą być spełniane przez rozwiązanie.

Problem CSP (Constraint Satisfaction Problem), to problem, gdzie są dane:

Rozwiązaniem CSP jest przypisanie każdej zmiennej wartość z jej dziedziny spełniającą wszystkie ograniczenia. Zadaniem jest znalezienie jednego rozwiązania lub wszystkich. W ogólności zadanie postawione w CSP jest obliczeniowo skomplikowane (problem NP-trudny).

 

1.1 Metody rozwiązywania CSP.

1.1.1        Algorytm GT (generate-and-test)

Metoda GT wywodzi się z matematycznego podejścia do rozwiązywania problemów kombinatorycznych. Najpierw algorytm GT zgaduje rozwiązanie a następnie sprawdza, czy to rozwiązanie jest poprawne. W tym paradygmacie, każda możliwa kombinacja przypisań zmiennych jest systematycznie generowana i testowana, po to aby sprawdzić spełnianie wszystkich ograniczeń. Ilość kombinacji rozważana w tej metodzie jest wielkością produktu Kartezjańskiego dziedzin wszystkich zmiennych. Podejście GT jest nieefektywne, ponieważ generuje dużo złych przypisań zmiennych, które są odrzucane w fazie testowania.

1.1.2        Backtracking (BT)

Najbardziej popularnym algorytmem wykonującym przeszukiwanie jest backtracking. Backtracking stopniowo próbuje rozszerzyć częściowe rozwiązanie, które określa zgodność wartości dla pewnych zmiennych, zmierzając do pełnego rozwiązania. W rezultacie backtracking jest znacząco lepszy niż GT, jednakże jego złożoność dla nie trywialnych problemów jest nadal wykładnicza.

 

 

2.   CLP w GNU-Prolog’u

 

GNU Prolog jest darmowym kompilatorem Prolog’a z wbudowanym solverem CLP nad skończonymi dziedzinami.

Solver charakteryzują:

Wprowadzono nowy typ danej: FD-zmienna, która może przyjmować wartości jedynie z własnej dziedziny. Początkowa dziedzina FD-zmiennej wynosi 0..fd_max_integer, gdzie fd_max_integer reprezentuje maksymalną wartość, jaką może przyjąć FD-zmienna. Predykat fd_max_integer/1 zwraca tą właśnie wartość.

 

2.1 Najprostszy przykład

 

?- fd_domain(X,1,3),fd_domain(Y,1,4),X+Y#=3,fd_labeling([X,Y]).

X = 1

Y = 2 ? ;

 

X = 2

Y = 1

yes

 

Opis:

fd_domain(lista_zmiennych_lub_zmienna, min, max)ogranicza dziedzinę zmiennych z listy (lub zmiennej) do przedziału min..max.

X+Y#=3 jest ograniczeniem arytmetycznym na zmienne X,Y. Suma zmiennych musi być równa 3 (#=).

fd_labeling(lista_zmiennych)nadaje zmiennym wartości z ich dziedzin, tak aby spełnione były wszystkie ograniczenia (czyli rozwiązuje zagadnienie CSP).

2.2 Ograniczenia arytmetyczne

 

Symbol

Opis

#=/2

równe

#\=/2

nie równe

#</2

mniejsze

#=</2

mniejsze lub równe

#>

większe

#>=

większe lub równe

fd_prime/1

czy liczba pierwsza

fd_not_prime/1

czy liczba nie jest pierwsza

2.3 Ograniczenia logiczne

 

Symbol

Funkcja logiczna

#\/1

not

#<=>/2

równoważność

#\<=>/2

nie równoważność

##/2

xor

#==>/2

implikacja

#\==>/2

nie implikacja

#/\/2

and

#\/\/2

nand (=not and)

#\//2

or

#\\//2

nor (=not or)

 

 

 

 

2.3 Ograniczenia symboliczne

 

fd_all_different(lista_zmiennych) ogranicza wszystkie zmienne z listy, tak aby przyjmowały różne wartości.

 

fd_element(I, lista_integer, X)ogranicza zmienną X, tak żeby była równa I-temu elementowi listy.

 

fd_atmost(N, List, V) co najwyżej N zmiennych z listy jest równych V.

fd_atleast(N, List, V)co najmniej N zmiennych z listy jest równych V.

fd_exactly(N, List, V) dokładnie N zmiennych z listy jest równych V.

 

 

3.               Przykłady

 

3.1              Układ równań całkowitoliczbowy  (uklad.pl)

% rozwiązuje układ równań z czterema niewiadomymi całkowitymi:

%

% a+4b+c=2

% a+2c=2

% b+c=5

%

% Rozwiązanie:

%   [A, B, C]

%   [3, 2, 1]

 

uklad:-

      LD = [A, B, C],

      fd_domain(LD,-10,10),

      A+3*B+C#=10,

      A+2*C#=5,

      B+C#=3,

      fd_labeling(LD),

      write(LD).

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

3.2              Puzzle  (puzzle.pl)

% rozwiązuje zadanie: przyporządkowanie każdej literze cyfry 0..9

% dokładnie raz tak aby:

%      S E N D

%  +   M O R E

%  -----------

%  = M O N E Y

%

%

% Rozwiązanie:

%  [S,E,N,D,M,O,R,Y]

%  [9,5,6,7,1,0,8,2]

 

 

puzzle:-

      LD=[S,E,N,D,M,O,R,Y],

      fd_all_different(LD),

      fd_domain(LD,0,9),

      fd_domain([S,M],1,9),

 

      1000*S+100*E+10*N+D + 1000*M+100*O+10*R+E

      #= 10000*M+1000*O+100*N+10*E+Y,

      fd_labeling(LD),

      write(LD).

 

3.3              Kwadrat  (kwadrat.pl)

% rozwiązuje problem znalezienia 8 cyfrowej liczby N takiej, ze:

%

% - N jest kwadratem jakiejś liczby

% - jeśli dodamy 1 na początku liczby N w notacji dziesiętnej, to liczba

%   ta jest nadal kwadratem

%

% Rozwiązanie:

%  [N,X,M,Y]

%  [23765625,4875,123765625,11125]

%  [56250000,7500,156250000,12500]

 

kwadrat:-

      (liczba8(L),

      write(L), nl,

      fail

      ;

      write('Wszystkie rozwiązania.'), nl).

 

liczba8(L):-

      L=[N,X,M,Y],

      N #>= 10000000,

      N#=<99999999,

        X**2 #= N,

      100000000+N #= M,

        Y**2 #= M,

      fd_labeling(L).

 

 

 

 

 

 

 

 

 

 

3.4              Mnożenie  (mnozenie.pl)

% rozwiązuje działania pisemnego mnożenia (każda cyfra wykorzystana

% dokładnie 2 razy):

%                   X1  X2  X3

%                 * X4  X5  X6

%                  -----------

%                   X7  X8  X9

%        +      X10 X11 X12

%        + X13 X14 X15

%        = -------------------

%          X16 X17 X18 X19 X20

%

% Rozwiązanie:

% [X1,X2,X3,X4,X5,X6,X7,X8,X9,X10,X11,X12,X13,X14,X15,X16,X17,X18,X19,X20]

% [ 1, 7, 9, 2, 2, 4, 7, 1, 6,  3,  5,  8,  3,  5,  8,  4,  0,  0,  9,  6]

 

 

mnozenie:-

      fd_set_vector_max(9),

      LD=[X1,X2,X3,X4,X5,X6,X7,X8,X9,X10,X11,X12,X13,X14,X15,X16,X17,X18,X19,X20],

      fd_domain(LD,0,9),

      fd_exactly(2,LD,0),

      fd_exactly(2,LD,1),

      fd_exactly(2,LD,2),

      fd_exactly(2,LD,3),    

      fd_exactly(2,LD,4),

      fd_exactly(2,LD,5),

      fd_exactly(2,LD,6),    

      fd_exactly(2,LD,7),

      fd_exactly(2,LD,8),

      fd_exactly(2,LD,9),

 

      Y#=100*X1+10*X2+X3,

      Z1#=100*X7 +10*X8 +X9,

      Z2#=100*X10+10*X11+X12,

      Z3#=100*X13+10*X14+X15,

      X6*Y #= Z1,

      X5*Y #= Z2,

      X4*Y #= Z3,          

 

        100*X7 +10*X8 +X9 + 1000*X10+100*X11+10*X12

      + 10000*X13+1000*X14+100*X15

        #= 10000*X16+1000*X17+100*X18+10*X19+X20,

      fd_labeling(LD),

      write(LD).

 

 

 

 

 

 

Tomasz Bielecki

Janusz Marcinkowski