Both sides previous revision
Poprzednia wersja
Nowa wersja
|
Poprzednia wersja
|
pl:prolog:prolog_lab:constraint_satisfaction_problems [2013/01/14 16:00] gjn Więcej o kryptoarytmetyce |
pl:prolog:prolog_lab:constraint_satisfaction_problems [2019/06/27 15:50] (aktualna) |
| |
//Based on [[http://www.cs.toronto.edu/~hector/|Hector's Levesque]] [[http://mitpress.mit.edu/catalog/item/default.asp?ttype=2&tid=12818|Thinking as Computation]]//. | //Based on [[http://www.cs.toronto.edu/~hector/|Hector's Levesque]] [[http://mitpress.mit.edu/catalog/item/default.asp?ttype=2&tid=12818|Thinking as Computation]]//. |
| |
| |
Celem ćwiczenia jest wprowadzenie do tematyki CSP i zapoznanie się z możliwościami wykorzystania Prologu do rozwiązywania zadań z ograniczeniami. | Celem ćwiczenia jest wprowadzenie do tematyki CSP i zapoznanie się z możliwościami wykorzystania Prologu do rozwiązywania zadań z ograniczeniami. |
| |
| ==== - Do przygotowania ==== |
Wprowadzeniem teoretycznym jest [[http://www.cs.toronto.edu/~hector/PublicTCSlides.pdf|rozdział 5. w.w. książki: ss. 98-151]]. | Wprowadzeniem teoretycznym jest [[http://www.cs.toronto.edu/~hector/PublicTCSlides.pdf|rozdział 5. w.w. książki: ss. 98-151]]. |
| |
| |
=== Szybsze rozwiązanie problemu SEND + MORE = MONEY === | === Szybsze rozwiązanie problemu SEND + MORE = MONEY === |
| Stosując powyższe reguły spróbuj samodzielnie zoptymalizować kod tego problemu. |
Przyjrzyj się teraz rozwiązaniu zagadki kryptoarytmetycznej uwzględniającej powyższe reguły. Predykaty dig i uniq_digits są zdefiniowane jak poporzednio. | |
<code prolog> | |
% solution(...) holds for a solution to SEND+MORE=MONEY. | |
solution(S,E,N,D,M,O,R,Y) :- | |
dig(D), dig(E), | |
Y is (D+E) mod 10, C1 is (D+E) // 10, | |
dig(N), dig(R), | |
E is (N+R+C1) mod 10, C10 is (N+R+C1) // 10, | |
dig(E), dig(O), | |
N is (E+O+C10) mod 10, C100 is (E+O+C10) // 10, | |
dig(S), S > 0, dig(M), M > 0, | |
O is (S+M+C100) mod 10, M is (S+M+C100) // 10, | |
uniq_digits(S,E,N,D,M,O,R,Y). | |
</code> | |
Przyjrzyj się, w jakiej kolejności generowane są wartości kolejnych zmiennych (najpierw D i E, na końcu S i M). Zauważ, że linie zawierające dzielenie przez 10 pozostały bez zmian, tylko rozdzielone przez generowanie wartości zmiennych. Na końcu zaś predykat uniq_digits używany jest tylko do testowania, a nie do generowania wartości zmiennych. Spróbuj zastosować podobną technikę optymalizacji do problemu kolorowania mapy na wybranym przykładzie. | |
| |
==== - Problem ośmiu hetmanów ==== | ==== - Problem ośmiu hetmanów ==== |
% checks if imposed inequalities hold for given variables | % checks if imposed inequalities hold for given variables |
checkMe(_, []). | checkMe(_, []). |
checkMe(FVars, [[student:staze2012:v1n_v2n|T]) :- | checkMe(FVars, [[V1n,V2n]|T]) :- |
nth1(V1n, FVars, V1), | nth1(V1n, FVars, V1), |
nth1(V2n, FVars, V2), | nth1(V2n, FVars, V2), |