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.
3 RJEŠAVANJE ZADATAKA METODAMA PRETRAŽIVANJA
65
Slika 3-17. Rješavanje zadatka najkraćeg puta na pojednostavljenoj mreži s 8 naselja otoka Brača za
pretraživanje jednolikim troškom
Najbliži grad Supetru (S) je Splitska (C) na udaljenosti od 7 km, pa idemo tamo. Nakon Splitske
možemo ići u Pučišća (D) ili u Nerežišće (B) za koje je akumulirana cijena 29, odnosno 15. Kako smo već
otvorili čvor Donji Humac (A) za koji je akumulirana cijena manja i iznosi 8, vraćamo se tamo i gledamo
nasljednike. Samo je jedan nasljednik i to Nerežišće (B) uz akumuliranu cijenu 10. Opet imamo jedan od
početnih čvorova kojem je akumulirana cijena manja i iznosi 9, pa se vraćamo njemu, itd.
Pseudokod algoritma prikazuje algoritam 3-7.
Algoritam 3-7. Pseudokod algoritma pretraživanja jednolikim troškom
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.
3 RJEŠAVANJE ZADATAKA METODAMA PRETRAŽIVANJA
66
6. Izbriši prvi član reda, dodaj djecu te nakon toga POREDAJ NIZ PREMA AKUMULIRANOJ
CIJENI, tako da je na prvom mjestu najmanja akumulirana cijena.
7. Ako smo došli do cilja, vrati USPJEH, ako nismo, vrati POGREŠKU.
Kod simboličkog zapisa postupka rješenja svakom putu dodajemo i njegovu težinu:
(0-S) :: Ukloni S i zamijeni ga njegovom djecom SA, SB, SC, koju treba poredati po akumuliranoj cijeni.
(7-SC, 8-SA, 9-SB):: Ukloni SC i zamijeni ga njegovom djecom SCS i SCB i SCD. SAS odbaci zato što
se radi o petlji. Cijeli red poredaj po akumuliranoj cijeni
(8-SA, 9-SB, 15-SCB, 29-SCD):: Ukloni SA i zamijeni ga njegovom djecom SAB, SAS. SBS odbaci, a red
poredaj po cijeni.
(9-SB, 10-SAB, 15-SCB, 29-SCD):: itd.
Ako je cijena svih putova ista, algoritam se svodi na pretraživanje u širinu. Problem algoritma je
što je dosta vremenski i prostorno zahtjevan, a ponekad nije ni optimalan. Može se dogoditi da je
akumulirana cijena jednog puta do zadnjeg koraka minimalna, a onda se zadnjim korakom povećava i
postaje veća od akumulirane cijene nekog drugog puta. Kao primjer zamislimo da idemo direktno kratkim
putom do podnožja planine, a onda moramo napraviti veliku zaobilaznicu, a da smo od početka išli putom
zaobilaženja planine, možda bismo u početku prelazili više, ali bi u sumi bilo najmanje. Ovaj problem
rješava pretraživanje optimalnim jednolikim troškom.
Pretraživanje optimalnim jednolikim troškom
Pretraživanje optimalnim jednolikim troškom (engl. OUCS – Optimal Uniform Cost Search)
je mala nadogradnja prethodnog postupka, a sastoji se od toga da ne stanemo kada prvi put dođemo do
cilja, već nastavljamo širiti čvorove ako je njihova cijena manja od akumulirane cijene dostignutog cilja.
Nadamo se da bismo širenjem nekog od čvorova koji imaju manju akumuliranu cijenu od one koju smo
sada postigli pronašli put koji će imati akumuliranu cijenu manju od postignute. Ako ima nade,
nastavljamo pretragu.
Pseudokod algoritma možemo ovako napisati:
Algoritam 3-8. Pseudokod algoritma pretraživanja optimalnim jednolikim troškom
1. Pohrani početni čvor u niz.
2. DOK niz nije prazan i nije dosegnut cilj i IMA ČVOROVA ČIJA JE AKUMULIRANA CIJENA
MANJA OD AKUMULIRANE CIJENE POSTIGNUTOG CILJA:
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, dodaj djecu te nakon toga POREDAJ NIZ PREMA AKUMULIRANOJ
CIJENI, tako da je na prvom mjestu najmanja akumulirana cijena.
7. Ako smo došli do cilja, vrati USPJEH, ako nismo, vrati POGREŠKU.
Ovaj algoritam sigurno pronalazi optimalno rješenje kao i pretraživanje u širinu, ali je isto tako
vremenski i prostorno zahtjevan. Ako je C konačna cijena, a
e
prosječna cijena jednog koraka, do cilja
nam treba ukupno (1+C/
e)
koraka pa je prostorna i vremenska složenost O(b
1+C/
e
).
Bi li se metode optimalnog pretraživanja mogle primijeniti kod rješavanja problema labirinta?
Odgovor je potvrdan, s tim da bismo tada trebali zapisivati prijeđeni put (npr. broj koraka) u pojedinoj
grani između dva raskrižja. Na svakom raskrižju birali bismo put kod kojega je prijeđeni broj koraka do
tada manji. Na primjer, za labirint sa slike 3-21 u prvom koraku kraći put dovodi do slijepog kraja (2) pa
idemo putem do (1). Sada nam se nude tri puta (3), (4) i (5). Jednoliki trošak kaže kreni najkraćim od
njih, a to je prema slici 3-21 sigurno put (4), gdje samo u jednom koraku dolazimo do novog raskrižja.
Tako nastavljamo dalje tim putem do (8) zato što je kraći od (9) itd. Sa slike nam je jasno da nam to nije
pravi put, ali nas jednoliki trošak vodi tim dijelom dok ponovo ne dođemo do slijepog kraja, a onda ćemo
3 RJEŠAVANJE ZADATAKA METODAMA PRETRAŽIVANJA
67
se ponovo morati vratiti na prethodno raskrižje na kojem smo krenuli u (4), te sada otići na (5) zato što je
kraće od (3). Ponovo pogrešan put, ali nas jednoliki trošak tako vodi. Na kraju ćemo doći do cilja, ali ćemo
se pošteno našetati i prehodati skoro cijeli labirint.
3.6.2 Heurističko pretraživanje
Kod heurističkog pretraživanja (engl. Heuristic Search) u svakom se koraku koristi pomoćna
veličina kojom nastojimo procijeniti koliko smo daleko uspjeli doći do cilja ili se udaljiti od početka.
Heuristiku smo već spomenuli u Poglavlju 2. Heurističko pretraživanje je postupak kojim se povećava
efikasnost postupka traženja, obično uz žrtvovanje potpunosti.
Uvodi se heuristička evaluacijska funkcija koja svakom stanju s u prostoru rješenja zadatka
pridodaje mjeru, broj koji procjenjuje koliko smo se približili cilju ili koliko smo daleko odmakli od početka:
f(s) = h , gdje je h procjena cijene do cilja ili procjena cijene od početka (3-3)
Naglasak je na procjena, pa h formalno možemo definirati kao preslikavanje sa skupa svih
mogućih rješenja S na skup pozitivnih realnih brojeva:
h : S →
#
+
(3-4)
Heurističke funkcije koje procjenjuju udaljenost do cilja obično su efikasnije pa se i više koriste.
U tom slučaju kada je cilj g dosegnut s = g i h(g) = 0. Heurističku funkciju već smo spomenuli u formalnoj
definiciji postupka pretraživanja opisanog jednadžbom (3-1) i označili s h
0
.
Postoji općenite heuristike koje su primjenjuju kod rješavanje različitih tipova zadataka, ali i
specijalizirane heuristike razvijene za potrebe rješavanja zadataka određene, uske domene. Pogledajmo
neke primjere. Kod zadataka tipa slagalice sa Slike 3-18 heuristička evaluacijska funkcija koja u
trenutnom stanju (na slici lijevo) procjenjuje udaljenost od početka mogla bi biti broj znamenaka dobro
postavljenih na svoje mjesto. U našem slučaju to bi bilo h(s) = 1, s obzirom na to da se samo broj 4 nalazi
na svom mjestu.
Slika 3-18. Trenutno i ciljno stanje kod problema slagalice za koju smo u tekstu opisali različite
heurističke funkcije
Ako kao heurističku funkciju uzmemo broj znamenki koje nisu na svom mjestu, onda na neki
način procjenjujemo koliko smo daleko do cilja kada bi sve znamenke trebale biti na svom mjestu. U
našem primjeru h(s) = 7.
Treća heuristička evaluacijska funkcija koja se i najviše koristi, ne samo u ovom problemu već i
u problemima labirinta, je Manhattan udaljenost. Ona iskazuje koliko je potrebno napraviti pomaka
(horizontalnih i vertikalnih) da bi se sve znamenke dovele na svoje mjesto za slučaj kada bi sve bilo prazno
i ne bi smetale druge znamenke. U našem primjeru 1 treba napraviti 3 pomaka, 2 treba napraviti 4
pomaka, itd. Ukupna Manhattan udaljenost je h(s) = 3 + 4 + 2 + 0 + 2 + 4 + 2 + 4 = 21.
3 RJEŠAVANJE ZADATAKA METODAMA PRETRAŽIVANJA
68
Kod problema labirinta, uz pretpostavku da znamo koordinate cilja (x
2
,y
2
) i znamo da se nalazimo
na koordinati (x
1
,y
1
) Manhattan udaljenost je:
h(s) = | x
1
– x
2
| + | y
1
– y
2
| (3-5)
Osim Manhattan udaljenosti koriste se i Euklidska udaljenost:
$
%
&
'
(
)
%
*
!
+*
"
'
"
,
%
-
!
+-
"
'
"
(3-6)
Chebyshevova udaljenost:
h(s) = max ( | x
1
– x
2
| , | y
1
– y
2
| (3-7)
i Oktilna udaljenost:
h(s) = max ( | x
1
– x
2
| , | y
1
– y
2
| ) + (
.
/+0
)
.
min ( | x
1
– x
2
| , | y
1
– y
2
| ) (3-8)
Manhattanska, Euklidska i Chebishevova udaljenost su specijalni slučajevi općenitije udaljenosti
koja se zove Minkowski udaljenost i koristi kao norma normiranih vektorskih prostora. Minkowski
udaljenost u dvodimenzionalnom prostoru definira se jednadžbom:
$
%
&
'
(
)
%
*
!
+*
"
'
#
,
%
-
!
+-
"
'
#
!
(3-9)
Minkowski udaljenost odgovara Manhattanskoj za p = 1, Euklidskoj za p = 2 i Chebishevovoj za
p = ¥.
Euklidska udaljenost je tipična heuristička funkcija koja se koristi kod različitih problema
pronalaženja puta, a obično se naziva zračna udaljenost od pojedinog čvora do ciljnog čvora. Za primjer
otoka Brača zračne udaljenosti prikazuje tablica 3-3:
Tablica 3-3. Zračne udaljenosti od pojedinih naselja do cilja – Sumartina (G) u km
Supetar (S)
28,30
Donji Humac (A)
25,45
Nerežišća (B)
24,79
Splitska (C)
23,68
Pučišća (D)
12,74
Pražnice (E)
14,80
Gornji Humac (F)
12,46
Ove ćemo podatke koristiti kod ilustracije različitih algoritama heurističkog pretraživanja. Opisat
ćemo metodu uspona na brdo, ograničeno širinsko pretraživanje i najbolje prvo pretraživanje
(pohlepno pretraživanje).
Metoda uspona na brdo
Metoda uspona na brdo (engl. Hill Climbing Method)
ili kako se ponekad zove metoda
poštednog uspona slična je pretraživanju u dubinu, samo što se ide samo onim putem koji ima najmanju
vrijednost heurističke evaluacijske funkcije. Primjenu metode uspona na vrh na primjeru najkraćeg puta
na otoku Braču prikazuje slika 3-19.
3 RJEŠAVANJE ZADATAKA METODAMA PRETRAŽIVANJA
69
Slika 3-19. Rješavanje zadatka najkraćeg puta na Braču metodom uspona na brdo
Lako je uočljivo da je jako brzo došla do cilja, ali rješenje nije optimalno jer do cilja nismo došli
najkraćim putem.
Pseudokod algoritma metode uspona na vrh prikazuje algoritam 3-9:
Algoritam 3-9. Pseudokod algoritma uspona na vrh
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, dodaj djecu na prvo mjesto, ali ih prije toga poredaj po
vrijednosti heurističke funkcije.
7. Ako smo došli do cilja, vrati USPJEH, ako nismo, vrati POGREŠKU.
Algoritam uspona na vrh inspiriran je penjanjem na planinu u magli. Pretpostavimo da ništa ne
vidimo, a želimo se popeti na vrh planine. Ideja je da napravimo korak u svim smjerovima i krenemo
onim putom za koji je uspon najveći. Tako postupimo i u drugom koraku, i u trećem koraku sve dok ne
dođemo do vrha. Jedini problem jest u tome je li to ujedno i najveći vrh? Možda smo došli do nekog
3 RJEŠAVANJE ZADATAKA METODAMA PRETRAŽIVANJA
70
lokalnog vrha, pa koraci u svim smjerovima vode spuštanju, ili smo došli do hrbata, pa se u dva smjera
spuštamo, a u dva ostajemo na istoj visini ili visoravni, što znači da u svim smjerovima više nema
napretka. Rješenje je skok od sedam milja (engl. Seven-league Boots)
prema dječjoj priči po kojoj se
oblačenjem čarobnih čizama može u jednom koraku napraviti sedam milja. Tako i sada, ako smo zapeli
na nekom lokanom vrhu trebamo skočiti na sljedeće brdo nadajući se da je njegov vrh upravo onaj koji
tražimo.
Kako bismo primijenili metodu uspona na brdo kod problema rješavanja labirinta?
Slika 3-20. Drugi korak rješavanja zadatka labirinta metodom uspona na brdo
Kako se radi o heurističkom informiranom pretraživanju, ono što bismo trebali unaprijed znati
jest koordinata izlaza iz labirinta. Trebali bismo znati gdje se izlaz nalazi, ali ne i put do njega. Njega
trebamo tek pronaći. Uz poznavanja koordinate izlaza (x
2
,y
2
) u svakom bi koraku trebao biti poznat i
trenutni položaj (x
1
,y
1
). Put po kojem trebamo nastavili ići određivali bismo na temelju proračuna
vrijednosti heurističke funkcije na kraju svakog puta koji smo otvorili. Uvijek nastavljamo dalje onim
putem koji ima manju vrijednost heurističke funkcije. Na primjer, ako u prvom koraku prikazanom na
slici 3-20 uzmemo Euklidsku udaljenost, onda na drugom križanju krećemo u granu (3) zato što je ona
najbliža izlazu po vrijednosti Euklidske udaljenosti.
Metoda uspona na vrh ne garantira pronalazak najboljeg rješenja, pa se može dalje unaprijediti
ograničenim širinskim pretraživanjem.
Ograničeno širinsko pretraživanje
Ograničeno širinsko!pretraživanje (engl. BS - Beam Search)
se od uspona na brdo razlikuje
jedino u tome što se paralelno spuštamo prema vrijednosti heurističke funkcije po n grana na način da
odabiremo na svakoj razini onih n grana koje imaju najmanju vrijednost heurističke funkcije. Slika 3-21
prikazuje slučaj kada je n = 2. Za razliku od metode uspona na brdo, ograničeno širinsko(pretraživanje je
pronašlo najbolje rješenje.
3 RJEŠAVANJE ZADATAKA METODAMA PRETRAŽIVANJA
71
Slika 3-21. Rješavanje zadatka najkraćeg puta na Braču metodom ograničenog širinskog pretraživanja
Najbolje prvo pretraživanje
Najbolje prvo pretraživanje (engl. BFS – Best First Search), ili kako se češće zove pohlepno
pretraživanje (engl. GS – Greedy Search),
je možda najbolji postupak heurističkog pretraživanja. Slično
je metodi uspona na vrh, samo što u svakom koraku širimo bilo koji od otvorenih čvorova koji imaju
najmanju vrijednost heurističke funkcije. Kod metode uspona na vrh novi se čvorovi najprije poslože po
vrijednosti heurističke funkcije, pa se onda dodaju na početak reda, a kod pohlepnog pretraživanja
najprije se dodaju novi članovi, a onda se posloži cijeli red (slično kao kod pretraživanja jednolikim
troškom, samo što se niz slaže po vrijednostima heurističke funkcije, a ne po vrijednosti do sada
akumulirane cijene).
Pseudokod metode najboljeg prvog pretraživanja prikazuje algoritam 3-8.
Algoritam 3-8. Pseudokod algoritma pretraživanja jednolikim troškom
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, dodaj djecu te nakon toga POREDAJ NIZ PREMA VRIJEDNOSTI
HEURISTIČKE FUNKCIJE h(s), tako da je na prvom mjestu najmanja vrijednost.
7. Ako smo došli do cilja, vrati USPJEH, ako nismo, vrati POGREŠKU.
3 RJEŠAVANJE ZADATAKA METODAMA PRETRAŽIVANJA
72
Vremenska i prostorna složenost pohlepnog pretraživanja ovisi o heurističkoj funkciji, a u
najgorem slučaju je eksponencijalna O(b
d
), gdje je d maksimalna dubina na kojoj se rješenje pronalazi.
I na kraju spomenimo još dva postupka heurističkog pretraživanja koja se često koriste u
problemima dva agenta, prije svega kod igranja igara dva igrača.
Heurističko pretraživanje kod problema dva agenta
Problemi dva agenta su prije svega igre dvaju igrača, na primjer kružić-križić, go, šah, shogi
(japanski šah), bridž, poker i slično, kod kojih dva igrača igraju jedan iza drugoga. Kod razvoja stabla
rješenja zadatka razine naizmjenično pripadaju jednom, pa drugom igraču. Pogledajmo primjer
jednostavne igre križić-kružić. Slika 3-22 prikazuje prva dva poteza u igri kod koje križić igra prvi.
Slika 3-22. Dva koraka igre križić-kružić. Križić počinje prvi i ima zbog simetrije samo tri moguća
poteza, staviti križić u sredinu, centralno uz rub ili u kut. Sljedeća razina pripada kružiću i ovisno o
tome gdje je postavljen križić, drugi igrač ima na raspolaganju dva ili pet mogućih poteza.
Pitanje je kako izabrati sustavnu tehniku pretraživanja koja bi nas dovela do cilja. Ovdje ćemo
ukratko opisati dvije metode koje se često koriste. Jedna je MinMax pretraživanje, a druga Monte
Carlo pretraživanje stabla.
MinMax pretraživanje stabla
MinMax pretraživanje (engl. MM – MinMax Search ili MinMax Search)
je pretraživanje kod
kojega se pri svakom širenju čvora i određivanju koji ćemo potez odigrati odlučujemo za onaj koji će nam
donijeti maksimalni dobitak ili minimalni gubitak. Pretpostavka je da oba igrača igraju optimalno. Igrač
koji nastoji postići maksimalni dobitak naziva se „maximiser”, a onaj koji želi pretrpjeti minimalni
gubitak „minimizer”. Kako se radi o informiranom pretraživanju, svakom stanju (potezu) je potrebno
pridijeliti heurističku evaluacijsku funkciju koja procjenjuje koliko smo se približili cilju. U igri križić-
kružić to može biti:
+10 za tri križića u redu (križić je „maximiser”),
-10 za tri kružića u redu (kružić je „minimiser”),
0 za neriješeni rezultat.
Princip MinMax pretraživanja je „minimizirati ukupni maksimalni gubitak”, što znači u svakom
potezu analizirati sve moguće poteze protivnika dok se ne dođe do kraja u kojem pobjeđuje jedan od igrača
ili je situacija neriješena. Kako nije svejedno u kojem se broju koraka dolazi do kraja, dobro je kao
3 RJEŠAVANJE ZADATAKA METODAMA PRETRAŽIVANJA
73
korekcijski faktor uzeti i broj koraka, na način da broj koraka dolaska do cilja oduzimamo od postignute
vrijednosti evaluacijske funkcije. Pogledajmo primjer sa slike 3-23.
Slika 3-23. Jedno od mogućih stanja u igri križić-kružić i svi mogući ishodi ovisno o potezima igrača kod
MinMax pretraživanja stabla
Na redu je igranje križića i on mora odrediti koji od tri moguća poteza odigrati. Križić simulira
sve moguće ishode kojih ima ukupno 5. U dva pobjeđuje križić (+10), u jednome kružić (-10), a postoje dva
neriješena ishoda (0). Prvi potez vodi pobjedi nakon jednog koraka, pa je heuristička vrijednost za taj
potez 10 – 1 = 9. Drugi potez ima dva ishoda, jedan vodi gubitku pa mu je vrijednost -10, drugi neriješenom
rezultatu 0. Treći potez vodi s jedne strane pobjedi, ali u tri koraka, pa mu je vrijednost heurističke
funkcije 10 – 3 = 7, a s druge strane neriješenom rezultatu 0. Križić je „maksimizer” pa teži maksimalnoj
vrijednosti, te je očito da će odigrati zadnji potez koji ima vrijednost heurističke funkcije 9 (i pobijediti).
Problem MinMax pretraživanja je u tome što se moraju odigrati sve igre do kraja kako bi se
pronašao najbolji potez. To je lako za jednostavne igre, ali za kompleksnije nije, pa se ponekad MinMax
nadopunjuje ograničenjem širenja u dubinu. Promatraju se svi mogući ishodi, ali do neke limitirane
dubine koja se isto tako određuje heuristički. Druga zanimljiva nadogradnja MinMax algoritma je tzv.
alpha–beta obrezivanje (engl. Alpha-Beta Pruning)
kod kojeg se eliminiraju potezi koji su već otkriveni
i daju bolji rezultat.
MinMax algoritam ovisi o heurističkoj funkciji, koju ponekad nije jednostavno odrediti, pa su
istraživači tražili na koje bi načine mogao uklonili taj nedostatak. Jedno od rješenja je postupak nazvan
Monte Carlo pretraživanje stabla.
3 RJEŠAVANJE ZADATAKA METODAMA PRETRAŽIVANJA
74
Monte Carlo pretraživanje stabla
Monte Carlo pretraživanje stabla (engl. MCTS – Monte Carlo Tree Search)
je univerzalni
algoritam određivanja poteza kod igre dvaju igrača, a najviše je uspjeha postigao u kompleksnim igrama
kod kojih se MinMax pretraživanje ne bi moglo primijeniti zato što je potencijalni prostor rješenja zadatka
prevelik. Primjer je igra Go. MinMax pretraživanje je bilo uspješno dok se nije došlo do igara čija je
složenost veća od igre šaha. IBM Deep Blue koji je pobijedio Garija Kasparova temeljio se je na
MinMax algoritmu, ali se kod igre Go taj algoritam nije mogao primijeniti pa je stoga razvijena i
predložena MCTS metoda. Temeljni dio ovog postupka je usmjeravanje na otvaranje čvorova koji najviše
obećavaju, šireći stablo pretraživanja slučajnim uzorkovanjem prostora pretraživanja. Najveći problem
ovakvih kompleksnijih zadataka je kombinacijska eksplozija, eksponencijalno širenje broja mogućih
akcija, a to je posebno prisutno u naglom rastu broja poteza koje dva igrača mogu odigrati kako igra
napreduje.
Ideja Monte Carlo metode temelji se na predviđanju kolika je vjerojatnost da neki potez dovede
do pobjede. Ako bismo je mogli odrediti, sigurno bi bilo vjerojatnije da ćemo u igri i pobijediti. Monte Carlo
pretraživanje stabla sastoji se od 4 koraka: izbor – širenje – simuliranje – ažuriranje (engl. Selection
– Expansion – Simulation – Backpropagation)
vrijednosti pojedinih čvorova stabla s ciljem pronalaska
konačnog rješenja koje ima najveću vjerojatnost pobjede.
Temelj metode je virtualno igranje igre od početka do kraja slučajnim izborom sljedećeg poteza.
Na temelju konačnog rezultata, svakom se čvoru pridodaje vjerojatnost koja ovisi o tome koliko je taj čvor(
pridonio pobjedi. Naglasak je na „slučajnom izboru poteza”, a što se više simulacija napravi, to je i veća
šansa pronalaska dobrog poteza. Pogledajmo primjer. Kod igre križić-kružić pretpostavimo da se
nalazimo u situaciji prikazanoj na slici 3-23. Početni čvor prikazan na vrhu je naš korijenski čvor s0, a
čvorovi sljedećeg reda s01, s02 itd. U ovom ćemo primjeru korigirati težine, pa će pobjeda nositi +1,
gubitak -1, a neriješeno 0. Sljedeći na redu je križić (x). Slučajnim izborom odigramo prvu virtualnu
partiju tako da izaberemo prvi potez i vrlo brzo izgubimo. Kod određivanja vjerojatnosti osim ishoda igre
u proračun uzimamo i broj simulacija koje smo napravili startajući iz tog čvora, pa vrijednost ishoda igre
podijelimo s tim brojem. Na primjer, u našem slučaju krenuli smo prvim putem i to samo jedanput, pa je
N = 1. Na kraju smo izgubili i ostvarili W = -1, pa su težine čvorova u
s0
= -1/1 i u
s01
= -1/1. Sada odigramo
još dva slučajna poteza do kraja (slika 3-24) od kojih jedan daje pobjedu, a jedan neriješeno. Sljedeći je
korak unatrag ažuriranje svih težina čvorova koji su prethodili novim simulacijama. Iz početnog čvora
odigrali smo tri igre, pa je N = 3. Jedanput smo dobili, jedanput izgubili, a jedanput igrali neriješeno, pa
je u
s0
= (-1+1+0)/3 = 0/3, ali on i nije toliko bitan s obzirom na to da mi trebamo odlučiti koji potez izabrati
na sljedećoj razini. Potez s01 je ostao na staroj težini u
s01
= -1/1, a kod poteza s02 odigrali smo dvije igre
(N = 2), jedanput dobili i jedanput igrali neriješeno, pa je u
s02
= (1+0)/2 = 1/2 , što je veće od težine za
s01, pa bismo se, bez daljnjih simulacija, odlučili za s02.
Ovo je jednostavni primjer kod kojeg smo napravili samo tri slučajne simulacije. Naravno, što je
broj simulacija veći, to je i veća šansa da smo napravili dobru odluku. Kod Monte Carlo pretraživanja
svakom simulacijom ažuriraju se sve težine na toj grani. Na primjer, da smo napravili sve moguće
simulacije koje smo napravili kod MinMax pretraživanja za stanje s0 prikazane na slici 3-23, čvorovi
druge razine imali bi težine u
s01
= -1/2, u
s02
= 1/2 i u
s03
= 1/1, pa bismo se kao i kod MinMax metode
odlučili za s03 koji vodi u najbržu pobjedu.
U prethodnom primjeru težinu čvora je određivao samo broj pobjeda (W
i
) i broj simulacija (N
i
)
koje su startale od tog i-tog čvora
1
$
(
%
"
&
"
(3-10)
ali je uobičajeno da se kod Monte Carlo metode težina definira mjerom koja se zove gornja granica
povjerenja (engl. UPC – Upper Confidence Bound):
1
$
(
%
"
&
"
,2
3
'(&
!
&
"
(3-11)
3 RJEŠAVANJE ZADATAKA METODAMA PRETRAŽIVANJA
75
Slika 3-24. Monte Carlo pretraživanje stabla. U prvom smo koraku (a) napravili jednu slučajnu
simulaciju, koja je dala gubitak. Kada napravimo nove simulacije, također slučajnim izborom, trebamo
unatrag ažurirati sve težine čvorova (vidi tekst).
gdje je N
i
ukupan broj simulacija koje prolaze kroz i-ti čvor, N
p
je broj simulacija roditeljskog čvora čvoru
i, a parametar c (koji treba biti veći ili jednak nuli) određuje hoćemo li istraživati čvorove koje smo u
simulacijama mali broj puta posjetili (veliki c) ili suprotno (mali c). Za naš prethodni primjer uz c = 1 i
situaciju sa slike 3-24 pod b) težine čvorova s01 i s02 po ovom proračunu bi bile: u
s01
= -1/1 + (ln 3/1)
1/2
= 0,048 i u
s02
= 1/2 + (ln 3/2)
1/2
= 1,241, a u slučaju da su napravljene sve simulacije sa Slike 3-24: u
s01
=
-1/2 + (ln 5/2)
1/2
= 0,397, u
s02
= 1/2 + (ln 5/2)
1/2
= 1,397 i u
s03
= 1/1 + + (ln 5/1)
1/2
= 2,269.
Kod velikog broja simulacija Monte Carlo pretraživanje stabla konvergira prema MinMax
pretraživanju, ali dosta sporo. Bez obzira na to ovaj postupak vodi prema puno manjem razvijenom
prostoru rješenja zadatka od MinMax metode proširene alpha-beta obrezivanjem. Nadalje, Monte Carlo
ne zahtijeva eksplicitnu heurističku funkciju. Težine se čvorova same računaju tijekom provođenja
simulacija. Monte Carlo metoda je bila zaslužna što je AlphaGo pobijedio korejskog profesionalnog igrača
Go-a Lee Sedola rezultatom 4 : 1, iako se spominje i to da je četvrtu partiju izgubio zbog toga što postoje
pojedinačne grane koje vode do gubitka, a slučajni izbor puteva ih ne može pronaći. Monte Carlo spada u
postupke pojačanog učenja (engl. Reinforcement Learning) koje detaljno obrađujemo u Poglavlju 6.5.1.
3 RJEŠAVANJE ZADATAKA METODAMA PRETRAŽIVANJA
76
3.6.3 Kombinacija optimalnog i heurističkog pretraživanje
I na kraju dolazimo do metoda pretraživanja kod kojih se kombinira optimalno i heurističko
pretraživanje. U svakom pojedinom stanju s iz S kombiniramo do sada ostvarenu cijenu i predviđenu
cijenu do cilja:
f(s) = c + h (3-12)
gdje je c cijena do sada prijeđenog puta, a h procjena cijene do cilja.
Dva se algoritma najčešće koriste: algoritam optimalnog jednolikog troška proširen
estimacijom i algoritam A*.
Pretraživanje optimalnim jednolikim troškom proširenim estimacijom
Pretraživanje optimalnim jednolikim troškom proširenim estimacijom (engl. Estimate –
Extended Optimal Uniform Cost Search)
razlikuje se od pretraživanja optimalnim jednolikim troškom
samo po tome što se u svakom koraku novoformirani red sortira po vrijednosti kombinirane cijene
pojedinog čvora koja uključuje do sada akumuliranu cijenu i estimaciju koliko još imamo do cilja
(algoritam 3-9).
Algoritam 3-9. Pseudokod algoritma pretraživanja optimalnim jednolikim troškom proširenim
estimacijom
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, dodaj djecu te nakon toga POREDAJ NIZ PREMA VRIJEDNOSTI
KUMULATIVNE FUNKCIJE f(s) = c(s) + h(s), tako da je na prvom mjestu najmanja
vrijednost.
7. Ako smo došli do cilja, vrati USPJEH, ako nismo, vrati POGREŠKU.
A* pretraživanje
Algoritam pretraživanja A* (čita se „Ei-Star”) je sigurno najznačajniji algoritam pretraživanja
koji uz svoje različite izvedenice pronalazi primjenu kod brojnih problema koji se rješavaju metodama
pretraživanja. Objavili su ga 1968. godine Peter Hart,!Nils Nilsson!i!Bertram Raphael(sa Stanford
Research Institute kao dio istraživanja vezanog uz jednog od prvih mobilnih robota nazvanog Shakey
prikazanog na Slici 3-25. A* algoritam je osmišljen kako bi se planiralo kretanje robota.
Algoritam je isti kao i pretraživanje optimalnim jednolikim troškom proširenim estimacijom, uz
dodatak da se brišu redundantni putevi i to samo na temelju do sada akumulirane cijene. Pretpostavimo
da se nakon širenja čvora nađemo u istom čvoru u kojem smo već bili na nekoj od prethodnih razina. Ako
je akumulirana cijena tog čvora veća od akumulirane cijene tog istog čvora koji smo već otvorili, zaključak
je da smo došli do istog čvora uz skuplju cijenu i da ga nema smisla dalje otvarati, pa se taj novi čvor
isključuje iz daljnjeg pretraživanja.
Pseudokod algoritma daje algoritam 3-10:
3 RJEŠAVANJE ZADATAKA METODAMA PRETRAŽIVANJA
77
Slika 3-25. Shakey, jedan od prvih mobilnih robota iz 1968. godine zbog kojeg je i osmišljen A*
algoritam
29
Algoritam 3-10. Pseudokod A* algoritma
1. Pohrani početni čvor u niz.
2. DOK niz nije prazan i prvi član niza 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, dodaj djecu te nakon toga POREDAJ NIZ PREMA VRIJEDNOSTI
KUMULATIVNE FUNKCIJE f(s) = c(s) + h(s), tako da je na prvom mjestu najmanja
vrijednost.
7. Ako red sadrži čvor koji smo u prethodnoj liniji uključili, a njegova akumulirana
cijena c(s) je veća od akumulirane cijene ovog novododanog čvora, taj novododani
čvor izbriši.
8. Ako smo došli do cilja, vrati USPJEH, ako nismo, vrati POGREŠKU.
29
Slika s https://commons.wikimedia.org/wiki/File:SRI_Shakey_with_callouts.jpg uz CC BY-SA 3.0 licencu.
3 RJEŠAVANJE ZADATAKA METODAMA PRETRAŽIVANJA
78
U praktičnoj izvedbi kod A* algoritma obično se uvode:
closedSet – skup svih čvorova koji su već istraženi i prošireni, te
openSet – skup čvorova koji su stvoreni, ali još nisu prošireni. Na početku postupka pretraživanja
openSet sadrži samo početni čvor openSet = { s
0
}.
Primjer primjene algoritma A* na traženju najkraćeg puta otoka Brača prikazuje slika 3-25.
Slika 3-25. Rješavanje zadatka najkraćeg puta na Braču metodom A* pretraživanja
Vremenska i prostorna složenost A* pretraživanja ovisi o heurističkoj funkciji, a u najgorem
slučaju je eksponencijalna O(b
d
), gdje je d maksimalna dubina na kojoj se rješenje pronalazi. Problem je
jedino ako rješenje ne postoji jer će ga A* algoritam i dalje stalno tražiti, pa je potrebno ugraditi
vremensko ograničenje nakon kojeg se algoritam zaustavlja.
Varijacije A* pretraživanja
A* algoritam je potaknuo razvoj cijelog niza algoritama koji su uveli određene novosti ili
prilagodili algoritam rješavanju specifičnih problema. Dijelimo ih u nekoliko različitih klasa
30
:
• inkrementalni algoritmi
• algoritmi koji vodu brigu o memoriji
30
https://pdfs.semanticscholar.org/bc00/5547fd17d5e0880fa3d78a3cb6b99f41b719.pdf
3 RJEŠAVANJE ZADATAKA METODAMA PRETRAŽIVANJA
79
• paralelni algoritmi
• algoritmi bilo kojeg vremena (engl. „Anytime” algoritmi) i
• algoritmi realnog vremena (engl. „Real-Time” algoritmi).
Inkrementalni algoritmi pretraživanja
Inkrementalni algoritmi pretraživanja (engl. Incremental Search)
se dinamički mijenjaju i
koriste informacije iz prethodnog pretraživanja za ubrzavanje trenutnog pretraživanja. Posebno su
efikasni u dinamičkim okružjima koja se mijenjaju između dva koraka pretraživanja. Tri su različita
pristupa inkrementalnim algoritmima pretraživanja:
• Algoritmi koji ponovo pokreću A* u stanju kada trenutna pretraga odstupa od prethodne.
Tipičan primjer je FSA* (engl. Fringe Saving A*)
31
iz 2007. godine.
• Algoritmi koji dinamički mijenjaju vrijednost heurističke funkcije h(s) (procjenu
cijene do cilja). Kod A* algoritma vrijednosti heurističke funkcije definiraju se na početku, a
kod ove grupe algoritama mijenjaju se kako bi realnije procijenili udaljenosti do cilja. Primjer
je GAA* (engl. Generalized Adaptive A*)
32
iz 2008. godine.
• Algoritmi koji dinamički mijenjaju cijenu postignutu od početka c(s) iz prethodnog
pretraživanja ili, rečeno na drugačiji način, kod ovih se algoritama transformira stablo
pretraživanja iz prethodnog pretraživanja u sadašnje pretraživanje. Primjeri su LPA*
(Lifelong Planning A*)
33
iz 2004. godine, D*, ponekad nazvan Dinamički A* (Dynamic A*)
34
iz 1995. godine, te D* Light
35
iz 2002. godine. D* algoritam i njegove izvedenice našli su
praktičnu primjenu u brojnim stvarnim problemima kao što su navigacija autonomnih vozila
na nepoznatom terenu, Mars Rover program itd.
Algoritmi koji vode brigu o memoriji
Algoritmi koji vodu brigu o memoriji
(engl. Memory-Concerned Search) posebnu pažnju
usmjeravaju prema količini memorije potrebne za pohranu čvorova u openSet i closedSet listama.
Velika upotreba memorije jedna je od mana A* algoritma, pa se različitim modifikacijama osnovnog
algoritma nastojalo prevladati ovaj problem. I ovdje razlikujemo tri osnovna tipa algoritama:
• Memorijski efektivni algoritmi (engl. Memory-Efficient Search) ne drže u memoriji
skupove openSet i closedSet, već otvaraju isti čvor onoliko puta koliko se pojavi tijekom
pretraživanja. Problem je što dobitak na memoriji plaćaju dužim vremenom izvođenja.
Primjeri su IDA* (Iterative-Deeping A*)
36
iz 1985. godine i RBFS (engl. Linear Space Best-
First Search)
37
iz 1993. godine.
• Memorijski ograničeni algoritmi (engl. Memory-Bounded Search) nastoje razriješiti
problem dugog vremena izvođenja na način da ograničavaju veličinu korištene memorije
kontrolirajući rast openSet skupa. Primjer je SMA* (engl. Simplified Memory-Bounded A*)
38
31
http://idm-lab.org/bib/abstracts/papers/ijcai07b.pdf
32
https://www.cs.nmsu.edu/~wyeoh/docs/publications/aamas08-gaastar.pdf
33
https://www.cs.cmu.edu/~maxim/files/aij04.pdf
34
http://www.frc.ri.cmu.edu/~axs/doc/ijcai95.pdf
35
https://pdfs.semanticscholar.org/9b5d/32d37b9809a295488e49c10919e312b5c357.pdf
36
https://pdfs.semanticscholar.org/7eaf/535ca7f8d1e920e092483d11efb989982f19.pdf
37
https://www.aaai.org/Papers/AAAI/1992/AAAI92-082.pdf
38
https://cse.sc.edu/~mgv/csce580f09/gradPres/Russell_ecai92-sma.pdf
3 RJEŠAVANJE ZADATAKA METODAMA PRETRAŽIVANJA
80
iz 1992. godine. Kod drugog pristupa spremaju se samo čvorovi nužni za traženje optimalnog
rješenja. Primjer je PEA* (engl. Partial Expansion A*)
39
iz 2000. godine.
• Algoritmi s pomoćnom memorijom koriste sekundarnu memoriju za pohranu strukture
algoritma. Sekundarna memorija (vanjski disk) daje puno više memorije za malu cijenu, ali
čestim pisanjem i čitanjem sa sekundarne memorije znatno se usporava algoritam
pretraživanja. Primjer je Frontier A*
40
iz 2004. godine.
Paralelni algoritmi
Paralelni algoritmi (engl. Parallel Search) prilagođeni su paralelnom izvođenju kako bi se
pretraživanje vremenski ubrzalo. Većina ih je projektirana za arhitekture s distribuiranom memorijom
kao na primjer PRA* (engl. Parallel Retracting A*)
41
algoritam iz 1991. godine. Sličan je i PLA* (engl.
Parallel Local A*)
42
algoritam iz 1993. godine. Predloženi su i algoritmi koji koriste zajedničku memoriju.
Algoritmi bilo kojeg vremena
Osnovna značajka algoritama bilo kojeg vremena (engl. „Anytime” Search)
je u tome da daju
rješenje (ne nužno najbolje) u bilo kojem trenutku zaustavljanja algoritma nakon inicijalnog perioda kada
se traži prvo rješenje. Kako vrijeme napreduje, algoritam daje sve bolje i bolje rješenje koje na kraju
konvergira prema optimalnom rješenju. Primjeri su AWA* (Anytime Weighted A*)
43
iz 2007. godine, ARA*
(Anytime Repairing A*)
44
iz 2004. godine i AD* (Anytime Dynamic A*)
45
iz 2005. godine.
Algoritmi realnog vremena
Algoritmi realnog vremena (engl. „Real-Time” Search)
su posljednja grupa modificiranih A*
algoritama kojima je osnovna značajka da mogu provoditi postupak pretraživanja uz prisustvo
vremenskog ograničenja, ali pri tome ne garantiraju da će pronaći optimalno rješenje. Ponekad se ova
skupina algoritama naziva i agentski usmjereno pretraživanje (engl. Agent-Centered Search). Koriste
se u situacijama u kojima je vrijeme pretraživanja važnije od pronalaska najboljeg rješenja. Primjeri su
LRTA* (Learning Real-Time A*)
46
iz 1990. godine i RTAA* (Real-Time Adaptive A*)
47
iz 2006. godine.
Rješavanje zadataka metodama pretraživanja imalo je, ima i imat će značajno mjesto u umjetnoj
inteligenciji. Još uvijek postoje brojni zadaci koji se mogu riješiti jedino metodama pretraživanja, pa je
dobro poznavanje temeljnih postupaka pretraživanja još uvijek vrlo važno kod savladavanja temeljnih
znanja iz područja umjetne inteligencije.
................................................
39
https://www.aaai.org/Papers/AAAI/2000/AAAI00-142.pdf
40
https://www.aaai.org/Papers/AAAI/2004/AAAI04-103.pdf
41
https://pdfs.semanticscholar.org/c412/a6b5c6ad577edd3c94096e99aa7216742ffe.pdf
42
https://pdfs.semanticscholar.org/7e9c/e4feb25250713276eceb85166c10fe3bfb0e.pdf
43
https://www.aaai.org/Papers/JAIR/Vol28/JAIR-2808.pdf
44
https://pdfs.semanticscholar.org/a931/74185b839bcad5e4f02d0ee65a449d1008ac.pdf
45
http://www.cs.cmu.edu/~ggordon/likhachev-etal.anytime-dstar.pdf
46
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.137.1955&rep=rep1&type=pdf
47
http://www.cs.cmu.edu/~./motionplanning/papers/sbp_papers/integrated2/koenig_realtime_adapti
ve_astar_aamas06.pdf
3 RJEŠAVANJE ZADATAKA METODAMA PRETRAŽIVANJA
81
Dodatak: Go je kompleksna, apstraktna, strategijska igra dva igrača koji igraju crnim i bijelim figurama
(žetonima) koji se na japanski zovi idi – kamen (碁石,棋子) na tabli goban
48
(碁盤). Cilj igre je opkoliti
protivničku figuru svojim figurama i na taj je način zarobiti. Igra je izmišljena u Kini prije više od 4000
godina, 2500 godina prije igre šah od koje je puno kompleksnija. Smatra se da igra šah ima 10
120
mogućih
kombinacija figura, a Go 10
174
. Igra je posebno popularna na dalekom istoku. Od 9. – 15. ožujka 2016.g.
u Južnoj Koreji odigrao se meč između svjetskog šampiona Lee Sedola koji je tu titulu ponio 18 puta i
Googlovog programa AlphaGo poznatog i pod nazivom Google DeepMind Challenge Match. Nagrada
je bila 1 milion $, ali budući da je AlphaGo pobijedio s rezultatom 4:1 Google je nagradu donirao
dobrotvornim organizacijama. Na slici ispod je položaj figura 1. partije nakon 99 poteza i za poteze od
100 – 186. AlphaGo se dosta razlikuje od programa koji su do tada korišteni kod igara dva igrača. Kod
slavnog IBMovog(računala Deep Blue koji je u igri šaha 1997.g. pobijedio Gary Kasparova koristilo se
puno heuristike i MaxMin pretraživanje, dok se AlphaGo temeljio na umjetnim neuronskim mrežama i
Monte Carlo pretraživanju stabla. Umjetne neuronske mreže korištene su kod predviđanja vjerojatnosti
pobjede na temelju podataka o brojnim partijama igre Go, uključujući i partije koje je AlphaGo igrao sam
protiv sebe. Postupkom Monte Carlo pretraživanja(stabla računate su vjerojatnosti pobjede ili gubitka
puno poteza u budućnosti. Više detalja o meču Sedola i AlphaGo možete pogledati u nagrađenom
dokumentarnom filmu „AlphaGo”
49
.
48
Slika table je sa stranice https://www.freepik.com
49
https://www.youtube.com/watch?v=WXuK6gekU1Y