Poszukiwanie rozwiązań (24 marca, wykład 4)

(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.

Tags: nawracanie, odcięcie, generowanie i testowanie, metapredykat, negacja