LAB: Constraint satisfaction problems

Laboratorium przygotował Mateusz Baran (2012) na podstawie podręcznika Hectora Levesque Thinking as Computation (slajdy). | Based on Hector's Levesque Thinking as Computation (slides).

Celem ćwiczenia jest wprowadzenie do tematyki CSP i zapoznanie się z możliwościami wykorzystania Prologu do rozwiązywania zadań z ograniczeniami.

1 Wprowadzenie

Problem spełniania ograniczeń (ang. Constraing satisfaction problem) składa się z trzech elementów:

  • (skończonego) zbioru zmiennych, których wartości są do znalezienia,
  • skończonych dziedzin dla każdej ze zmiennych (każda zmienna może przyjmować wartość tylko z określonego, skończonego zbioru; różne zmienne mogą przyjmować wartości z różnych zbiorów),
  • ograniczeń, które muszą być spełniane przez odpowiednie podzbiory zmiennych.

Ogólną wersję CSP można zapisać w postaci następującego pseudokodu:

solution(Variable_1, Variable_2, ..., Variable_n) :-
  domain_1(Varaible_1),
  ...
  domain_n(Variable_n),
  constraint_1(Variable,...,Variable),
  ...
  constraint_m(Variable,...,Variable),

Pierwsze linie określają dziedziny poszczególnych zmiennych, następne zaś ograniczenia na nie nakładane. Rozwiązaniem problemu spełniania ograniczeń jest przypisanie wartości poszczególnym zmiennym. Zadanie może mieć oczywiście wiele rozwiązań, dokładnie jedno, lub też nie mieć ich wcale.

Przedstawiony pseudokod może posłużyć jako szablon predykatu rozwiązujący dowolny problem programowania z ograniczeniami. Generowałby on po kolei wszystkie możliwe przypisania wartości zmiennym i sprawdzał, czy spełniają ograniczenia. Nie jest to zbyt efektywna metoda. Poniższe przykłady pokażą, jak można projektować szybsze algorytmy dla pewnych problemów.

2 Kolorowanie mapy

Zadanie kolorowania mapy polega na przypisaniu każdemu z regionów jednego z wybranych kolorów w taki sposób, aby żadne dwa sąsiadujące regiony nie miały takiego samego koloru. Można pokazać (twierdzenie o czterech barwach), że w przypadku regionów na płaszczyźnie wystarczą cztery kolory.

Dla podanej na rysunku mapy można napisać następujący program wyznaczający jej kolorowanie:

solutionMC(A,B,C,D,E) :-
  color(A), color(B), color(C), color(D), color(E),
  \+ A=B, \+ A=C, \+ A=D, \+ A=E, \+ B=C, \+ C=D, \+ D=E.
 
color(red).
color(white).
color(blue).

Porównaj predykat solutionMC z tym ze wstępu. Pierwsza linia określa dziedziny poszczególnych zmiennych (A,B,C,D,E), druga zaś zawiera siedem ograniczeń, każde na pewną parę zmiennych.

Zadania

  1. Uruchom załączony program. Ile różnych kolorowań generuje predykat solutionMC (użyj średnika w SWI-Prologu)?
  2. Narysuj inną mapę z sześcioma obszarami tak, aby potrzeba było czterech kolorów do jej pokolorowania. Odpowiednio zmodyfikuj solution tak, aby generował kolorowanie dla twojej mapy.

3 Sudoku

Jednym z popularnych problemów z ograniczeniami jest łamigłówka Sudoku. Najczęściej jest opisywana w wersji 9×9, jednak dla uproszczenia rozwiążemy wersję 4×4.

Sudoku 4x4.

W pola szachownicy 4×4, spośród których niektóre są już wypełnione, trzeba wpisać liczby od 1 do 4 w taki sposób, aby spełnione były następujące ograniczenia:

  • liczby w każdej kolumnie są różne,
  • liczby w każdym wierszu są różne,
  • liczby w każdym z kwadratów 2×2 (NW, NE, SW, SE) są różne.

Problem rozwiązywany jest przez predykat sudoku z następującego pliku: sudoku.pl. Predykat uniq jest jednak niepoprawnie napisany – powinien on sprawdzać, czy zmienne P, Q, R, S są różne. Przyjrzyj się jednak predykatowi solution z tego pliku. Używa on predykatu uniq nie tylko do testowania, ale także do generowania rozwiązań. Napisz ten predykat tak, aby unifikował zmienne z odpowiednimi liczbami w razie potrzeby.

Z poprawnym predykatem uniq predykat solution będzie mógł sprawdzać, czy w poszczególnych wierszach, kolumnach i kwadratach 2×2 są różne liczby. Przetestuj działanie programu wywołując następujący cel:

sudoku(
1, 4, _, _,
_, _, 4, _,
2, _, _, _,
_, _, _, 3).

Zmodyfikuj program tak, aby wypisywał komunikat o braku rozwiązań, jeśli zagadka ich istotnie nie posiada.

Przestrzeń rozwiązań

Spróbujmy się teraz zastanowić, czy powyższy program zadziałałby (po odpowiednich, łatwych do wyobrażenia modyfikacjach) dla normalnego sudoku 9×9. Na pierwszy rzut oka nie ma powodu, aby było inaczej. Spróbujmy się jednak zastanowić, jak długo taki predykat mógłby być liczony.

Do porównywania problemów programowania z ograniczeniami wprowadza się pojęcie przestrzeni rozwiązań. Jest to zbiór wszystkich możliwych przypisań wartości zmiennym, bez uwzględniania ograniczeń.

  • W Sudoku 4×4 każda z 16 zmiennych może przyjmować jedną z 4 wartości, co daje 416 możliwych przypisań (około 4 miliardy). Taka wartość jest uznawana za małą dla komputerów.
  • W Sudoku 9×9 każda z 81 zmiennych może przyjąć jedną z 9 wartości, dając 981 możliwych przypisań (około 2×1077). Wartość ta jest ogromna.

Porównując wielkości przestrzeni rozwiązań, powolne działanie analogicznego programu dla Sudoku 9×9 nie byłoby zaskoczeniem.

Aby rozwiązać większe Sudoku, potrzeba bardziej wyrafinowanych metod niż proste generowanie rozwiązań i sprawdzanie, czy spełniają ograniczenia. Człowiek, mierząc się z Sudoku nigdy tak nie robi. Jedną z najprostszych metod jest korzystanie z wymuszonych wartości (ang. forced values) – jeśli w pewnym wierszu, kolumnie lub kwadracie wszystkie zmienne poza jedną mają ustalone wartości, wówczas wartość tej ostatniej można jednoznacznie wyliczyć.

4 Problemy kryptoarytmetyczne

Problemy kryptoarytmetyczne są klasą zagadek, w których musimy odgadnąć, jakim cyfrom odpowiadają litery umieszczone w pewnym równaniu. Klasycznym przykładem takiego problemu jest SEND+MORE=MONEY:

  SEND
 +MORE
------
 MONEY  

Za poszczególne litery (S,E,N,D,M,O,R,Y) musimy wstawić różne cyfry od 0 do 9 tak, aby przedstawione dodawanie było poprawne. Zmiennym S i M muszą odpowiadać przy tym wartości różne od zera.

Uruchom i przeanalizuj działanie poniższego programu:

% solution(...) holds for a solution to SEND+MORE=MONEY.
solution(S,E,N,D,M,O,R,Y) :- 
   uniq_digits(S,E,N,D,M,O,R,Y), S > 0, M > 0, 
   Y is (D+E) mod 10, C1 is (D+E) // 10, 
   E is (N+R+C1) mod 10, C10 is (N+R+C1) // 10,
   N is (E+O+C10) mod 10, C100 is (E+O+C10) // 10,
   O is (S+M+C100) mod 10, M is (S+M+C100) // 10.
 
% uniq(...) holds if the arguments are all distinct digits.
uniq_digits(S,E,N,D,M,O,R,Y) :-
   dig(S), dig(E), dig(N), dig(D), dig(M), dig(O), dig(R), dig(Y),
   \+ S=E, \+ S=N, \+ S=D, \+ S=M, \+ S=O, \+ S=R, \+ S=Y,
           \+ E=N, \+ E=D, \+ E=M, \+ E=O, \+ E=R, \+ E=Y,
                   \+ N=D, \+ N=M, \+ N=O, \+ N=R, \+ N=Y,
                           \+ D=M, \+ D=O, \+ D=R, \+ D=Y,
                                   \+ M=O, \+ M=R, \+ M=Y,
                                           \+ O=R, \+ O=Y,
                                                   \+ R=Y.
% The digits
dig(0). dig(1). dig(2). dig(3). dig(4). 
dig(5). dig(6). dig(7). dig(8). dig(9). 

Pierwsza linia predykatu solution generuje, jak w poprzednich przykładach, przypisania wartości do zmiennych, których zgodność z ograniczeniami jest następnie sprawdzana. Zmienne C1, C10 i C100 reprezentują przeniesienie.

Zaprezentowany program działa poprawnie, jednak pewnym problemem jest szybkość działania. Oblicz wielkość przestrzeni rozwiązań dla tego problemu. Istnieją jednak pewne metody przyspieszenia działania. Zaprezentujemy dwie z nich.

Zasada 1.

Jeśli wartość zmiennej jest w pełni wyznaczona przez określone już wartości innych zmiennych (wartość wymuszona), nie próbuj jej zgadnąć i sprawdzać, czy jest poprawna. Dla przykładu zamiast pisać

uniq3(A,B,C),     % zgaduje wartości A,B,C
B is (A+C) mod 10 % sprawdza, czy B spełnia ograniczenie

lepiej napisać

uniq2(A,C),        % zgaduje wartości A i C
B is (A+C) mod 10, % wyznacza B
uniq3(A,B,C)       % sprawdza, czy wartości zmiennych są różne

, gdzie uniq2 i uniq3 sprawdzają (lub generują) odpowiednio dwie lub trzy różne wartości. Przestrzeń rozwiązań drugiego przykładu jest 10 razy mniejsza.

Zasada 2.

Nie umieszczaj niezależnej generacji wartości pomiędzy generowaniem i sprawdzaniem innych wartości. Dużo jaśniejszy niż opis na pewno będzie przykład. Zamiast pisać

dig(A), dig(B), % generuje A i B
dig(C), dig(D), % generuje C i D
A > B           % sprawdza ograniczenie na A i B

lepiej zamienić linię drugą i trzecią:

dig(A), dig(B), % generuje A i B
A > B           % sprawdza ograniczenie na A i B
dig(C), dig(D), % generuje C i D

. Dzięki temu zabiegowi znowu ograniczamy rozmiar przestrzeni rozwiązań.

Szybsze rozwiązanie problemu SEND + MORE = MONEY

Stosując powyższe reguły spróbuj samodzielnie zoptymalizować kod tego problemu.

5 Problem ośmiu hetmanów

Problem ośmiu hetmanów polega na rozmieszczeniu na szachownicy 8×8 ośmiu hetmanów (królowych) tak, aby żadna nie biła dowolnej innej. Aby to zachodziło, wszystkie muszą być w różnych wierszach, kolumnach, lewych oraz prawych przekątnych.

Do opisania tego problemu użyjemy ośmiu zmiennych: C1, …, C8, gdzie Ci oznacza kolumnę w której znajduje się hetman z i-tego rzędu. Ten sposób kodowania zapewnia, że żadni dwaj hetmani nie znajdę się w tym samym wierszu. Pozostałe warunki trzeba jednak sprawdzać. Niezajmowanie tej samej kolumny sprawdzić jest prosto. Można również wykazać, że dla pól na tej samej lewej czy prawej przekątnej odpowiednio różnica i suma współrzędnych są stałe.

Przestrzeń rozwiązań jest dość duża (88 > 16 mln), zatem warto od razu zastosować usprawnienia z poprzedniego przykładu. W istocie będziemy generować pozycje dla kolejnych hetmanów i sprawdzać, czy nie biją któregoś z już umieszczonych – jeśli tak się dzieje, to następuje backtracking i obierane jest inne rozstawienie wcześniejszych hetmanów.

% Solve the 8-queens problem.
solution(C1,C2,C3,C4,C5,C6,C7,C8) :-
  col(C1), 
  col(C2), \+ cap(2,C2,1,C1),
  col(C3), \+ cap(3,C3,1,C1), \+ cap(3,C3,2,C2),
  col(C4), \+ cap(4,C4,1,C1), \+ cap(4,C4,2,C2), \+ cap(4,C4,3,C3), 
  col(C5), \+ cap(5,C5,1,C1), \+ cap(5,C5,2,C2), \+ cap(5,C5,3,C3), 
      \+ cap(5,C5,4,C4),
  col(C6), \+ cap(6,C6,1,C1), \+ cap(6,C6,2,C2), \+ cap(6,C6,3,C3), 
      \+ cap(6,C6,4,C4), \+ cap(6,C6,5,C5), 
  col(C7), \+ cap(7,C7,1,C1), \+ cap(7,C7,2,C2), \+ cap(7,C7,3,C3), 
      \+ cap(7,C7,4,C4), \+ cap(7,C7,5,C5), \+ cap(7,C7,6,C6),
  col(C8), \+ cap(8,C8,1,C1), \+ cap(8,C8,2,C2), \+ cap(8,C8,3,C3), 
      \+ cap(8,C8,4,C4), \+ cap(8,C8,5,C5), \+ cap(8,C8,6,C6), 
           \+ cap(8,C8,7,C7).
 
% The columns
col(1). col(2). col(3). col(4). col(5). col(6). col(7). col(8). 
 
% cap(R1,C1,R2,C2): a queen on (R1,C1) can capture one on (R2,C2).
cap(R,_,R,_).                            % Note the use of the _ here 
cap(_,C,_,C).                            % and here, too.
cap(R1,C1,R2,C2) :- R1-C1 =:= R2-C2.
cap(R1,C1,R2,C2) :- R1+C1 =:= R2+C2.

Uruchom i zrozum powyższy kod.

6 Problemy logiczne

Problemy logiczne stanowią klasę problemów, w których mamy zestaw wskazówek odnośnie tożsamości osób z pewnej grupy. Najłatwiej zademonstrować to przez przykład:

Andrzej, Barbara i Celina ustalają w toku rozmowy, że wykonują trzy różne zawody (lekarz, prawnik, inżynier) i grają na trzech różnych instrumentach (fortepian, flet, skrzypce). Wiedząc, że:

  1. Barbara jest żoną lekarza,
  2. prawnik gra na fortepianie,
  3. Barbara nie jest inżynierem,
  4. Andrzej jest pacjentem skrzypka

ustal kto gra na flecie.

W przypadku problemów logicznych trzeba się najpierw zastanowić, jakie będą zmienne, a jakie ich dziedziny. W powyższym przypadku musimy ustalić osobę wykonującą pewien zawód i grającą na określonym instrumencie, zatem rozsądnym wyborem jest:

  • określenie zmiennych Lekarz, Prawnik, Inżynier, Pianista, Flecista i Skrzypek,
  • określenie wspólnej dziedziny dla zmiennych: {andrzej, barbara, celina}.

Do napisania programu potrzeba jeszcze formalnego określenia znaczenia faktów 1 i 4. Należy to zrobić w następujący sposób:

  • jeśli x jest żoną y, to \+ x=y (jesteśmy nowocześni i nie sprawdzamy, czy płcie małżonków są różne),
  • jeśli x jest pacjentem y, to \+ x=y oraz y jest lekarzem.

Otrzymujemy (po zapisaniu tych warunków) następujący program:

% A logic puzzle involving jobs and musical instruments,
solution(Flute) :-
 
   % Distinct occupations and instruments
   uniq_people(Doctor,Lawyer,Engineer),
   uniq_people(Piano,Violin,Flute),
 
   % The four clues
   \+ barbara = Doctor,     % Barbara is married to the doctor.
   Lawyer = Piano,        % The lawyer plays the piano.
   \+ Engineer = barbara,   % The engineer is not Barbara.
   Violin = Doctor,       % Andrzej is a patient of 
   \+ andrzej = Violin.     %    the violinist.
 
% uniq(...) is used to generate three distinct people.
uniq_people(A,B,C) :- person(A),  person(B),  person(C),  
                      \+ A=B, \+ A=C, \+ B=C. 
 
% The three given people
person(andrzej).   person(barbara).   person(celina).

Zmodyfikuj program, i sprawdź, czy Barbara wyszła za Andrzeja, czy też wybrała drugą z możliwych opcji.

Jednym z problemów pojawiających się podczas rozwiązywania tego typu problemów jest wykrywanie ukrytych zmiennych. Jeśli na przykład trzecie ograniczenie brzmiałoby „Celina nie jest żoną inżyniera”, można wprowadzić dodatkowe zmienne Małżonek_Andrzeja, Małżonek_Barbary, Małżonek_Celiny o odpowiedniej dziedzinie i ograniczane predykatem malzonkowie/3 określającym możliwe trójki wartości nowych zmiennych (pamiętaj – jedna osoba może być na raz w związku z co najwyżej jedną inną osobą). Zmodyfikuj odpowiednio program i przetestuj.

Zagadka Einsteina

Przeanalizuj problem i jego rozwiązanie (tzw. zagadka Einsteina) przedstawione tutaj. Jest to nieco inny sposób reprezentowania wiedzy w tego typu zagadkach logicznych.

7 Harmonogramowanie

Ostatnim przykładem programowania z ograniczeniami jest harmonogramowanie. Obejmuje ono między innymi przypisywanie ludzi do prac czy spotkań do pokoi. Rozpatrzymy przykład, w którym poszczególnym zajęciom będą przypisywane czasy – tak, aby bezkonfliktowo mogły się odbyć w jednej sali.

Przyjmiemy następujące definicje:

  • zmienne: P1, P2, P3, P4, P5, gdzie Pi oznacza czas dla i-tego zajęcia,
  • dziedziny: każdy czas jest pewną godziną pewnego dnia; zostanie on zakodowany jako liczba (100xdzień)+godzina, na przykład wtorek, 14:00 to 214,
  • ograniczenia: wszystkie czasy muszą być dostępne (zajęcia nie mogą na przykład odbywać się w nocy), zajęcia nie mogą następować po sobie, zaś w każdym dniu mogą się odbywać najwyżej dwa zajęcia.

Następująca funkcja generuje dostępne czasy:

% Monday: only 11am and 1pm are available.
taken(X) :- X // 100 =:= 1, \+ X=111, \+ X=113. 
% Tuesday: only 1pm and 2pm are available.
taken(X) :- X // 100 =:= 2, \+ X=213, \+ X=214. 
% Wednesday: nothing available.
taken(X) :- X // 100 =:= 3. 
% Thursday: all available, except for 10am, 12pm, and 2pm.
taken(410). taken(412). taken(414). 
% Friday: nothing available.
taken(X) :- X // 100 =:= 5.
 
uniq_periods(P1,P2,P3,P4,P5) :-
   per(P1), per(P2), per(P3), per(P4), per(P5),
   \+ P1=P2, \+ P1=P3, \+ P1=P4, \+ P1=P5, \+ P2=P3,
   \+ P2=P4, \+ P2=P5, \+ P3=P4, \+ P3=P5, \+ P4=P5.
 
per(P) :- day(D), time(T), P is 100*D+T, \+ taken(P).
 
day(1). day(2). day(3). day(4). day(5).
 
time(9). time(10). time(11). time(12).
time(13). time(14). time(15). time(16).
 
% This program solves a classroom scheduling problem.
solution(P1,P2,P3,P4,P5) :-  
  uniq_periods(P1,P2,P3,P4,P5),       % All different periods.
  not_2_in_a_row(P1,P2,P3,P4,P5),     % Not two consecutive hrs. 
  not_3_same_day(P1,P2,P3,P4,P5).     % Not three on the same day.
 
not_2_in_a_row(P1,P2,P3,P4,P5) :-
  \+ seq(P1,P2), \+ seq(P1,P3), \+ seq(P1,P4), \+ seq(P1,P5),
  \+ seq(P2,P3), \+ seq(P2,P4), \+ seq(P2,P5), \+ seq(P3,P4),
  \+ seq(P3,P5), \+ seq(P4,P5).
 
seq(A,B) :- A =:= B-1.
seq(A,B) :- A =:= B+1.
 
not_3_same_day(P1,P2,P3,P4,P5) :-
  \+ eqday(P1,P2,P3), \+ eqday(P1,P2,P4), \+ eqday(P1,P2,P5),
  \+ eqday(P1,P3,P4), \+ eqday(P1,P3,P5), \+ eqday(P1,P4,P5),
  \+ eqday(P2,P3,P4), \+ eqday(P2,P3,P5), \+ eqday(P2,P4,P5),
  \+ eqday(P3,P4,P5).
 
eqday(A,B,C) :- Z is A // 100, Z is B // 100, Z is C // 100.

Uruchom i przeanalizuj powyższy kod.

8 Zadania fakultatywne

  • Przepisz szablon predykatu z wprowadzenia na prawdziwy predykat (z wykorzystaniem list oraz meta programowania w Prologu) tak, aby rozwiązywał dowolny, zadany w argumentach problem z ograniczeniami. Twój predykat powinien być wołany w następujący sposób:
solution([Variable_1, ..., Variable_n], [domain_1, ..., domain_n], [constraint_1, ..., constraint_m]).

Przetestuj swój predykat na jednym z opisywanych problemów.

  • Przypomnij sobie, ile kolorowań mapy wygenerował predykat solutionMC. Czy dla pewnych ograniczeń wynikających z sąsiedztwa ten predykat może dać dowolną liczbę kolorowań (np. 5)? Uzasadnij swoje przypuszczenia. Napisz predykat generujący wszystkie kolorowania bez przeglądania całego zbioru rozwiązań.

rozwiązanie:

% helper for gen1n
gen1p(1, [1]).
gen1p(N, [N|T]) :- Nm is N-1, gen1p(Nm, T).
 
% generates list [1..N]
gen1n(1, [1]).
gen1n(N, L) :- gen1p(N, Lp), reverse(Lp,L).
 
% assigns successive elements from DomainL to V and fills the VT in
% similar fashion; it's intented to iterate first argument over [1..1]
% to [1,2..,n-1,n,..,n]
memberizeImpl([], _, _).
memberizeImpl([V|VT], DomainL, [HR|TR]) :-
    append(DomainL, [HR], DL2),
    member(V, DL2),
    memberizeImpl(VT, DL2, TR).
memberizeImpl([V|VT], DomainL, []) :-
    member(V, DomainL),
    memberizeImpl(VT, DomainL, []).
 
memberize(Vars, Domain) :- memberizeImpl(Vars, [], Domain).
 
% checks if imposed inequalities hold for given variables
checkMe(_, []).
checkMe(FVars, [[V1n,V2n]|T]) :-
    nth1(V1n, FVars, V1),
    nth1(V2n, FVars, V2),
    V1=\=V2,
    checkMe(FVars, T), !.
 
% generates fresh variables in second argument -- the same number as
% in the first
freshVars([], []).
freshVars([_|To], [_|Tn]) :- freshVars(To, Tn), !.
 
% unifies VH with FVH-th tlement of PDom
unif([], [], _).
unif([VH|VT], [FVH|FVT], PDom) :-
    nth1(FVH, PDom, VH),
    unif(VT, FVT, PDom).
 
% Vars -- variable to solve, Domain -- common domain for all vars
solve(Vars, Domain, Diff) :-
    length(Domain, DomLen),
    gen1n(DomLen, Nums), % Nums=[1..DomLen]
    freshVars(Vars, FVars),!, %len(Vars)=len(FVars), FVars -- new,
                              %fresh variables
    memberize(FVars, Nums),
    checkMe(FVars, Diff),
    permutation(Domain, PDom), % permutes elements in Domain -- we
                               % rely only on equality, so specific
                               % values are irrelevant, therefore we
                               % can assign them in any order to
                               % obtain valid assignment
    unif(Vars, FVars, PDom).
 
% use this to test
solution :-
    solve([A,B,C,D,E], [red, green, blue], [[1,2], [1,3], [1,4], [1,5], [2,3], [3, 4], [4, 5]]),
    format('A = ~w, B = ~w, C = ~w, D = ~w, E = ~w', [A,B,C,D,E]).
  • Stwórz program do rozwiązywania Sudoku 9×9 z wykorzystaniem wartości wymuszonych. Pamiętaj, że nowe wymuszone wartości mogą pojawić się po każdym przypisaniu zmiennej wartości. Sprawdź, jak sobie radzi z łamigłówkami znajdującymi się w Internecie.

Więcej o kryptoarytmetyce

pl/dydaktyka/ai/2017/labs/lab_csp.txt · ostatnio zmienione: 2017/07/17 08:08 (edycja zewnętrzna)
www.chimeric.de Valid CSS Driven by DokuWiki do yourself a favour and use a real browser - get firefox!! Recent changes RSS feed Valid XHTML 1.0