Sztuczna inteligencja/SI Ćwiczenia 5

Zadanie 1

Zaimplementować w języku PROLOG predykat rozwiązujący problem plecakowy.

Rozwiązanie

% Przykładowy zestaw; lista przedmiotów, przedmiot to [Waga Cena]
zestaw([[1,10],[10,1],[11,10]]).

% Najlepszy plecak będzie zapamiętywany dynamicznie.
:- dynamic najlepszy/2.

% Główny predykat, wywołując podaje się zestaw danych, pojemność plecaka, w
% ostatniej zmiennej zwracana jest odpowiedź.
rozwiaz_plecak(Zestaw,Pojemnosc,Odpowiedz) :-
  assert(najlepszy([],0)),
  plecak(Zestaw,[],Pojemnosc),
  najlepszy(Odpowiedz,_),
  retract(najlepszy(_,_)).

% Rozgałęzienie drzewa przeszukiwań - 2^N; rozgałęzienie przy decyzji: przyjmij
% lub odrzuć przedmiot.
plecak([P|PReszta],Plecak,Pojemnosc) :-
  plecak(PReszta,Plecak,Pojemnosc),             % Jedno poddrzewo bez danego przedmiotu.
  plecak(PReszta,[P|Plecak],Pojemnosc).         % Drugie podrzewo z przedmiotem w plecaku.

% Ocena liścia.
plecak([],Plecak,Pojemnosc) :-
  ocen(Plecak,Wagi,Cena),
  Wagi =< Pojemnosc,
  najlepszy(_,NCena),
  NCena < Cena,
  retract(najlepszy(_,_)),              % Usuń zapamiętany najlepszy plecak.
  assert(najlepszy(Plecak,Cena)).       % Zapamiętaj nowy najlepszy plecak.

% Jeśli liść nie jest lepszy od najlepszego znalezionego plecaka.
plecak([],_,_).

% Predykat obliczający wartość i ciężar plecaka.
ocen([],0,0).

ocen([[Waga,Cena]|Reszta],SumaW,SumaC) :-
  ocen(Reszta,SumaWP,SumaCP),
  SumaW is Waga + SumaWP,
  SumaC is Cena + SumaCP.

Zadanie 2

Zaimplementować w języku PROLOG predykat rozwiązujący problem poszukiwania najkrótszej drogi w grafie.

Rozwiązanie

% Program realizuje algorytm Dijkstry poszukując najkrótszej ścieżki pomiędzy
% dwoma wierzchołkami. Korzysta z predykatów tworzonych dynamicznie, za pomocą
% których implementowana jest kolejka dla przeszukiwania wszerz.

% Przykładowy zestaw danych.
wierzcholki([a,b,c,d,e,f]).
sasiedzi(a,[b,d,f]).
sasiedzi(b,[c,f,a]).
sasiedzi(c,[d]).
sasiedzi(d,[a,e]).
sasiedzi(e,[f,d]).
sasiedzi(f,[d]).

:- dynamic bialy/1,
           szary/1,
           sciezka/2.

% Główny predykat: znajdź ścieżkę od Poczatek do Koniec i zapisz ją w Sciezka
szukaj(Poczatek,Koniec,Sciezka) :-
  wierzcholki(V),                       % pobierz dostępne wierzchołki
  inicjuj(V),                           % inicjuj predykaty
  retract(bialy(Poczatek)),
  assert(sciezka(Poczatek,[Poczatek])),
  assert(szary(Poczatek)),              % pierwszy wierzchołek w kolejce
  dijkstra(Koniec,Sciezka),             % znajdź scieżkę
  !.                                    % uniemożliwiamy nawroty

% Ustawia wszystkie wierzchołki w stanie 'bialy'.
inicjuj([]).
inicjuj([X|Y]) :-
  assert(bialy(X)),
  inicjuj(Y).

% Wyszukaj ścieżkę do Koniec i zapisz ją w Sciezka.
dijkstra(Koniec,Sciezka) :-
  retract(szary(Koniec)),
  sciezka(Koniec,Sciezka).

dijkstra(Koniec,Sciezka) :-
  retract(szary(Wierzcholek)),
  sasiedzi(Wierzcholek,Sasiedzi),
  sprawdz_sasiadow(Wierzcholek,Sasiedzi),
  dijkstra(Koniec,Sciezka).

dijkstra(_,[]).                         % Jeśli dotarł tutaj, to nie ma połączenia.

% Predykat dla każdego sąsiada aktualizuje ścieżkę do niego i dodaje jego
% sąsiadów do kolejki.
sprawdz_sasiadow(_,[]).

sprawdz_sasiadow(Wierzcholek,[Sasiad|Reszta]) :-
  retract(bialy(Sasiad)),
  sciezka(Wierzcholek,Sciezka),         % pobierz ścieżkę do bieżącego wierzchołka
  assert(sciezka(Sasiad,[Sasiad|Sciezka])),
  assertz(szary(Sasiad)),               % dodaj na końcu kolejki
  sprawdz_sasiadow(Wierzcholek,Reszta).

sprawdz_sasiadow(Wierzcholek,[_|Reszta]) :-     % jeśli poprzedni sąsiad nie był wolny
  sprawdz_sasiadow(Wierzcholek,Reszta).

Zadanie 3

Napisać program poszukujący drogi w labiryncie metodą w głąb i wszerz.

Rozwiązanie

Zadanie 4

Rozważmy drzewo genealogiczne. Załóżmy, że krawędzie są skierowane od rodziców w kierunku dzieci. W którym kierunku - zgodnie czy przeciwnie do skierowania krawędzi - lepiej jest prowadzić przeszukiwanie drzewa, chcąc stwierdzić, że X jest prapradziadkiem Y?

Rozwiązanie

Przeszukując graf zgodnie z kierunkiem krawędzi (od rodziców do dzieci) przy każdym węźle możemy mieć inny stopień rozgałęzienia, który odpowiada licznie potomków danej osoby (danego węzła). W zależności od średniej ilości dzieci w drzewie średni stopień rozgałęzienia wynosił będzie od 0 do pewnej wartości $\alpha$. Odległość, którą należy pokonać w głąb grafu wynosi w tym przypadku $n=4$. Zgodnie z punktem wybór metody wnioskowania ilość węzłów ostatniego poziomu do sprawdzenia jest rzędu ${\alpha }^4$.

Przeszukując graf przeciwnie do kierunku krawędzi otrzymujemy zawsze stopień rozgałęzienia równy dwa. W tym przypadku odległość wynosi $n=3$. Ilość węzłów ostatniego poziomu do spradzenia wynosi więc $8$.

Jeśli $\alpha >8^{\frac{1}{4}}\approx 1.68$, to lepiej jest przeszukiwać drzewo przeciwnie do kierunku krawędzi.