Both sides previous revision
Poprzednia wersja
Nowa wersja
|
Poprzednia wersja
|
pl:prolog:prolog_lab:constraint_satisfaction_problems [2012/12/12 09:15] ikaf zagadka einteina |
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 ==== |
\+ barbara = Doctor, % Barbara is married to the doctor. | \+ barbara = Doctor, % Barbara is married to the doctor. |
Lawyer = Piano, % The lawyer plays the piano. | Lawyer = Piano, % The lawyer plays the piano. |
\+ Engineer = celina, % The engineer is not Celina. | \+ Engineer = barbara, % The engineer is not Barbara. |
Violin = Doctor, % Andrzej is a patient of | Violin = Doctor, % Andrzej is a patient of |
\+ andrzej = Violin. % the violinist. | \+ andrzej = Violin. % the violinist. |
=== Zagadka Einsteina === | === Zagadka Einsteina === |
Przeanalizuj problem i jego rozwiązanie (tzw. zagadka Einsteina) przedstawione [[pl:prolog:prolog_lab:reprezentacja_wiedzy#zagadka_einsteina|tutaj]]. | Przeanalizuj problem i jego rozwiązanie (tzw. zagadka Einsteina) przedstawione [[pl:prolog:prolog_lab:reprezentacja_wiedzy#zagadka_einsteina|tutaj]]. |
Jest to inny sposób reprezentowania wiedzy w tego typu zagadkach logicznych. | Jest to nieco inny sposób reprezentowania wiedzy w tego typu zagadkach logicznych. |
| |
==== - Harmonogramowanie ==== | ==== - Harmonogramowanie ==== |
==== - Zadania fakultatywne ==== | ==== - 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: | * Przepisz szablon predykatu z wprowadzenia na prawdziwy predykat (z wykorzystaniem list oraz [[pl:prolog:prolog_lab:prolog_lab_metaprog|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: |
<code prolog> | <code prolog> |
solution([Variable_1, ..., Variable_n], [domain_1, ..., domain_n], [constraint_1, ..., constraint_m]). | solution([Variable_1, ..., Variable_n], [domain_1, ..., domain_n], [constraint_1, ..., constraint_m]). |
% 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), |
| |
* Stwórz program do rozwiązywania Sudoku 9x9 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. | * Stwórz program do rozwiązywania Sudoku 9x9 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 ==== |
| * [[http://bach.istc.kobe-u.ac.jp/llp/crypt.html|Cryptarithmetic Puzzle Solver]] |
| * [[http://cryptarithms.awardspace.us/primer.html|Primer]] |
| |
| |