March 2020
Wejście i wyjście (31 marca, wykład 5)
30/03/20 21:10
(Obejrzany 45 razy)
Dodatkowo przeczytajcie piąty rozdział z książki W.F. Clocksin, C.S. Mellish. Programming in Prolog (odnośnik powinien działać również spoza kampusu PWr).
DOPISANE
Jeśli kogoś zainteresował problem samoreplikujących się programów, to polecam stronę rosettacode/Quine (dzisiaj dopisałem tam przykład w Prologu jaki pokazywałem na wykładzie).
Comments
Poszukiwanie rozwiązań (24 marca, wykład 4)
23/03/20 19:30
(Obejrzany 91 razy)
O generowaniu rozwiązań, nawracaniu i odcięciu można dodatkowo przeczytać w czwartym rozdziale książki W.F. Clocksin, C.S. Mellish. Programming in Prolog (odnośnik powinien działać również spoza kampusu PWr).
DOPISANE
W prezentację wkradł się błąd. Pokazany na koniec wykładu przykład gry Tetravex, wbrew temu co powiedziałem, nie jest rozwiązywany metodą generowania i testowania. Gdy popatrzymy na definicję predykatu solve/2:
solve(Tiles, Board) :-
board(Board),
insert(Board, Tiles).zauważymy, że nie ma w nim pierwszego etapu generowania rozwiązania i drugiego testowania. Po przygotowaniu predykatem board/1 szkieletu planszy (pola zawierające zmienne, które połączono warunkami unifikacji) następuje wypełnienie szkieletu przez wkładanie do niego klocków predykatem insert/2 (przegląd z nawrotami).
W prosty sposób można przekształcić predykat solve/2, tak by był zgodny z metodą generowania i testowania:
solve(Tiles, Board) :-
insert(Board, Tiles),
board(Board).jednak zmiana taka bardzo wydłużyłaby czas poszukiwania rozwiązania (ponad 3 miliony kroków wnioskowania zamiast 469):
?- solve(t3).
% 3,260,122 inferences, 0.494 CPU in 0.501 seconds (99% CPU, 6596419 Lips)
true ;
% 62,058 inferences, 0.017 CPU in 0.020 seconds (82% CPU, 3749728 Lips)
false.Pamiętajmy, metoda generowania i testowania to pełen przegląd. Stosujmy ją w ostateczności. Jeśli można zaproponować lepszy sposób poszukiwania rozwiązania, to postarajmy się go znaleźć.
Dlaczego pokazana na wykładzie wersja predykatu solve/2 działa dużo szybciej niż ta zgodna z metodą generowania i testowania? Otóż zanim przystępujemy do wypełniania planszy klockami, narzucono już wszystkie równości na odpowiednie zmienne odpowiadające stykającym się ćwiartkom kwadratów. Zatem już częściowo wypełniona plansza może okazać się niedopuszczalna i Prolog wycofa się z tej gałęzi poszukiwań. W wersji pokazanej powyżej, każde umieszczenie klocków na planszy jest dopuszczalne i dopiero po wypełnieniu całej planszy predykatem insert/2 sprawdzany jest predykatem board/1 warunek zgodności kolorów na styku klocków.
Struktury danych (17 marca, wykład 3)
16/03/20 14:20
(Obejrzany 148 razy)
Dodatkowo przeczytajcie trzeci rozdział z książki W.F. Clocksin, C.S. Mellish. Programming in Prolog (odnośnik powinien działać również spoza kampusu PWr). Jeśli uda Wam się zamieścić poniżej pytania do wykładu, to postaram się na nie odpowiedzieć.