Metode Pretraživanja Web-a

Posted by on ruj. 2, 2010 in Mreža

Rad pretraživača može se opisat na sljedeći način. Web agent pretražuje bazu podataka, izlistava riječi koje zadovoljavaju upit (ključnu riječ) i zapisuje mjesto gdje ih je našao, indeksira pronađene riječi u indeks prema vlastitom sustavu prosudbe, kodira podatke na sigurno
mjesto i sprema podatke za uporabu[TEŽA2001]. Što se sprema u bazu podataka, ovisi o određenom pretraživaču. Neki indeksiraju svaku riječ iz Web dokumenata, a drugi indeksiraju samo naslov. Kada se provodi pretraživanje preko ključne riječi ili fraze, pretražuje se cijela baza podataka, ali u rezultatu se pokazuju samo Web stranice u kojima je nađena ta ključna riječ ili fraza

Danas je količina dostupnih sadržaja na Webu toliko velika da su pretraživački alati neophodni, ali isto tako neophodno je i njihovo usavršavanje. Trenutno je najveći problem količina dostupnih sadržaja i nemogućnost agenata da uključe sve dostupne sadržaje u bazu. Jedan korak u rješavanju tih problema je upotreba meta-pretraživača, koji koriste baze podataka različitih pretraživača, pa na taj način povećavaju vjerojatnost pronalaženja željenih informacija. Međutim upotreba meta-pretraživača ne rješava ostale probleme. Jedini način za rješavanje svih problema bi bila upotreba umjetne inteligencije. Inteligentni agenti za pretraživanje Web-a (eng. Intelligent Web searching agent) bi pretraživali Web samo u potrazi za korisnikovim upitom.

Razlikujemo dvije osnovne klase algoritama za pretraživanje:
1. SLIJEPO ILI NEINFORMIRANO PRETRAŽIVANJE (eng. blind search or uninformed search)
2. HEURISTIČKO ILI USMJERENO (INFORMIRANO) PRETRAŽIVANJE (eng. heuristic or informed search)

Slijepo pretraživanje je pretraživanje koje nema nikakvih informacija o broju koraka ili
vrijednosti putanje (vrijednost udaljenosti čvora od početnog čvora) od početnog do krajnjeg
stanja, tj. cilja. U ova pretraživanja spadaju:
− pretraživanja po dubini (eng. Depth-first search)
− pretraživanja po širini (eng. Breadth-first search)
− pretraživanja s jednolikom cijenom (eng. Uniform-cost search)
− pretraživanje do određene dubine (eng. Depth-limiting search)
− iterativno pretraživanje po dubini (eng. Iterative deeping search)
− dvosmjerno pretraživanje (eng. Bidirectional search)

Heurističko pretraživanje je pretraživanje koje ima dodatne informacije o cilju, cijenu putanje ili
broj koraka. Te informacije čine ova pretraživanja boljim od slijepih te im omogućuju gotovo
racionalno ponašanje. U ova pretraživanja spadaju:
− pretraživanje najboljim prvim (eng. Best first search)
− pretraživanje penjanjem (eng. Hill-climbing search)
− A* pretraživanje (eng. A* search)
− ograničeno pretraživanje po širini (eng. Beam search)
− IDA* pretraživanje (eng. Iterative deeping A* search)

Metode pretraživanja razmatraju se u okviru ovih kriterija: [ŠULJ2008]
– Potpunost (eng. completeness): da li strategija pretraživanja garantira pronalazak rješenja?
– Vremenska složenost (eng. time complexity): koliko je vremena potrebno za pronalazak
rješenja?
– Složenost prostora (eng. space complexity): koliko je memorije potrebno za izvođenje
pretraživanja?
– Optimalnost (eng. optimality): da li strategija pretraživanja pronalazi visoko kvalitetno
rješenje među više rješenja?

Za razliku od slijepih metoda pretraživanja, usmjerene ili heurističke metode pretraživanja
koriste dodatne informacije o problemu koje mogu bitno ubrzati pronalaženje rješenja, što je više
podataka dostupno metodi pretraživanja to je pretraživanje efikasnije.Usmjerene metode
pretraživanja koriste dodatne informacije kako bi pronašle što kraći put od početnog stanja do
ciljnog stanja. Te dodatne informacije su npr. informacije o naravi stanja, o cijeni prijelaza iz
jednog stanja u drugo, o osobinama cilja, itd. Takve informacije obično se nazivaju heurističke –
temelje se na iskustvenim pravilima i tehnikama prosuđivanja koje mogu pomoći, ali nužno ne
osiguravaju pronalaženje rješenja. Heurističke informacije mogu se oblikovati u heurističku
evaluacijsku funkciju koja zavisi od pojedinog čvora n i od cilja koji se traţi, f(n) = g(n) + h(n).
Dakle, ukupna vrijednost heurističke funkcije f(n) dobiva se zbrajanjem vrijednost h(n) i g(n).
Pri tome je h(n) funkcija procjene udaljenosti čvora n od ciljnog čvora, a g(n) udaljenost čvora n
od početnog čvora[ŠULJ2008].
Vrijednost g(n) se koristi samo u slučaju A* pretraživanja. Ovi algoritmi ne pretražuju čvorove
po redu nego za svaki obiđeni čvor izračunavaju vrijednost heurističke funkcije te se
pretraţivanje usmjerava na čvor sa najmanjom vrijednošću heurističke funkcije. Većina
algoritama za usmjereno pretraživanje namijenjena je za strukture stabla. Jedan od nedostataka
usmjerenih metoda pretraţivanja je izravna ovisnost o odabiru heurističke funkcije. Ukoliko je
ona dobro odabrana, usmjerene metode će neusporedivo brže doći do rješenja nego slijepe
metode. Međutim, pogrešnim odabirom heurističke funkcije pretraţivanje će biti vrlo
neučinkovito.

Nastavak dokumenta nalazi se na linku >www.splithorizont.com/pdf/metode_pretrazivanja_weba.pdf

Leave a Reply

Vaša adresa e-pošte neće biti objavljena. Nužna polja su označena s *