Neinformirano pretraživanje je klasa algoritama pretraživanja opće namjene koji rade na način grube sile. Neinformirani algoritmi pretraživanja nemaju dodatne informacije o stanju ili prostoru pretraživanja osim o tome kako preći stablo, pa se to naziva i slijepo pretraživanje.
Slijede različite vrste neinformiranih algoritama pretraživanja:
1. Pretraživanje u širinu:
- Pretraživanje u širinu najčešća je strategija pretraživanja za prelaženje stabla ili grafikona. Ovaj algoritam pretražuje uzduž stabla ili grafa, pa se naziva pretraživanje u širinu.
- BFS algoritam započinje pretraživanje od korijenskog čvora stabla i proširuje sve čvorove nasljednike na trenutnoj razini prije prelaska na čvorove sljedeće razine.
- Algoritam pretraživanja u širinu primjer je algoritma pretraživanja općeg grafa.
- Pretraživanje u širinu implementirano korištenjem FIFO strukture podataka čekanja.
Prednosti:
- BFS će pružiti rješenje ako postoji.
- Ako postoji više od jednog rješenja za određeni problem, BFS će pružiti minimalno rješenje koje zahtijeva najmanji broj koraka.
Nedostaci:
- Zahtijeva puno memorije jer se svaka razina stabla mora spremiti u memoriju da bi se proširila sljedeća razina.
- BFS treba puno vremena ako je rješenje daleko od korijenskog čvora.
Primjer:
U donjoj strukturi stabla prikazali smo prelazak stabla pomoću BFS algoritma od korijenskog čvora S do ciljnog čvora K. BFS algoritam pretraživanja prelazi u slojevima, tako da će slijediti putanju prikazanu točkastom strelicom, a prijeđeni put će biti:
S---> A--->B---->C--->D---->G--->H--->E---->F---->I---->K
Vremenska složenost: Vremenska složenost BFS algoritma može se dobiti brojem čvorova prijeđenih u BFS-u do najplićeg čvora. Gdje je d= dubina najplićeg rješenja, a b je čvor u svakom stanju.
T (b) = 1+b2+b3+.......+ bd= O (bd)
Složenost prostora: Prostorna složenost BFS algoritma dana je veličinom memorije granice koja je O(bd).
Potpunost: BFS je dovršen, što znači ako je najplići ciljni čvor na nekoj konačnoj dubini, tada će BFS pronaći rješenje.
Optimalnost: BFS je optimalan ako je trošak puta neopadajuća funkcija dubine čvora.
2. Pretraživanje u dubinu
- Pretraživanje prvo u dubinu je rekurzivni algoritam za prelaženje podatkovne strukture stabla ili grafikona.
- Naziva se pretraživanjem prve dubine jer počinje od korijenskog čvora i prati svaku stazu do njezinog najvećeg dubinskog čvora prije prelaska na sljedeću stazu.
- DFS za svoju implementaciju koristi strukturu podataka stog.
- Proces DFS algoritma sličan je BFS algoritmu.
Napomena: Backtracking je tehnika algoritma za pronalaženje svih mogućih rješenja pomoću rekurzije.
Prednost:
- DFS zahtijeva vrlo manje memorije jer treba samo pohraniti hrpu čvorova na putu od korijenskog čvora do trenutnog čvora.
- Potrebno je manje vremena da se dođe do ciljnog čvora od BFS algoritma (ako ide po pravoj stazi).
Hendikep:
- Postoji mogućnost da se mnoga stanja ponavljaju, a nema jamstva da će se pronaći rješenje.
- DFS algoritam ide za duboko pretraživanje i ponekad može otići do beskonačne petlje.
Primjer:
U donjem stablu pretraživanja prikazali smo tijek pretraživanja najprije u dubinu, a ono će slijediti sljedeći redoslijed:
Korijenski čvor--->Lijevi čvor ----> desni čvor.
Počet će tražiti od korijenskog čvora S, i prijeći A, zatim B, zatim D i E, nakon obilaska E, vratit će stablo jer E nema drugog nasljednika i ciljni čvor još uvijek nije pronađen. Nakon povratnog praćenja prijeći će čvor C, a zatim G, i ovdje će završiti kada je pronašao ciljni čvor.
Potpunost: DFS algoritam pretraživanja dovršen je unutar konačnog prostora stanja jer će proširiti svaki čvor unutar ograničenog stabla pretraživanja.
kako pretvoriti int u string
Vremenska složenost: Vremenska složenost DFS-a bit će ekvivalentna čvoru koji prolazi algoritam. Daje ga:
T(n)= 1+ n2+ n3+.........+ nm=O(nm)
Gdje je m = maksimalna dubina bilo kojeg čvora i to može biti puno veće od d (najmanja dubina rješenja)
Složenost prostora: DFS algoritam treba pohraniti samo jedan put od korijenskog čvora, stoga je prostorna složenost DFS-a ekvivalentna veličini rubnog skupa, što je O(bm) .
Optimalno: DFS algoritam pretraživanja nije optimalan jer može generirati veliki broj koraka ili visoku cijenu za postizanje ciljnog čvora.
3. Algoritam pretraživanja ograničene dubine:
Algoritam pretraživanja ograničenog dubinom sličan je pretrazi prvo dubinom s unaprijed određenim ograničenjem. Pretraživanje ograničene dubine može riješiti nedostatak beskonačne putanje u pretraživanju prvo u dubinu. U ovom algoritmu, čvor na granici dubine tretirat će se kao da dalje nema čvorove nasljednike.
Pretraga ograničena dubinom može se prekinuti uz dva uvjeta neuspjeha:
- Standardna vrijednost greške: označava da problem nema rješenja.
- Granična vrijednost neuspjeha: ne definira rješenje za problem unutar zadane granice dubine.
Prednosti:
Pretraživanje ograničeno dubinom je memorijski učinkovito.
Nedostaci:
- Pretraživanje ograničeno dubinom također ima nedostatak nepotpunosti.
- Možda neće biti optimalno ako problem ima više od jednog rješenja.
Primjer:
Potpunost: DLS algoritam pretraživanja je dovršen ako je rješenje iznad granice dubine.
Vremenska složenost: Vremenska složenost DLS algoritma je O(bℓ) .
Složenost prostora: Prostorna složenost DLS algoritma je O (b�ℓ) .
Optimalno: Pretraživanje ograničeno dubinom može se promatrati kao poseban slučaj DFS-a, a također nije optimalno čak ni ako je ℓ>d.
4. Algoritam pretraživanja s jedinstvenom cijenom:
Pretraživanje s ujednačenom cijenom je algoritam pretraživanja koji se koristi za prelaženje težinskog stabla ili grafa. Ovaj algoritam dolazi u obzir kada je za svaki rub dostupan drugačiji trošak. Primarni cilj pretraživanja s jedinstvenim troškom je pronaći put do ciljnog čvora koji ima najniži kumulativni trošak. Pretraživanje po jedinstvenoj cijeni proširuje čvorove prema njihovim troškovima puta iz korijenskog čvora. Može se koristiti za rješavanje bilo kojeg grafa/stabla gdje je potreban optimalan trošak. Prioritetni red čekanja implementira algoritam pretraživanja s ujednačenom cijenom. Maksimalni prioritet daje najnižem kumulativnom trošku. Pretraživanje jedinstvene cijene ekvivalentno je BFS algoritmu ako je cijena puta svih rubova ista.
Prednosti:
- Jednoobrazno troškovno pretraživanje je optimalno jer se u svakom stanju odabire put s najmanjim troškom.
Nedostaci:
- Nije ga briga za broj koraka koji su uključeni u pretraživanje i brine samo o cijeni puta. Zbog čega ovaj algoritam može zapeti u beskonačnoj petlji.
Primjer:
Potpunost:
Pretraživanje po jedinstvenoj cijeni je dovršeno, na primjer, ako postoji rješenje, UCS će ga pronaći.
Vremenska složenost:
Neka C* je trošak optimalnog rješenja , i e je svaki korak da se približite ciljnom čvoru. Tada je broj koraka = C*/ε+1. Ovdje smo uzeli +1, jer počinjemo od stanja 0 i završavamo do C*/ε.
Stoga je najgora vremenska složenost pretraživanja s jedinstvenom cijenom O(b1 + [C*/e])/ .
Složenost prostora:
Ista je logika za složenost prostora, tako da je najgori slučaj prostorne složenosti pretraživanja s jedinstvenom cijenom O(b1 + [C*/e]) .
Optimalno:
Pretraživanje po jedinstvenoj cijeni uvijek je optimalno jer odabire samo put s najnižom cijenom puta.
5. Iterativno dubinsko dubinsko pretraživanje:
Algoritam iterativnog produbljivanja je kombinacija DFS i BFS algoritama. Ovaj algoritam pretraživanja pronalazi najbolju granicu dubine i to postupnim povećanjem granice dok se ne pronađe cilj.
Ovaj algoritam izvodi prvo dubinsko pretraživanje do određene 'granice dubine' i nastavlja povećavati granicu dubine nakon svake iteracije dok se ne pronađe ciljni čvor.
Ovaj algoritam pretraživanja kombinira prednosti brzog pretraživanja pretraživanja u širinu i memorijske učinkovitosti pretraživanja u dubinu.
Algoritam iterativnog pretraživanja koristan je za neinformirano pretraživanje kada je prostor pretraživanja velik, a dubina ciljnog čvora nepoznata.
Prednosti:
- Kombinira prednosti BFS i DFS algoritma pretraživanja u smislu brzog pretraživanja i učinkovitosti memorije.
Nedostaci:
- Glavni nedostatak IDDFS-a je taj što ponavlja sav rad prethodne faze.
Primjer:
Sljedeća struktura stabla prikazuje iterativno dubinsko pretraživanje prvo u dubinu. IDDFS algoritam izvodi različite iteracije dok ne pronađe ciljni čvor. Iteracija koju izvodi algoritam dana je kao:
1. ponavljanje-----> A
2. ponavljanje----> A, B, C
3. ponavljanje------>A, B, D, E, C, F, G
4. ponavljanje------>A, B, D, H, I, E, C, F, K, G
U četvrtoj iteraciji, algoritam će pronaći ciljni čvor.
Potpunost:
Ovaj algoritam je potpun ako je faktor grananja konačan.
Vremenska složenost:
Pretpostavimo da je b faktor grananja, a dubina d, tada je vremenska složenost u najgorem slučaju O(bd) .
vlc za preuzimanje youtube
Složenost prostora:
Prostorna složenost IDDFS-a bit će O(bd) .
Optimalno:
IDDFS algoritam je optimalan ako je cijena puta neopadajuća funkcija dubine čvora.
6. Algoritam dvosmjernog pretraživanja:
Dvosmjerni algoritam pretraživanja pokreće dva istovremena pretraživanja, jedno iz početnog stanja koje se naziva pretraživanje unaprijed i drugo iz ciljnog čvora koje se naziva pretraživanje unatrag, kako bi se pronašao ciljni čvor. Dvosmjerno pretraživanje zamjenjuje jedan jedini graf pretraživanja s dva mala podgrafa u kojima jedan počinje pretraživanje od početnog vrha, a drugi počinje od ciljnog vrha. Pretraživanje se zaustavlja kada se ta dva grafikona međusobno presijecaju.
Dvosmjerno pretraživanje može koristiti tehnike pretraživanja kao što su BFS, DFS, DLS itd.
Prednosti:
- Dvosmjerno pretraživanje je brzo.
- Dvosmjerno pretraživanje zahtijeva manje memorije
Nedostaci:
- Implementacija dvosmjernog stabla pretraživanja je teška.
Primjer:
U donjem stablu pretraživanja primjenjuje se dvosmjerni algoritam pretraživanja. Ovaj algoritam dijeli jedan graf/stablo na dva pod-grafa. Započinje kretanje od čvora 1 u smjeru prema naprijed i počinje od ciljnog čvora 16 u smjeru unatrag.
Algoritam završava na čvoru 9 gdje se susreću dvije pretrage.
Potpunost: Dvosmjerno pretraživanje je dovršeno ako koristimo BFS u oba pretraživanja.
Vremenska složenost: Vremenska složenost dvosmjernog pretraživanja pomoću BFS-a je O(bd) .
Složenost prostora: Prostorna složenost dvosmjernog pretraživanja je O(bd) .
Optimalno: Dvosmjerno pretraživanje je optimalno.