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

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