Sztuczna inteligencja/SI Ćwiczenia 5
Spis treści
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 . Odległość, którą należy pokonać w głąb grafu wynosi w tym przypadku . Zgodnie z punktem wybór metody wnioskowania ilość węzłów ostatniego poziomu do sprawdzenia jest rzędu .
Przeszukując graf przeciwnie do kierunku krawędzi otrzymujemy zawsze stopień rozgałęzienia równy dwa. W tym przypadku odległość wynosi . Ilość węzłów ostatniego poziomu do spradzenia wynosi więc .
Jeśli , to lepiej jest przeszukiwać drzewo przeciwnie do kierunku krawędzi.
