Međutim, između informiranih i neinformiranih tehnika pretraživanja, informirana pretraga je učinkovitija i isplativija.
Tablica usporedbe
| Osnova za usporedbu | Informirano pretraživanje | Neinformirano pretraživanje |
|---|---|---|
| Osnovni, temeljni | Koristi znanje za pronalaženje koraka do rješenja. | Nema znanja |
| efikasnost | Visoko učinkovit jer troši manje vremena i troškova. | Učinkovitost je posrednička |
| cijena | nizak | Komparativno visoka |
| Izvođenje | Brže pronalazi rješenje | Brzina je sporija od informiranog pretraživanja |
| algoritmi | Pretraživanje po dubini, pretraživanje po širini i prvo pretraživanje najniže cijene | Heuristička dubina prvog i širokog pretraživanja i A * pretraživanja |
Definicija informiranog pretraživanja
Tehnika informiranog pretraživanja koristi specifično znanje problema kako bi dala trag rješavanju problema. Ova vrsta strategije pretraživanja zapravo sprječava algoritme da se spotaknu o cilj i smjer u rješenje. Informirana pretraga može biti povoljna u smislu troškova gdje se optimalnost postiže pri nižim troškovima pretraživanja.
Za traženje optimalnog troška puta u grafu primjenom informirane strategije pretraživanja najperspektivniji čvorovi n umetnuti su u heurističku funkciju h (n). Tada funkcija vraća ne-negativni stvarni broj koji je približan trošak puta izračunat od čvora n do ciljnog čvora.
Ovdje je najvažniji dio informirane tehnike heuristička funkcija koja olakšava prenošenje dodatnog znanja o problemu algoritmu. Kao rezultat, pomaže u pronalaženju puta do cilja kroz različite susjedne čvorove. Postoje različiti algoritmi koji se temelje na informiranom pretraživanju, kao što su heurističko traženje dubine, heurističko traženje po širini, pretraživanje A * i slično. Razumimo heurističku pretragu dubine.
Heuristička dubina prve pretrage
Slično metodi traženja dubine koja se daje ispod heurističke dubine, prvo pretraživanje odabire putanju, ali prijeđe sve staze od odabrane staze prije odabira druge staze. Međutim, on bira najbolji put na lokalnoj razini. U slučajevima gdje je najmanja heuristička vrijednost prioritet za granicu, tada je poznata kao najbolja prva pretraga.
Još jedan traženi algoritam pretraživanja je A * pretraživanje koje spaja koncept najniže cijene prvi i najbolji prvi pretraživanja. Ova metoda uzima u obzir i trošak puta i heurističku informaciju u procesu pretraživanja i odabira putanje za proširenje. Procijenjeni ukupni trošak puta koji se koristi za svaku stazu koja se nalazi na granici od početka do ciljnog čvora. Stoga istovremeno koristi dvije funkcije - trošak (p) je trošak otkrivene staze, a h (p) je procijenjena vrijednost cijene staze od početnog čvora do ciljnog čvora.
Definicija neinformiranog pretraživanja
Neinformirano pretraživanje razlikuje se od informiranog pretraživanja na način da samo daje definiciju problema, ali ne i daljnji korak u pronalaženju rješenja problema. Primarni cilj neinformiranog pretraživanja je razlikovanje između ciljnog i neciljnog stanja, i potpuno zanemaruje odredište na koje se kreće na putu dok ne otkrije nasljednika cilja i izvješća. Ova strategija je također poznata kao slijepa pretraga.
U ovoj kategoriji postoje različiti algoritmi pretraživanja, kao što su pretraživanje dubine, jedinstveno pretraživanje troškova, pretraživanje po širini i tako dalje. Razumimo sada koncept neinformirane potrage uz pomoć dubokog pretraživanja.
Prvo pretraživanje dubine
U potrazi za dubinom, stog Last in first out se koristi za dodavanje i uklanjanje čvorova. Istodobno se dodaje ili uklanja samo jedan čvor, a prvi element uklonjen s granice snopa bio bi posljednji element dodan u stog. Upotrebom stog u graničnim rezultatima u traganju za stazama prvi se put odvija dubina. Kada se traži najkraća i optimalna putanja pomoću traženja dubine, put stvoren od susjednih čvorova završava se prvo, čak i ako nije željeni. Zatim se pretražuje alternativni put kroz povratno praćenje.
Drugim riječima, algoritam odabire prvu alternativu na svakom čvoru, a zatim se vraća na drugu alternativu dok ne prijeđe sve staze od prvog odabira. To također dovodi do problema gdje pretraživanje može prestati zbog beskonačnih petlji (ciklusa) prisutnih u grafikonu.
Ključne razlike između informiranog i neinformiranog pretraživanja
- Bivša tehnika informiranog pretraživanja koristi znanje kako bi pronašla rješenje. S druge strane, potonja neinformirana tehnika pretraživanja ne koristi znanje. Jednostavnije rečeno, nema dodatnih informacija o rješenju.
- Učinkovitost informiranog pretraživanja bolja je od neinformirane pretrage.
- Neinformirana pretraga troši više vremena i troškova jer nema pojma o rješenju u usporedbi s informiranim pretraživanjem.
- Pretraživanje po dubini, prvo pretraživanje po opsegu i prvo pretraživanje najniže cijene su algoritmi koji spadaju u kategoriju neinformiranog pretraživanja. Nasuprot tome, informirano pretraživanje obuhvaća algoritme kao što su heurističko traženje dubine, heurističko pretraživanje i A * pretraživanje.
Zaključak
Informirana pretraga daje smjer u odnosu na rješenje, dok se u neinformiranom pretraživanju ne daje prijedlog za rješenje. To čini neinformirano pretraživanje duže kada se algoritam implementira.
