Pretraživanje

1. Na temelju baze znanja o avionskim letovima iz prethodne vježbe, pronađi polazni i odredišni grad te dan u kojem je moguće obaviti putovanje s najvećim brojem letova.

Uputa:
Rješavanje zadataka u kojima je potrebno analizirati sva rješenja nekog predikata se obavlja uz pomoć ugrađenih predikata findall/3, setof/3 i bagof/3. Tako se slijedećim upitom dobiva lista koja sadrži sva putovanja od Ljubljane do Edinburgha:
?-findall(P_t,putovanje(ljubljana,edinburgh,_,P_t),Lista).
Za rješavanje zadatka potrebno je sakupiti sva moguća putovanje kako bi se pronašlo 'najduže'. To se može zatražiti slijedećim ciljem: findall(P_t,putovanje(_,_,_,P_t),Lista).

2. U prethodnom zadatku, predikat putovanje uvijek pronalazi rješenja s konačnim brojem elemenata zbog slijedećih ograničenja:

U općem zadatku pronalaženja puta u usmjerenom grafu takvog ograničenja nema pa se može dogoditi da program, iako deklarativno ispravan, ne bude primjenljiv na ciklički graf.

Za dani graf G, početni čvor s i predikat cilj (koji definira ciljne čvorove), problem pretraživanja se sastoji u određivanju puta od s do t u G tako da vrijedi cilj(t). Većina algoritama prilikom pretraživanja održava dvije liste: lista OTVORENI sadrži čvorove do kojih je postupak došao, ali ih još nije ispitao, dok lista ZATVORENI sadrži već ispitane čvorove. Algoritmi imaju slijedeću temeljnu strukturu: 

  procedura traži(graf G, čvor Početni, predikat Cilj)
    OTVORENI := {Početni}
    ZATVORENI := {}
    pronašao := 0
    dok (OTVORENI nije prazna) i (pronašao==0) radi
      prebaci čvor N iz OTVORENI u ZATVORENI
      ako cilj(N) onda
        pronašao:=1
      inače
        nađi sljedbenike od N u G koji nisu u listama OTVORENI i ZATVORENI
        i dodaj ih u listu OTVORENI
    ako pronašao==1 onda
      vrati N
    inače
      neuspjeh
Često se još dodatno traži da nakon uspješnog pretraživanja, algoritam vrati i put kojim je pronađen ciljni čvor. Pokazuje se da se takav zahtjev može ispuniti jednostavnom modifikacijom temeljnog algoritma.
Različitim strategijama odabira slijedećeg čvora iz liste OTVORENI, dobivaju se algoritmi pretraživanja koji su podesni za različite probleme.

3. Razmatra se problem slagalice, igre u kojoj se na ploči dimenzija MxN nalaze kvadrati označeni brojevima od 1 do M*N-1. Cilj igre je presložiti slagalicu na neku unaprijed zadanu ciljnu poziciju, pomicanjem jednog po jednog kvadrata. Slagalicu je u Prologu najlakše predstaviti listom čiji elementi su liste koje predstavljaju retke slagalice. Ciljna pozicija za slagalicu 3x3, se tako može opisati slijedećom strukturom: 

  [[1, 2, 3],
   [4, 5, 6],
   [7, 8, x]]
Odaberi prikaz pozicije slagalice i napiši proceduru za njen formatirani ispis korštenjem ugrađenog predikata write/1. Napiši predikat pobjeda/1 koji ispituje da li je zadana pozicija konačna. Procedure moraju raditi za proizvoljne dimenzije slagalice (npr. 3x3,4x2,...).

Oblikuj proceduru dohvati(+Pozicija,?Element,?Polje) za manipuliranje elementima slagalice proizvoljnih dimenzija. Procedura treba raditi za slijedeće kombinacije parametara:

Polje predstavi dvočlanom strukturom sa funktorom ":" (dvotočka), čiji su elementi indeksi retka i stupca slagalice koji počinju od nule. Konačno, omogući operatorski zapis strukture (Redak:Stupac).

4. Predikat potez na temelju zadane pozicije pronalazi nove, u koje se može doći legalnim potezima igre. Za njegov rad, potreban je predikat dohvati/3. Ispitaj ispravan rad predikata potez/5 i dohvati/3.

'Slijepe' metode pretraživanja u dubinu i širinu na svom ulazu zahtijevaju relaciju koja definira graf (Arc), početni čvor grafa (Start) i ciljni predikat (GoalPred), a vraćaju listu čvorova grafa (Sol) kao rješenje problema. Predikat closing/1 može biti iskorišten za ispis redosljeda posjećenih čvorova za vrijeme pretraživanja. U našem slučaju, čvorovi grafa su pozicije u igri slagalice, prijelaze između stanja definira predikat potez/5, dok predikat pobjeda/1 definira ciljni čvor grafa. Predikat rijesi/2 povezuje spomenute predikate i pronalazi rješenje pozicije zadane prvim argumentom. U istoj datoteci su zadane i neke pozicije tako da se rješenje igre traži jednostavnim upitom: 

?-igra61(A),rijesi(A,N).

Kod većih programa, pogodno je jednu datoteku zadužiti za učitavanje svih predikata od kojih se program sastoji. Predložena je takva datoteka za ovu vježbu, pod pretpostavkom da je dohvati/3 definiran u datoteci dohvati.pl.

Iskušaj metode pretraživanja u dubinu i širinu za razne dimenzije slagalice. Pri svim eksperimentima, ljusku Prologa pozovi s parametrima -O -G64M -L8M.

5. Korišteni algoritmi pretraživanja su relativno neefikasni pa program 'slijepim' metodama ne pronalazi rješenje slagalica čije su dimenzije veće od 2x3.
Performansa pretraživanja se može poboljšati primjenom heurističkog algoritma kojim se pretraživanje usmjerava na onaj čvor iz liste OTVORENI za kojeg je vrijednost zadane heurističke funkcije Hfun/2 minimalna. Zadana funkcija za svaki čvor grafa daje numeričku procjenu njegove udaljenosti od ciljnog čvora.

Predložena je vrlo jednostavna heuristička funkcija koja vraća broj elemenata zadane pozicije poziciji koji nisu na odgovarajućim mjestima. Unatoč jednostavnosti heurističke funkcije, heurističko pretraživanje je bitno sporije u obrađivanju čvorova. Uvjeri se u to tako što ćeš usporediti vremena obrade različitih metoda pretraživanja na nekoj nerješivoj slagalici, za koju svi algoritmi pretraživanja obilaze sve čvorove grafa.

Ipak, heurističko pretraživanje je vrlo efikasno kod rješivih problema. Tako se heurističkim pretraživanjem mogu riješiti rješive slagalice dimenzija 2x4 i 3x3 koje 'slijepe' metode ne mogu riješiti zbog ograničenog prostora na stogu računala.

6. Pokušaj riješiti slagalicu dimenzija 4x4 boljom heurističkom funkcijom.
Ovaj zadatak nije uvjet za predavanje vježbi.