Różnice między wybraną wersją a wersją aktualną.
| 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 [2015/03/23 12:49] kkr [9 Zadania fakultatywne] |
||
|---|---|---|---|
| Linia 5: | Linia 5: | ||
| //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]]. | ||
| Linia 168: | Linia 168: | ||
| === 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 ==== | ||
| Linia 366: | Linia 351: | ||
| % 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), | ||
