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 [2012/12/04 11:43] gjn odnosnik do slajdów |
pl:prolog:prolog_lab:constraint_satisfaction_problems [2019/06/27 15:50] (aktualna) |
||
|---|---|---|---|
| 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 234: | Linia 219: | ||
| 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: | 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, Fleciarz i Skrzypek, | + | * określenie zmiennych Lekarz, Prawnik, Inżynier, Pianista, Flecista i Skrzypek, |
| * określenie wspólnej dziedziny dla zmiennych: {andrzej, barbara, celina}. | * 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: | 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 ż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. | * jeśli x jest pacjentem y, to \+ x=y oraz y jest lekarzem. | ||
| Linia 253: | Linia 238: | ||
| \+ 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 = chris, % The engineer is not Chris. | + | \+ 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. | ||
| Linia 268: | Linia 253: | ||
| 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. | 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 [[pl:prolog:prolog_lab:reprezentacja_wiedzy#zagadka_einsteina|tutaj]]. | ||
| + | Jest to nieco inny sposób reprezentowania wiedzy w tego typu zagadkach logicznych. | ||
| ==== - Harmonogramowanie ==== | ==== - Harmonogramowanie ==== | ||
| Linia 330: | Linia 319: | ||
| ==== - 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]). | ||
| Linia 362: | 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), | ||
| Linia 402: | Linia 391: | ||
| * 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]] | ||
| + | |||
