3 RJEŠAVANJE ZADATAKA METODAMA PRETRAŽIVANJA
44
3 RJEŠAVANJE ZADATAKA METODAMA
PRETRAŽIVANJA
Metode rješavanja zadataka koje nazivamo pretraživanje (engl. Search) definirane su kao
detaljno pretraživanje prostora stanja (prostora mogućih rješenja zadatka) gdje tražimo put od početnog
stanja do ciljnog (ili ciljnih) stanja
25
. Pretraživanje je osjetljivo na kombinacijsku eksploziju, pa spada u
slabe metode. Iako su ove metode „slabe”, u posljednjih su nekoliko desetljeća riješile brojne „jake”
probleme, pa su još uvijek temeljne metode rješavanja zadataka u brojnim sustavima umjetne
inteligencije, od problema traženja najboljeg puta, do računalnih realizacija igranja različitih igara,
primjerice šaha.
Prostor rješenja zadataka pretraživanjem može se predstaviti usmjerenim grafom tipa stabla,
kod kojega krećemo od početnog stanja te prolazimo kroz niz međustanja nastojeći doći do jednog od
ciljnih stanja. Metode pretraživanja na sustavni način konstruiraju graf rješenja zadatka. Pri tome se
graf može konstruirati eksplicitno, na početku rješavanja zadatka, pa se postupak traženja puta od
početnog do ciljnog stanja provodi po cijelom prostoru stanja, ili implicitno, dio po dio kako se zadatak
rješava i to samo u dijelu važnom za traženje rješenja.
U svakoj od metoda pretraživanja važne su sljedeće osobine:
• način predstavljanja prostora stanja (prostora problema, prostora rješenja) i to na
formalni, matematički način koji se može jednostavno prenijeti računalnom programu
• izbor prikladnog pravila za prelazak iz stanja u stanje koje se dohvaća iz baze znanja u
kojoj su pohranjena sva dostupna pravila, zapisana na formalni, matematički način i
25
Engleska riječ „search” prevodi se na hrvatski i kao pretraživanje i kao traženje, ali ove riječi u hrvatskom jeziku imaju različito
značenje. Glagol „tražiti” prema Hrvatskom jezičnom portalu (http://hjp.znanje.hr) definira se (među ostalim) kao „truditi se da se
pronađe ono što je izgubljeno, zametnuto ili još nepoznato”, dok glagol „pretražiti” znači „detaljno pregledati, tražeći što”. Kako se u
kontekstu rješavanja zadataka ovom metodom radi „o sustavnom traženju rješenja u prostoru stanja”, engleskoj riječi „search” više
bi odgovarala hrvatska riječ „pretraživanje”.
Pretraživanje je jedan od temeljnih načina kako se rješavaju kompleksni, nealgoritamski
zadaci postupcima umjetne inteligencije. Pretražuje se detaljno i sustavno prostor
mogućih rješenja zadatka (prostor stanja) unutar kojeg nastojimo pronaći put od
početnog stanja iz kojeg krećemo do ciljnog ili ciljnih stanja koje nastojimo doseći. Iako
možda na prvi pogled postupci pretraživanja i ne izgledaju previše „pametni“, uspjeli su
riješiti brojne kompleksne zadatke.
“
„
3 RJEŠAVANJE ZADATAKA METODAMA PRETRAŽIVANJA
45
• vođenje postupka pretraživanja na sustavan način koji omogućava napredak od početnog
prema ciljnim stanjima.
Metode pretraživanja primjenu nalaze kod rješavanja brojnih problema koje grubo dijelimo u
dvije grupe:
• ilustrativni problemi ili kako se uobičajeno nazivaju problemi za igru (engl. Toy
Problems) koji nemaju neku posebnu praktičnu primjenu, već prije svega služe za ilustraciju
i objašnjenje različitih postupaka, te
• stvarni problemi ili kako se uobičajeno zovu problemi stvarnog svijeta (engl. Real-World
Problems) koji nalaze stvarnu primjenu u različitim ljudskim djelatnostima.
Drugi način podjele je na:
• problemi jednog agenta-igrača (engl. Single-agent Problem)
• problemi dva agenta-igrača (engl. Two-players Game) i
• problemi zadovoljenja ograničenja (engl. Constraint-satisfaction Problems).
Kod problema jednog agenta slijed događanja ovisi samo o agentu (igraču) i njegovim potezima.
Zadatak mu je od nekog početnog stanja doći do konačnog stanja na bilo koji način ili na najbolji mogući
način. Tipičan primjer je problem traženja puta (engl. Road Routing Problem) kod kojeg zadatak može
biti samo pronaći put od početne točke do krajnje točke, ali i pronaći najkraći put od početne do krajnje
točke.
Problemi dva agenta su različite igre, na primjer kružić-križić, šah, go. Kod sviju njih sljedeći
potez prvog agenta (igrača) ovisi o potezu drugog agenta (igrača), pa je kompleksnost ovakvih zadataka
puno veća.
Problemi zadovoljenja ograničenja svode se na to da skup objekata treba zadovoljiti određeni
broj ograničenja. Tipični primjeri takvih problema su problemi osam kraljica ili problemi bojanja grafa
koje ćemo u nastavku posebno opisati.
Ilustrativni problemi obično su dobro zadani i precizno opisani, pa se na njima mogu testirati
uspješnosti različitih postupaka pretraživanja, te se zbog toga uobičajeno koriste u udžbenicima iz kojih
se uče temelji umjetne inteligencije. Stvarni su problemi dosta složeniji, ali se u biti temelje na istim
algoritmima, samo s većim stupnjem složenosti.
Primjeri ilustrativnih problema jednog agenta su:
• Različite „mozgalice” – problemski zadaci kod kojih se treba riješiti određeni problem zadan
pričom – tipičan je problem dva vrča koji smo već upoznali u prethodnom poglavlju, u kojem
je zadatak iz nekog početnog stanja napunjenosti vrčeva doći do konačnog stanja koristeći
dozvoljena pravila prelijevanja. Ovaj se problem može i zakomplicirati na n vrčeva. Drugi
primjer je problem farmera, lisice, guske i zrnja (engl. Farmer, Fox, Goose and Grain
Problem)
kod kojeg farmer treba prevesti preko vode lisicu, gusku i zrnje, ali pri tome u čamcu
ne smiju biti lisica i guska ili guska i zrnje. Treći primjer su tornjevi Hanoia (engl. Tower
of Hanoi) kod kojeg se diskovi različitog promjera poredani na jednom od stupova trebaju
prebaciti na drugi, na način da nikada veći disk ne ide iznad manjega, a kod prebacivanja se
može koristiti pomoćni stup (slika 3-1), itd.
• Problem slagalice s praznim mjestom (engl. Sliding Puzzle ili Sliding Block Puzzle)
koja
može imati n x n polja kod koje iz nekog početnog stanja pomičući polja horizontalno ili
vertikalno trebamo doći do ciljnog stanja (primjer slagalice 3 x 3 je na slici 3-2).
• Problem labirinta (engl. Maze Problem) kod kojeg trebamo pronaći put od ulaza do izlaza
iz labirinta. Labirint spada u ilustrativne, školske probleme, ali danas nalazi i direktnu
primjenu u mobilnoj robotici.
3 RJEŠAVANJE ZADATAKA METODAMA PRETRAŽIVANJA
46
Slika 3-1. Problem tornjeva Hanoia
26
Slika 3-2. Problem slagalice s praznim mjestima veličine 3 x 3 s primjerom početnog stanja i željenog
(ciljnog) stanja
Slika 3-3. Problem labirinta s primjerom sustavnog pretraživanja s ciljem pronalaska puta od ulaza do
izlaza labirinta
26
Slika s https://commons.wikimedia.org/wiki/File:Tower_of_Hanoi.jpeg uz CC BY-SA 3.0 licencu.
3 RJEŠAVANJE ZADATAKA METODAMA PRETRAŽIVANJA
47
Primjeri ilustrativnih problema dva agenta su različite igre dvaju igrača:
• Kružić-križić (engl. Tic-Tack Toe) – igra dvaju igrača koju smo sigurno svi barem jednom u
životu igrali. Cilj je postaviti tri svoja znaka horizontalno, vertikalno ili dijagonalno.
Slika 3-4. U igri kružić-križić jedan igrač nastoji postaviti tri svoja znaka u horizontali, vertikali ili
dijagonali, pa je u primjeru sa slike pobijedio kružić
• Šah, možda jedan od najpoznatijih primjera testiranja algoritama umjetne inteligencije,
posebno nakon što je 1997. godine računalni program za igranje šaha poznat pod nazivom
IBM's Deep Blue pobijedio Garija Kasparova, višestrukog svjetskog prvaka 3½ – 2½.
Iako je za neke ova pobjeda bila diskutabilna, činjenica je da je 2006. godine drugi računalni
program za igranje šaha Deep Fritz pobijedio tadašnjeg svjetskog prvaka Vladimira
Kramnika 4 : 2.
• Go, apstraktna, 2500 godina stara strategijska igra dvaju igrača, igra jednostavnih pravila,
ali puno kompleksnija od igre šaha, pa je tek 2015. godine računalni program AlphaGo
pobijedio profesionalnog igrača Go-a bez hendikepa na punoj 19 x 19 ploči. 2016. godine
AlphaGo pobjeđuje korejskog igrača Leeja Sedola, u to vrijeme najboljeg svjetskog igrača
Go-a rezultatom 4 : 1. Više u dodatku iz ovog poglavlja.
Slika 3-5. Go – drevna apstraktna strategijska igra dvaju igrača porijeklom iz Kine – puno kompleksnija
od igre šaha, pa je tek 2015. godine računalni program AlphaGo pobijedio profesionalnog igrača Go-a na
punoj ploči bez hendikepa
27
27
Slika je s web-stranice https://commons.wikimedia.org/wiki/File:13_by_13_game_finished.jpg uz CC BY-SA 2.0
licencu.
3 RJEŠAVANJE ZADATAKA METODAMA PRETRAŽIVANJA
48
Ilustrativni problemi koji spadaju u probleme zadovoljenja ograničenja su:
• Problem osam kraljica (engl. Eight Queens Puzzle)
kod kojeg treba na šahovsku ploču 8 x
8 postaviti 8 kraljica na način da se kraljice međusobno ne ugrožavaju. Edsger Dijkstra je
1972. godine baš ovaj problem koristio kod opisa strukturnog programiranja uz detaljni opis
tzv. backtracking algoritma temeljenog na dubinskom pretraživanju.
Slika 3-6. Problem osam kraljica – kraljice treba postaviti na šahovsku ploču tako da se međusobno ne
ugrožavaju
• Problem bojanja grafa (engl. Graph Coloring Problem)
(2D ili 3D) ima dvije inačice: bojanje
vrhova grafa na način da dva vrha povezana stranicom nemaju istu boju ili bojanje stranica
grafa kada dvije stranice povezane istim vrhom ne smiju biti bojane istom bojom.
Slika 3-7. Problem bojanja grafa
• Različite „slagalice”, na primjer križaljke, sudoku, kakuro, hidato, ali i logičke zagonetke.
Posebno zanimljiv primjer logičkih zagonetki su zagonetke logičke tablice (engl. Logic
Grid Puzzles), na primjer Einsteinova zagonetka (engl. Einstein's Riddle). Temelji se na
tome da se postavi određeni broj logičkih izjava (tvrdnji) vezanih uz stanare 5 kuća, njihovih
omiljenih pića, cigareta i ljubimaca. Na primjer „Postoji pet kuća.”, „Englez živi u crvenoj
kući.”, „Španjolac ima psa.” itd. Jedan od kućnih ljubimaca je ribica, pa je pitanje na koje se
treba odgovoriti: “Tko ima ribicu za ljubimca?” Druga varijanta ove zagonetke je malo
drugačija i naziva se zebra zagonetka (engl. Zebra Puzzle) zato što se traži tko ima zebru
za ljubimca. U dodatku ovog udžbenika, u dijelu koji se bavi programskim jezikom Prolog,
zagonetka je detaljno objašnjena i riješena u Prologu.
3 RJEŠAVANJE ZADATAKA METODAMA PRETRAŽIVANJA
49
Kod problema stvarnog svijeta koriste se isti algoritmi, ali se primjenjuju za rješavanje
stvarnih problema u pojedinim područjima. Tipični primjeri su:
• Problem pronalaska puta (engl. Route Finding Problem)
od neke početne pozicije do
konačnog odredišta. Ovaj smo tip problema već spominjali u obliku problema najkraćeg
puta, problema trgovačkog putnika i problema kineskog poštara. Problem
najkraćeg puta (engl. Shortest Path Problem)
često se koristi kao primjer na kojem se
ilustriraju razlike različitih algoritama pretraživanja, pa ćemo ga i u ovom udžbeniku
koristiti na primjeru otoka Brača. Slika 2-3 prikazuje cestovnu mrežu otoka Brača koju smo
koristili kod objašnjavanja problema trgovačkog putnika, dok ovdje ilustriramo problem
najkraćeg puta, ali na pojednostavljenoj cestovnoj mreži otoka Brača na kojoj smo istakli 8
naselja: Supetar (S), Donji Humac (A), Nerežišća (B), Splitska (C), Pučišća (D), Pražnice E),
Gornji Humac (F) i Sumartin (G). Slika 3-8 prikazuje zadatak i formalno u obliku otežanog
grafa, gdje su čvorovi gradovi simbolički prikazani slovima, a težine na granama
predstavljaju zaokružene udaljenosti između njih iskazane u kilometrima. Zadatak je
pronaći najkraći put između dvaju gradova – u našem slučaju to će biti najkraći put između
Supetra i Sumartina. Postoji ukupno 6 različitih putova, a samo je jedan od njih najkraći.
Ovaj ćemo primjer koristiti kod opisa različitih algoritama pretraživanja.
Slika 3-8. Cestovna mreža otoka Brača i formalno prikazani problem najkraćeg puta na
pojednostavljenoj mreži s 8 naselja otoka Brača
• Upravljanje digitalnim prometom (engl. Routing Problem)
od izvora do konačnog
odredišta preko mrežnih usmjerivača, komutatora i koncentratora.
• Kod projektiranja integriranih sklopova, posebno VLSI (engl. Very-Large-Scale
Integration), algoritmi pretraživanja se koriste kod pozicioniranja milijuna komponenti i
priključaka na čipu kako bi se smanjila površina i skratilo kašnjenje signala.
• Robotska navigacija koja je zapravo prebacivanje problema labirinta u realni prostor.
Danas, sa sve većom pojavom autonomnih vozila, ovo područje postaje sve zanimljivije.
• Automatsko sekvenciranje montaže (engl. Automatic Assembly Sequencing)
čiji je cilj
pronaći redoslijed za sastavljanje složenog objekta od sastavnih dijelova koji ponekad mogu
biti i geometrijski složeni.
• Dizajn proteina kojem je zadatak utvrđivanje niza aminokiselina koje će se presaviti u 3D
protein s točno određenim svojstvima za liječenje neke bolesti.
3 RJEŠAVANJE ZADATAKA METODAMA PRETRAŽIVANJA
50
• Pronalaženje grešaka u kodu (engl. Code Debugging)
– ovo je područje u posljednjih
desetak godina posebno zanimljivo, a cilj mu je automatska analiza programskog koda i
pronalaženje mogućih pogrešaka.
Primjera je je još puno, ali kada se shvati kako algoritmi pretraživanja funkcioniraju, lako ih je i
primijeniti. U nastavku spominjemo neke zajedničke karakteristike postupaka pretraživanja, a nakon
toga prikazujemo osnovne tipove algoritama pretraživanja, od jednostavnih do složenih.
3.1
Predstavljanje prostora problema (prostora pretraživanja)
Prostor problema, ili kako se češće zove prostor pretraživanja (engl. Search Space), je prostor
u kojem tražimo rješenje problema. Ovaj prostor grafički predstavljamo grafom tipa stablo koji nazivamo
stablo rješenja problema. U slučaju problema punjenja dvaju vrčeva dio stabla problema prikazuje
slika 2-2, a kod problema trgovačkog putnika cjelovito stablo problema prikazuje slika 2-4. Stablo
problema gradi se postupno i sustavno od početnog stanja do ciljnog kod unaprijednog pretraživanja i
obrnuto, od ciljnog stanja do početnog kod povratnog pretraživanja. Postupci pretraživanja razlikuju se
upravo po tome kako se gradi stablo rješenja problema, ali bez obzira o kojem se postupku radi, obavezno
treba biti ugrađen mehanizam koji ne dozvoljava stvaranje petlji i vraćanje unatrag. Na primjeru
problema dvaju vrčeva sa slike 2-2 to na primjer znači da smo na trećoj razini naišli na stanje (0,0) od
kojeg smo krenuli, pa se to stanje dalje ne razvija. Nadalje, ako na istoj razini postoje dva identična stanja,
na primjer stanja (4,3) na trećoj razini problema dvaju vrčeva, dalje se razvija samo jedno od njih (obično
prvo).
Postupak sustavnog građenja stabla rješenja problema ima i svoju specifičnu terminologiju:
• čvor (engl. Node) – moguće rješenje u problemskom prostoru pretraživanja u kojem
odlučujemo kojim putem ići dalje
• poveznica (engl. Link ili Edge) – veza između dvaju čvorova kojoj može biti pridružena
određena težina (npr. broj pravila koje smo primijenili u problemu dvaju vrčeva ili udaljenost
između dvaju gradova u problemima pronalaženja puta)
• grana (engl. Branch) – put između više čvorova – sastoji se od čvorova kroz koje se prolazi i
grana kojima se prolazi
• roditelji (engl. Parents) – čvorovi koji se u stablu rješenja problema nalaze iznad čvorova
djece (engl. Child)
• predci (engl. Anecestors) – svi roditeljski čvorovi na određenoj razini
• potomci (engl. Descendents) – svi nasljednici nekog čvora
• korijenski čvor (engl. Root Node) – početni čvor od kojeg krećemo
• ciljni čvor (engl. Goal Node) – završni čvor do kojeg želimo doći (može ih biti i više)
• proširiti čvor (engl. Expanding the Node) – uključiti u stablo rješenja problema svu djecu
određenog čvora
• faktor grananja (engl. Branching Factor)
b – broj djece određenog roditeljskog čvora.
Čvor koji smo već uključili, ali nismo još proširili zove se otvoreni čvor (engl. Open Node), a onaj
koje smo već proširili zove se zatvoreni čvor (engl. Closed Node).
Formalna definicija prostora pretraživanja je šestorka:
(S, A, c, s
0
, S
g
, h
0
) (3-1)
gdje su:
S – konačni skup svih mogućih rješenja {s
i
} kojim gradimo prostor pretraživanja
A – konačni broj akcija {a
k
} (operatora prijelaza) koje dozvoljavaju prelazak iz jednog čvora
(mogućeg rješenja) u drugi
3 RJEŠAVANJE ZADATAKA METODAMA PRETRAŽIVANJA
51
c – cijena prijelaza iz jednog čvora u drugi c(i,j) korištenjem neke od akcija iz skupa A
s
0
– početno stanje
S
g
– skup svih ciljnih stanja {s
gj
} u biti podskup skupa S (Sg ! S) – treba biti najmanje jedno
ciljno stanje s
g
, ali ih može biti i više
h
0
– heuristička funkcija koja je poznata na početku i pomaže u usmjeravanju postupka
pretraživanja.
Pogledajmo nekoliko primjera:
Slagalica 3 x 3 (slika 3-2)
Prostor pretraživanja gradimo devetorkama brojeva kojima prikazujemo pojedino stanje
slagalice. Za prazno mjesto koristimo 0. Na primjer, početno stanje s
0
je (8, 0, 6, 5, 4, 7, 2, 3, 1) i imamo
samo jedno ciljno stanje s
g
(0, 1, 2, 3, 4, 5, 6). Prostor pretraživanja može činiti ukupno 181440 različitih
kombinacija (|S| = 9!/2).
Dozvoljene akcije su pomak lijevo, desno, dolje i gore na mjesto gdje se nalazi 0, s tim da su sve
dozvoljene jedino ako je 0 na 5. mjestu u prikazu stanja slagalice. Ako je 0 na rubovima slagalice (na 1.,
3. 7. i 9. mjestu), dozvoljena su samo dva poteza lijevo (ili desno) ili gore (ili dolje). Treća je situacija kada
je 0 na rubu u sredini (na 2. , 4. , 6. i 8. mjestu) i kada su moguća tri poteza. Na primjer, dvije dozvoljene
akcije kada je 0 na 1. mjestu možemo prikazati implikacijama:
(0, x, ?, ?, ?, ?, ?, ?, ?) → (x, 0, ?, ?, ?, ?, ?, ?, ?)
(0, ?, ?, x, ?, ?, ?, ?, ?) → (x, ?, ?, 0, ?, ?, ?, ?, ?)
Ukupno postoje 24 ovakve akcije koje uključuju sve moguće poteze, ovisno o tome gdje se 0 nalazi.
U ovom slučaju |A| = 24.
Cijena prijelaza c je 1 (sve su akcije jednako vrijedne).
Faktor grananja b kod ovog zadatka je 2, 3 ili 4 (b
∈
{2,3,4}).
O heurističkoj funkciji za ovakav tip zadatka kasnije će biti više govora. Ona pomaže u
usmjeravanju postupka pretraživanja.
Problem najkraćeg puta na primjeru otoka Brača (slika 3-8)
Prostor pretraživanja čini 8 naselja otoka Brača: Supetar (S), Donji Humac (A), Nerežišća (B),
Splitska (C), Pučišća (D), Pražnice E), Gornji Humac (F) i Sumartin (G), tako da se u svakom čvoru nalazi
jedno od slova koja predstavljaju ova naselja.
Početno stanje s
0
je naselje Supetar (S), a ciljno stanje s
g
naselje Sumartin (G). Cilj smo dosegli
ako se u nekom od novootvorenih čvorova pojavi G.
Dozvoljene akcije definirane su slikom 3-8 koja prikazuje iz kojeg se grada može ići u koji, a
možemo ih definirati i tablicom 3-1 koja ujedno daje i cijenu (c) prijelaza iz jednog čvora prostora
pretraživanja u drugi.
Tablica 3-1. Dozvoljene akcije (operatori prijelaza) u zadatku najkraćeg puta na otoku Braču gdje X znači da ne
postoji direktni put između naselja
Supetar
(S)
Donji
Humac
(A)
Nerežišća
(B)
Pučišća
(D)
Pražnice
(E)
Gornji
Humac
(F)
Sumartin
(G)
Supetar (S)
0
8
9
X
X
X
X
Donji Humac (A)
8
0
2
X
X
X
X
3 RJEŠAVANJE ZADATAKA METODAMA PRETRAŽIVANJA
52
Nerežišća (B)
9
2
0
X
13
X
X
Splitska (C)
7
X
8
22
X
X
X
Pučišća (D)
X
X
X
0
11
X
X
Pražnice (E)
X
X
13
11
0
4
X
Gornji Humac (F)
X
X
X
X
4
0
16
Sumartin (G)
X
X
X
X
X
16
0
Faktor grananja i u ovom je zadatku 1, 2 ili 3, a heurističku funkciju kasnije ćemo detaljnije
razmatrati.
U ovom tipu zadatka nije nam samo cilj doći u konačno, ciljno stanje već i odrediti put do njega.
Zbog toga se kod formalnog definiranja ovog zadatka koristi izmijenjena notacija koja u sebi uključuje i
prijeđeni put. Slika 3-9 prikazuje dio stabla rješenja problema i način kako se pojedini čvor formalno
označava.
Slika 3-9. Dio stabla rješenja problema najkraćeg puta bez udaljenosti s formalnim označavanjem
čvorova koji uključuju i informaciju o redoslijedu prolaska čvorova
Početni čvor je S i iz njega krećemo. Njegova djeca su čvorovi A, B i C, ali mi ih označavamo SA,
SB i SC kako bismo sačuvali informaciju o tome da smo već bili u čvoru S i iz njega došli u čvorove A, B,
C. Isti se princip primjenjuje i dalje. Iz čvora A možemo ići u čvor B ili se vratiti u S, pa su njegova djeca
SAB i SAS. Na ovaj način jednostavno detektiramo i to jesmo li se vratili unatrag i započeli petlju. Drugi
nasljednik SAS kaže da smo se iz A vratili natrag u S, pa u nastavku nema smisla dalje nastavljati
njegovo proširivanje, zato što ćemo se vrtjeti u petlji. Ista je situacija u nastavku pa SABA kaže da nam
je ovo drugi put u čvoru A, znači vrtimo se u petlji. Ovaj zadatak ima 6 mogućih rješenja koje prikazuje
slika 3-10.
Od svih rješenja jedno je najbolje zato što je ukupni prijeđeni put najkraći (42 km). Kako se do
njega može sustavno doći, opisujemo u sljedećim poglavljima.
3 RJEŠAVANJE ZADATAKA METODAMA PRETRAŽIVANJA
53
Slika 3-10. Sva moguća rješenja zadatka najkraćeg puta
3.2
Izbor prikladnog pravila
Do sada smo naglasili da se postupak rješavanja zadatka sastoji od traženja rješenja u prostoru
pretraživanja uz pomoć pravila koja opisuju moguće akcije, prijelaz iz jednog stanja u drugo, ali još ništa
nismo rekli o tome kako u svakom pojedinom koraku izabrati najprikladnije pravilo, na koji način graditi
stablo rješenja problema.
Moguće akcije kojima se iz jednog stanja prelazi u drugo definirane su skupom A. Najjednostavniji
način izbora pravila je sustavni prolazak kroz sva pravila uz odabir onoga kojeg možemo primijeniti u
trenutnom stanju. Međutim, ova metoda ima nedostatak ako je broj pravila velik, a to je čest slučaj kod
stvarnih primjena.
Postupci pretraživanja baš se i razlikuju po tome koja pravila odabiremo i na koji način
nastavljamo graditi stablo rješenja problema. Strategije pretraživanja obično dijelimo na:
• unaprijedno i
• povratno pretraživanje,
te na:
• neinformirano i
• informirano pretraživanje,
o čemu će biti više riječi u nastavku. Kod vrednovanja pojedine strategije pretraživanja postavljamo četiri
pitanja:
• Je li se sigurno nalazi rješenje?
• Je li rješenje najbolje?
3 RJEŠAVANJE ZADATAKA METODAMA PRETRAŽIVANJA
54
• Kolika je vremenska složenost?
• Kolika je prostorna složenost?
Vremenska složenost vezana je s brojem razina u kojima se šire čvorovi i zamjenjuju njihovom
djecom, a prostorna složenost vezana je s brojem otvorenih čvorova. Ove obje veličine ovise o:
• b – faktoru grananja koji smo već spominjali (obično se koristi prosječni faktor grananja, ali
može i najveći)
• m – dubini na kojoj se očekuje najbolje rješenje (rješenje s najmanjom cijenom puta)
• d – maksimalnoj dubini stabla rješenja problema (može biti i beskonačna).
Ako postupak pretraživanja sigurno pronalazi rješenje i to najbolje, te ako uz to ima i malu
prostornu i vremensku složenost, onda je on sigurno bolji od onoga koji nam ne garantira da se do rješenja
uopće može doći.
3.3
Unaprijedno i povratno pretraživanje
Cilj postupka pretraživanja je otkrivanje puta u prostoru mogućih rješenja od početnog stanja do
ciljnog stanja. Postoje dva smjera u kojima se pretraživanje može provesti:
• unaprijed – od početnog stanja prema ciljnom stanju – unaprijedno pretraživanje (engl.
Forward Chaining)
• unatrag – od ciljnog stanja prema početnom stanju – povratno pretraživanje (engl.
Backward Chaining).
Kod unaprijednog pretraživanja testira se lijeva strana pravila koja definira uvjete da bi se
dotično pravilo primijenilo, dok se kod povratnog pretraživanja testira desna strana (mogući rezultat).
Kao ilustrativni primjer pogledajmo temeljnu strukturu ekspertnog sustava. Radi se o dijagnostičkom
ekspertnom sustavu industrijskog procesa. Baza znanja sastoji se od 4 različita tipa uzročno-
posljedičnih pravila (engl. If-Then Rules):
1. Ako <okidač> tada predlažem <hipotezu>.
Na osnovu opažanja situacije ili opažanja stanja produkta postavlja se određena hipoteza.
Kao primjer možemo uzeti ekspertni sustav za pečenje kolača:
„Ako je kolač izgorio, tada je peć previše vruća.”
2. <Hipoteza> je uzrokovana <pogreškom>.
Razmatramo što je moglo uzrokovati hipotezu:
„Peć je previše vruća ako je zakazalo hlađenje.”
3. <Greška> se potvrđuje <testom>.
„Hlađenje je zakazalo ako je ventil na ON, priključak vode je hladan i pumpa ne vibrira.”
4. Ako je <greška> tada poduzmi <akciju>.
„Ako je hlađenje zakazalo i pumpa ne vibrira, tada je potrebno zamijeniti pumpu.”
Unaprijedno zaključivanje je pretraživanje od opažene posljedice (okidača) preko hipoteze, greške,
prema akciji. Npr. početak traženja iniciran je činjenicom „Kolač je izgorio.”. Kod povratnog zaključivanja
krećemo unatrag, npr. od testa da pumpa ne vibrira i idemo unatrag dok ne dođemo do moguće posljedice,
a jedna od njih će biti da kolač može izgorjeti.
Kod problema najkraćeg puta unaprijedno pretraživanje je traženje puta od Supetra do
Sumartina, a povratno pretraživanje od Sumartina do Supetra.
Ponekad je jedan od smjerova pretraživanja efikasniji od drugoga, odnosno s njim brže dolazimo
do rezultata, pa obično sve metode heurističkog traženja imaju mogućnost i unaprijednog i povratnog
3 RJEŠAVANJE ZADATAKA METODAMA PRETRAŽIVANJA
55
pretraživanja. Pitanje je može li se pretpostaviti na osnovu značajki zadatka koje je pretraživanje
efikasnije. Neki od faktora koji na to utječu su:
• Ima li više početnih ili ciljnih stanja? – Obično idemo od onog stanja koje ima manji broj
varijacija.
• U kojem je smjeru faktor grananja veći? – Bolji je onaj smjer u kojem je faktor grananja manji.
• Ako moramo objašnjavati postupke, tada je bolji onaj smjer kod kojeg imamo bolje poklapanje
sa slijedom ljudskih misli.
3.4
Neinformirano i informirano pretraživanje
Druga podjela postupaka pretraživanja je vezana uz informacije s kojima raspolažemo kada
širimo čvorove i gradimo stablo rješenja problema.
Ako pri odabiru strategije pretraživanja ne koristimo nikakve informacije, onda se takvo
pretraživanje naziva neinformirano pretraživanje (engl. Non-informed Search), slijepo
pretraživanje (engl. Blind Search) ili pretraživanje grubom silom (engl. Brute Force Search).
S druge strane, ako kod odabira načina izgradnje stabla problema koristimo neke informacije koje
mogu biti pouzdane, determinističke, ali i nepouzdane, heurističke, tada se pretraživanje zove
informirano pretraživanje (engl. Informed Search) ili usmjereno pretraživanje (engl. Directed
Search). Sigurno je da su ovakve strategije pretraživanja efikasnije.
3.5
Neinformirano ili slijepo pretraživanje
Neinformirano ili slijepo pretraživanje zahtijeva poznavanje:
• početnog stanja
• dopuštenih akcija prijelaza iz jednog stanja u drugo i
• testa kojim se provjerava jesmo li došli u ciljno stanje.
Primjer postavljanja zadatka najkraćeg puta kod neinformiranog pretraživanja prikazuje slika 3-
11:
Slika 3-11. Cestovna mreža otoka Brača i formalno prikazani problem najkraćeg puta na
pojednostavljenoj mreži s 8 naselja otoka Brača za neinformirano (slijepo) pretraživanje
3 RJEŠAVANJE ZADATAKA METODAMA PRETRAŽIVANJA
56
Jedina dostupna informacija je koja su naselja direktno povezana, pa tablicu dozvoljenih akcija
prikazuje tablica 3-2.
Kod slijepog pretraživanja najbolje rješenje je ono koje se pronađe u najmanjem broju koraka
(najmanjem broju razina stabla rješenja problema). Na primjeru svih mogućih rješenja problema
najkraćeg puta na slici 3-10 vidimo da se prvo rješenje pronalazi na 5. razini, nakon pet širenja čvorova.
Pri tome je put opisan sa SBEFG. Za njega je ujedno i put najkraći, ali kod slijepog traženja informacija
o prijeđenom putu nije nam važna, zato što nije poznata. U ovom se primjeru poklopilo da je put s
najmanjim brojem koraka i najkraći, ali to nije opće pravilo. Najgore je rješenje prvo rješenje na lijevoj
strani kojem treba 8 razina, a put je SABCDEFG.
Strategije neinformiranog ili slijepog pretraživanja razlikuju se po tome kako se prilikom širenja
čvora odlučuje kojim putem ići u sljedećoj razini širenja. Dva su pristupa:
• sustavni pristup kod kojega se na unaprijed dogovoreni način odlučuje na koji način graditi
stablo rješenja zadatka (pretraživanje u širinu, pretraživanje u dubinu, pretraživanje
ograničeno po dubini i iterativno pretraživanje u dubinu), te
• slučajni pristup kod kojeg nema nikakvih pravila kako u nekom čvoru odabrati put kojim
ćemo nastaviti graditi stablo rješenja zadatka (ne-determinističko slijepo pretraživanje).
Tablica 3-2. Dozvoljene akcije (operatori prijelaza) u zadatku najkraćeg puta na otoku Braču za
neinformirano (slijepo) pretraživanje gdje D znači da postoji, a X da ne postoji direktni put između
naselja
Supetar
(S)
Donji
Humac
(A)
Nerežišća
(B)
Pučišća
(D)
Pražnice
(E)
Gornji
Humac
(F)
Sumartin
(G)
Supetar (S)
0
D
D
X
X
X
X
Donji Humac (A)
D
0
D
X
X
X
X
Nerežišća (B)
D
D
0
X
D
X
X
Splitska (C)
D
X
D
D
X
X
X
Pučišća (D)
X
X
X
0
D
X
X
Pražnice (E)
X
X
D
D
0
D
X
Gornji Humac (F)
X
X
X
X
D
0
D
Sumartin (G)
X
X
X
X
X
D
0
Svi ovi algoritmi mogu biti jednodirekcijski, kada se ide od početnog stanja prema ciljnom kod
unaprijednog pretraživanja, ili od ciljnog prema početnom kod povratnog pretraživanja, ali i
bidirekcijski kada se istovremeno kreće unaprijed i unatrag, pa je zadatak riješen kada se dva smjera
pretraživanja poklope u istom stanju (istom čvoru stabla rješenja problema).
3.5.1 Pretraživanje u širinu
Pretraživanje u širinu (engl. BFS – Breadth First Search)
je jedan od temeljnih sustavnih
postupaka pretraživanja kod kojeg se na svakoj razini šire svi čvorovi koji se mogu otvoriti. Slika 3-12
prikazuje nekoliko koraka u formiranju stabla rješenja postupkom pretraživanja u širinu za zadatak
najkraćeg puta sa slike 3-11.
3 RJEŠAVANJE ZADATAKA METODAMA PRETRAŽIVANJA
57
Slika 3-12. Nekoliko koraka u izgradnji stabla rješenja problema kod pretraživanja u širinu
Prema slici 3-10 vidimo da će se pretraživanjem u širinu pronaći najbolje rješenje, zato što će se
na 5. razini prvi put doći do cilja (naselja G), pa će test zaustaviti daljnje traženje.
U ovom ćemo dijelu algoritam pretraživanja prikazati pseudokodom (algoritam 3-1), a u nastavku
će se za sve ove algoritme dati i kod u programskim jezicima koji se u umjetnoj inteligenciji najčešće
koriste.
Algoritam 3-1. Pseudokod algoritma pretraživanja u širinu
1. Pohrani početni čvor u niz.
2. DOK niz nije prazan i nije dosegnut cilj:
3. Skupi svu djecu prvog člana niza.
4. Odbaci djecu koja zatvaraju petlju.
5. Provjeri je li dosegnut cilj.
6. Izbriši prvi član niza, a djecu koja su ostala dodaj NA KRAJ NIZA.
7. Ako smo došli do cilja, vrati USPJEH, ako nismo, vrati POGREŠKU.
Kod primjera najkraćeg puta simbolički zapis nekoliko koraka sustavne izgradnje stabla rješenja
problema je:
(S):: Ukloni S i zamijeni ga njegovom djecom SA, SB, SC.
(SA, SB, SC) :: Ukloni SA i zamijeni ga njegovom djecom SAB i SAS. SAS odbaci zato što se radi o petlji
(vratili smo se u S).
(SB, SC, SAB):: Ukloni SB i zamijeni ga njegovom djecom SBA, SBC, SBE, SBS. SBS odbaci zato što se
radi o petlji.
(SC, SAB, SBA, SBC, SBE):: Ukloni SC i zamijeni ga njegovom djecom SCB, SCD, SCS. SCS odbaci
zato što se radi o petlji.
(SAB, SBA, SBC, SBE, SCB, SCD):: Ukloni SAB i zamijeni ga njegovom djecom SABA, SABS, SABC.
SABA i SABS odbaci zato što se radi o petljama.
(SBA, SBC, SBE, SCB, SCD, SABC):: itd.
Na petoj razini jedan od nasljednika čvora SBEF bit će SBEFG. Test koji provjerava samo zadnje
slovo simboličkog zapisa ustanovit će da smo došli do cilja – naselja G, te vratiti informaciju o uspjehu.
Pretraživanje u širinu je:
3 RJEŠAVANJE ZADATAKA METODAMA PRETRAŽIVANJA
58
• potpuno – uvijek pronalazi rješenje za konačni faktor grananja b i to najbolje rješenje –
rješenje do kojeg se dolazi u najmanjem broju koraka (kod zadatka najkraćeg puta simbolički
zapis ima najmanje slova SBEFG)
• ima veliku vremensku i prostornu složenost O(b
m+1
) gdje je b faktor grananja, a m dubina
na kojoj se očekuje najbolje rješenje. Na primjer, za b = 4 i m = 16, uz pretpostavku da nam
je za pohranu svakog stanja potrebno 100 B (Byta), ukupno stablo rješenja trebat će malo
više od 1,7 TB.
3.5.2 Pretraživanje u dubinu
Pretraživanje u dubinu (engl. DFS - Depth First Search)
je drugi temeljni sustavni postupak
slijepog pretraživanja kod kojeg se razvija jedna grana dok god se ili ne dođe do rješenja ili dosegne limit
dubine pretraživanja (d). Slika 3-13 prikazuje nekoliko koraka u formiranju stabla rješenja postupkom
pretraživanja u dubinu za zadatak najkraćeg puta sa slike 3-11.
Slika 3-13. Nekoliko koraka u izgradnji stabla rješenja problema kod pretraživanja u dubinu
Pseudoalgoritam pretraživanja u dubinu prikazuje algoritam 3-2.
3 RJEŠAVANJE ZADATAKA METODAMA PRETRAŽIVANJA
59
Algoritam 3-2. Pseudokod algoritma pretraživanja u dubinu
1. Pohrani početni čvor u niz.
2. DOK niz nije prazan i nije dosegnut cilj:
3. Skupi svu djecu prvog člana niza.
4. Odbaci djecu koja zatvaraju petlju.
5. Provjeri je li dosegnut cilj.
6. Izbriši prvi član niza, a djecu koja su ostala dodaju NA POČETAK NIZA.
7. Ako smo došli do cilja vrati USPJEH, ako nismo vrati POGREŠKU.
Razlika u odnosu na pretraživanje u širinu je samo u tome što se djeca dodaju na početak reda.
Kod primjera najkraćeg puta simbolički zapis nekoliko koraka sustavne izgradnja stabla rješenja
problema je:
(S):: Ukloni S i zamijeni ga njegovom djecom SA, SB, SC.
(SA, SB, SC):: Ukloni SA i zamijeni ga njegovom djecom SAB i SAS. SAS odbaci zato što se radi o petlji
(vratili smo se u S).
(SAB, SB, SC):: Ukloni SAB i zamijeni ga njegovom djecom SABA, SABS, SABC. SABA i SABS odbaci
zato što se radi o petljama.
(SABC, SB, SC):: Ukloni SABC i zamijeni ga njegovom djecom SABCS, SABCB, SABCD. SABCS i
SABCB odbaci zato što se radi o petljama.
(SABCD, SB, SC):: itd.
Postupak pretraživanja u dubinu do prvog rješenja dolazi tek na osmoj razini SABCDEFG.
Postupak je pronašao rješenje, ali nije pronašao najbolje rješenje (s najmanjim brojem koraka), a osim
toga za pretpostaviti je da će njegova prostorna složenost biti puno manja.
Pretraživanje u dubinu:
• rješenje pronalazi samo u konačnim mrežama, i to ne najbolje rješenje, a
• vremenska složenost mu je jednaka kao kod pretraživanja u širinu O(b
m
), ali mu je
zato prostorna složenost manja, u najboljem slučaju jednaka dubini u kojoj se očekuje najbolje
rješenje pomnoženog s faktorom grananja O(b
.
m).
3.5.3 Nedeterminističko slijepo pretraživanje
Nedeterminističko slijepo pretraživanje (engl. Non-deterministic Blind Search)
u svakom
koraku širenja čvora put kojim će se nastaviti odabire slučajnim izborom (npr. bacanjem kocke). U
pseudoalgoritmu postupka razlika je jedino u tome što se djeca dodaju bilo gdje u nizu slučajnim
odabirom:
Algoritam 3-3. Pseudokod algoritma nedeterminističkog slijepog pretraživanja
1. Pohrani početni čvor u niz.
2. DOK niz nije prazan i nije dosegnut cilj:
3. Skupi svu djecu prvog člana niza.
4. Odbaci djecu koja zatvaraju petlju.
5. Provjeri je li dosegnut cilj.
6. Izbriši prvi član reda, a djecu koja su ostala dodaj BILO GDJE U NIZU SLUČAJNIM
ODABIROM.
7. Ako smo došli do cilja, vrati USPJEH, ako nismo, vrati POGREŠKU.
3 RJEŠAVANJE ZADATAKA METODAMA PRETRAŽIVANJA
60
Nasljednici čvora koji se uklanja dodaju se na slučajno odabrano mjesto. Postupak će doći do
rješenja u konačnim mrežama, ako napravimo dovoljan broj pokušaja. Ako imamo sreće, možda će biti i
najbolje rješenje, ali se ništa ne može garantirati, kao niti odrediti vremenska i prostorna složenost. U
najgorem slučaju bit će potrebno izgraditi cijelo stablo rješenja problema pa će i vremenska i prostorna
složenost biti proporcionalna s O(b
d
).
Ovaj je postupak na neki način vezan s poznatim beskonačnim majmunskim teoremom (engl.
Infinity Monkey Theorem)
koji kaže da će majmun slučajno udarajući po tipkama pisaće mašine sigurno
napisati bilo koji zadani tekst (na primjer sva djela Shakespearea) ako ima dovoljno vremena. U pojmu
dovoljno vremena misli se na jako puno vremena. Pogledajmo za primjer koliko bi majmunu trebalo
vremena da napiše riječ „banana”. Pisaća mašina ima 50-ak tipki, slova i interpunkcije, pa bi vjerojatnost
da će majmun slučajnim udaranjem po tipkama napisati riječ „banana” koja predstavlja blok od 6 slova
bila p = (1/50)
6
= 1/15 625 000 000 (pretpostavljamo da je svaki udarac nezavisan događaj). Vjerojatnost
da majmun u bloku od 6 znakova ne napiše riječ „banana” je 1-p = 1 - (1/50)
6
. Pretpostavimo sada da je
majmun napisao n blokova od 6 znakova. Kako je svaki blok nezavisan, vjerojatnost da se nakon n blokova
ne napiše riječ „banana” je P
n
= (1 – (1/50)
6
)
n
. Kako n raste tako ova vjerojatnost pada. Za milijun blokova
je 0,999, a za 10 milijardi 0,53, a ako n teži u beskonačno, vjerojatnost da ne napiše riječ „banana” je 0,
što znači da će majmun sigurno, s vjerojatnošću 100%, nakon beskonačno pokušaja napisati riječ
„banana”.
3.5.4 Pretraživanje ograničeno po dubini
Pretraživanje ograničeno po dubini (engl. DLS – Depth Limited Search)
je pretraživanje u
dubinu kod kojeg je limitirana dubina do koje se pretražuje. Dubina n do koje se ide obično je
pretpostavljena dubina m na kojoj bi se trebalo pronaći najbolje rješenje. Naglasak je na
pretpostavljena. Ako je pretpostavka kriva, rješenje se neće pronaći. Algoritam pretraživanja
ograničenog po dubini prikazuje algoritam 3-4:
Algoritam 3-4. Pseudokod algoritma pretraživanja ograničenog u dubinu
1. Pohrani početni čvor u niz.
2. DOK niz nije prazan i nije dosegnut cilj:
3. Ako je DUBINA PRETRAŽIVANJA MANJA OD n, skupi svu djecu prvog člana niza.
4. Odbaci djecu koja zatvaraju petlju.
5. Provjeri je li dosegnut cilj.
6. Izbriši prvi član reda, a djecu koja su ostala dodaj NA POČETAK NIZA.
7. Ako smo došli do cilja, vrati USPJEH, ako nismo, vrati POGREŠKU.
Pretraživanje ograničeno po dubini je:
• potpuno ako je pretpostavljena dubina n veća ili jednaka dubini m na kojoj se nalazi najbolje
rješenje i tom slučaju pronalazi se i najbolje rješenje (rješenje do kojeg se dolazi u najmanjem
broju koraka), a
• prostorna složenost je O(b
.
n) gdje je n pretpostavljena maksimalna dubina do koje idemo,
dok je vremenska složenost O(b
n
).
3.5.5 Iterativno pretraživanje u dubinu
Iterativno pretraživanje u dubinu (engl. IDS – Iterative Deepening Search) razlikuje se od
DLS-a samo po tome što se odredi početna pretpostavljena dubina n, pa ako se na njoj ne pronađe rješenje,
dubina se poveća za 1 (n = n+1), sve dok se rješenje ne pronađe. Pseudokod algoritma prikazuje algoritam
3-5.
3 RJEŠAVANJE ZADATAKA METODAMA PRETRAŽIVANJA
61
Algoritam 3-5. Pseudokod algoritma iterativnog pretraživanja u dubinu
1. Pohrani početni čvor u niz.
2. DOK niz nije prazan i nije dosegnut cilj:
3. Kreni od početne dubine m.
4. Ako je DUBINA PRETRAŽIVANJA MANJA OD n, skupi svu djecu prvog člana niza.
5. Odbaci djecu koja zatvaraju petlju.
6. Provjeri je li dosegnut cilj.
7. Izbriši prvi član reda, a djecu koja su ostala dodaj NA POČETAK NIZA.
8. Ako smo došli do cilja, vrati USPJEH, ako nismo, POVEĆAJ DUBINU n = n + 1 pa se
vrati na vrati korak 5.
9. Ako je dosegnuta najveća dubina d, a nismo došli do cilja, vrati POGREŠKU.
Iterativno pretraživanje u dubinu je:
• potpuno – uvijek pronalazi rješenje i to najbolje rješenje (rješenje do kojeg se dolazi u
najmanjem broju koraka)
• prostorna složenost je O(b
.
m) gdje je m dubina na kojoj smo pronašli rješenje (ne početna
dubina), dok je vremenska složenost O(b
m
).
Ovo pretraživanje kombinira dobre osobine i pretraživanja u dubinu i pretraživanja u širinu.
Iterativno pretraživanje po dubini sigurno pronalazi najbolje rješenje ako krenemo od početne dubine n
= 1 i onda je postupno podižemo na n = 2, 3, ... sve do m na kojoj se nalazi najbolje rješenje.
3.5.6 Rješavanje problema labirinta slijepim pretraživanjem
Slijepo pretraživanje je posebno značajno kod rješavanja zadataka labirinta, koje u stvarnom
svijetu vodi prema autonomnoj navigaciji vozila u nepoznatom okružju. Zamislimo da uđemo u stvarni
vegetacijski labirint sa slike 3-14 kod kojeg je vegetacija toliko visoka da vidimo samo nebo. Kod odabira
puta jedino što možemo birati jest gdje skrenuti na raskrižju putova.
Slika 3-14. Vegetacijski labirint
28
28
Slika je s https://www.freeimages.com/photo/landscape-labyrinth-1634853 - licenca Public Domain
3 RJEŠAVANJE ZADATAKA METODAMA PRETRAŽIVANJA
62
Pretpostavimo li da je shema labirinta prikazana slikom 3-3, što bi u tom slučaju bilo
pretraživanje u širinu, a što pretraživanje u dubinu?
Pretraživanje u širinu bilo bi na svakom raskrižju krenuti na primjer desnim putom do
sljedećeg raskrižja. Ako nismo došli do izlaza, vraćamo se natrag i biramo drugi put. Primjer širinskog
pretraživanja kod kojeg je otvoreno ukupno 13 grana dok se nije došlo do cilja prikazuje slika 3-15.
Slika 3-15. Širinsko pretraživanje kod rješavanja problema labirinta. U prvom koraku otvore se dva
puta – 1 i 2. Kako izlaz nije pronađen, otvara se drugi korak s tri puta – 3, 4 i 5 itd. Na četvrtoj razini
grane 3 otvorila su se dva puta 12 i 13 od kojih je 13 doveo do izlaza. Širinsko pretraživanje sigurno će
pronaći izlaz iz labirinta, ali ćemo se stvarno našetati (velika prostorna složenost).
Slika 3-16. Dubinsko pretraživanja kod rješavanja problema labirinta. Na svakom je skretanju korišteno
„pravilo desnog skretanja” koje kaže da se na svakom skretanju uvijek skrene desno dok se ne dođe do
kraja. Nakon toga se vraćamo samo za jedan korak i idemo sljedećim putom ponovo koristeći „pravilo
desnog skretanja”. Nakon petog dubinskog koraka došli smo do dviju grana koje ne vode nigdje, pa smo
se morali vratiti na 4. razinu i krenuti drugim mogućim putom koji je doveo do izlaza.
3 RJEŠAVANJE ZADATAKA METODAMA PRETRAŽIVANJA
63
Kod dubinskog pretraživanja prikazanog na slici 3-16 korišteno je „pravilo desnog
skretanja” – na svakom skretanju skrenuti desno, a ako nismo tom granom došli do kraja, vratiti se na
prvo prethodno raskrižje i ponoviti postupak novim putom koji nismo prošli. Nakon petog dubinskog
koraka došli smo do dviju grana koje ne vode nigdje, pa smo se morali vratiti na 4. razinu i krenuti drugim
mogućim putom koji će možda dovesti do izlaza.
3.6 Informirano ili usmjereno pretraživanje
Kod informiranog pretraživanja (engl. Informed Search),
ili kako se ponekad naziva
usmjerenog pretraživanja (engl. Directed Search), osim početnog stanja, dopuštenih akcija prijelaza iz
jednog stanja u drugo, i testa kojim se provjerava jesmo li došli u ciljno stanje, raspolažemo i s određenim
informacijama o prostoru pretraživanja i stanju u kojem se trenutno nalazimo.
Na primjeru najkraćeg puta na Braču kod neinformiranog pretraživanja nismo ništa znali o
udaljenostima između naselja (slika 3-11 i tablica 3-2), dok kod informiranog pretraživanja koristimo i
informacije o udaljenostima između pojedinih naselja (slika 3-8 i tablica 3-1). Ovo su pouzdane ili
determinističke informacije koje prema formalnoj definiciji postupka pretraživanja (3.1) predstavljaju
cijenu prijelaza iz jednog čvora u drugi c(i,j). Udaljenost između Supetra i Nerežišća je sigurno 9 km, pa
kada smo prešli taj put, prešli smo baš 9 km. Osim ovakvih pouzdanih informacija kod informiranog
pretraživanja mogu se koristiti i nepouzdane, heurističke informacije. Iako su nepouzdane, na njima
su se razvili brojni postupci pretraživanja koji su uspješno rješavali i kompleksne probleme. IBM-ov Deep
Blue pobijedio je Garija Kasparova upravo zahvaljujući dobro odabranoj heuristici pomoću koje se
značajno smanjio prostor pretraživanja i ubrzao postupak pronalaženja rješenja.
U nastavku se najprije bavimo usmjerenim pretraživanjem temeljenim na determinističkim
informacijama koje se uobičajeno naziva optimalno pretraživanje, zatim usmjerenim pretraživanjem
temeljenim na heurističkim informacijama koje zovemo heurističko pretraživanje i na kraju
postupcima pretraživanja koji koriste i determinističke i heurističke informacije i koji su, baš zbog toga,
možda i najefikasniji.
3.6.1 Optimalno pretraživanje
Kod optimalnog pretraživanja (engl. Optimal Search) u svakom koraku promatramo koliku
smo do sada „platili cijenu” dolaska do tog čvora i nastavljamo dalje onim putem kod kojeg je dosadašnji
trošak bio najmanji:
f(s) = c, gdje je c cijena do sada prijeđenog puta (3-2)
Prethodnik svih algoritama optimalnog pretraživanja je slavni Dijkstra algoritam. Edsger W.
Dijkstra (1930. – 2002.) uveo ga je 1956. godine s ciljem pronalaska najkraćih puteva između čvorova
otežanih (usmjerenih ili neusmjerenih) grafova. Cilj mu je bio izgraditi:
• potpunu mapu udaljenosti između čvorova grafa, te
• pronaći najkraći put između bilo koja dva čvora.
Razlika između Dijkstra algoritma i algoritama optimalnog pretraživanja je u tome što se kod
optimalnog pretraživanja traži samo najkraći put, a ne potpuna mapa udaljenosti između svih čvorova.
Dijkstra algoritam
Pseudokod Dijkstra algoritma prikazuje algoritam 3-6:
Algoritam 3-6. Pseudokod Dijkstra algoritma
1. Formiraj skup svih čvorova S.
2. Za svaki čvor s iz skupa S postavi inicijalno:
3. cijena(s) = 0 AKO je v početni čvor,
3 RJEŠAVANJE ZADATAKA METODAMA PRETRAŽIVANJA
64
4. cijena(s) = ∞ ZA SVE OSTALE čvorove v
5. DOK skup S nije prazan i nije dosegnut cilj:
6. Izberi najbliže čvorove s početnom čvoru i promijeni njegovu cijenu iz ∞ u c ij e na (s)
= c(s0,s), gdje je c(s0,s) cijena dolaska od početnog čvora s0 do čvora s.
7. Za sve susjedne čvorove v čvorovima s koji još nisu posjećeni promijeni cijenu u
cijena(v) = cijena(s) + c(s,v).
8. AKO je neki od čvorova a već bio posjećen, promijeni mu cijenu ako je nova cijena
MANJA.
9. Ako smo obišli sve čvorove, vrati USPJEH.
Pogledajmo na primjeru Brača. Početna tablica kod koje polazimo iz Supetra (S) izgledala bi:
S A B C D E F G
0
"
"
"
"
"
"
"
U sljedećem koraku gledamo gdje možemo doći iz početnog naselja S (Supetra). To su naselja
Donji Humac (A), Nerežišća (B) i Splitska (C). Nadopunimo tablicu udaljenostima do njih:
S A B C D E F G
0
"
"
"
"
"
"
"
8 9 7
"
"
"
"
U nastavku promatramo možemo li do pojedinih naselja doći i brže preko nekih od naselja kroz
koja smo prošli. Na primjer do B smo došli uz cijenu 9. Ako bismo išli preko A do B, cijena bi bila 8 + 2 =
11 što je veće od 9. Isto tako do B možemo i preko C, ali bi cijena također bila veća (7 + 8 = 15), pa
zadržavamo cijenu do B na 9 koja je najkraća.
Cijela tablica udaljenosti koja daje najkraće udaljenosti od Supetra (S) do svih ostalih naselja je:
S A B C D E F G
0
"
"
"
"
"
"
"
8 9 7
"
"
"
"
29 22
"
"
26
"
42
Najmanja udaljenost do Sumartina (G) je 42 km što smo već i detektirali na Slici 3-10.
Kako se isti ovaj zadatak rješava postupcima optimalnog pretraživanja, ilustrirat ćemo na istom
primjeru s algoritmima:
• pretraživanje jednolikim troškom
• pretraživanje optimalnim jednolikim troškom.
Pretraživanje jednolikim troškom
Pretraživanje jednolikim troškom (engl. UCS – Uniform Cost Search) sastoji se od toga da u
svakom čvoru krećemo onim putem i širimo onaj čvor za koji je dosadašnja akumulirana cijena bila
najmanja. Na primjeru najkraćeg puta na otoku Braču to je ukupan broj prijeđenih kilometara. Slika 3-
17 prikazuje stablo rješavanja problema u ovom slučaju.