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

Poniżej znajdują się dwie funkcje, korzystające ze zdefiniowanych wcześniej struktur danych, zmiennych globalnych i funkcji pomocnicznych. Pełna treść programu znajduje się w tym pliku: Media:labirynt.cc.

/* Przeszukiwanie w głąb. Funkcja jest rekurencyjna, dzięki czemu dane z każdego
 * kroku trzymane są bezpośrednio na stosie - nie potrzeba kontenera dla
 * przetwarzanych węzłów przestrzeni przeszukiwań.
 */
void labirynt_wglab (const Pole & poczatek)
{
  odwiedzone (poczatek);

  if (jestGorny(poczatek) && !czyOdwiedzone(gorny(poczatek)))
    labirynt_wglab (gorny(poczatek));

  if (jestLewy(poczatek) && !czyOdwiedzone(lewy(poczatek)))
    labirynt_wglab (lewy(poczatek));

  if (jestDolny(poczatek) && !czyOdwiedzone(dolny(poczatek)))
    labirynt_wglab (dolny(poczatek));
  
  if (jestPrawy(poczatek) && !czyOdwiedzone(prawy(poczatek)))
    labirynt_wglab (prawy(poczatek));
}

/* Przeszukiwanie wszerz. Węzły trzymane są w zwykłej kolejce (FIFO). */
void labirynt_wszerz (const Pole & poczatek)
{ 
  queue<Pole> kolejka;
  kolejka.push (poczatek);
  odwiedzone (poczatek);

  while (!kolejka.empty()) {
    Pole & pole = kolejka.front();

    if (jestGorny(pole) && !czyOdwiedzone(gorny(pole))) {
      kolejka.push (gorny(pole));
      odwiedzone (gorny(pole));
    }
    if (jestLewy(pole) && !czyOdwiedzone(lewy(pole))) {
      kolejka.push (lewy(pole));
      odwiedzone (lewy(pole));
    }
    if (jestDolny(pole) && !czyOdwiedzone(dolny(pole))) {
      kolejka.push (dolny(pole));
      odwiedzone (dolny(pole));
    }
    if (jestPrawy(pole) && !czyOdwiedzone(prawy(pole))) {
      kolejka.push (prawy(pole));
      odwiedzone (prawy(pole));
    }

    kolejka.pop();
  }
}

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^{1 \over 4}\approx 1.68$, to lepiej jest przeszukiwać drzewo przeciwnie do kierunku krawędzi.