Sadržaj

• Usporedni grafikon
• Definicija informiranog pretraživanja
• Prva heuristička dubina
• Definicija neinformiranog pretraživanja
• Dubina prva pretraga
• Zaključak

Pretraživanje je postupak pronalaska niza koraka potrebnih za rješavanje bilo kojeg problema. Prethodna razlika između informirane i neinformirane pretraživanja je da informirana pretraga pruža smjernice o tome gdje i kako pronaći rješenje. Suprotno tome, neinformirana pretraga ne daje nikakve dodatne informacije o problemu osim njegove specifikacije.

Međutim, između informirane i neinformirane tehnike pretraživanja, informirana pretraga je učinkovitija i isplativija.

1. 1. Usporedni grafikon
   2. definicija
   3. Ključne razlike
   4. Zaključak

Usporedni grafikon

Osnove za usporedbu	Informisana pretraga	Neinformirana pretraga
Osnovni, temeljni	Koristi znanje za pronalaženje koraka do rješenja.	Nema koristi od znanja
efikasnost	Vrlo učinkovit, jer troši manje vremena i troškova.	Učinkovitost je posrednička
cijena	nizak	Relativno visok
Izvođenje	Brže pronalazi rješenje	Brzina je sporija od pretraživane informiranosti
algoritmi	Prvo heuristička dubina i prvo pretraživanje širine i A * pretraživanje	Dubinska pretraga, prvo pretraživanje širine i najniža cijena najpre pretraživanja

Definicija informiranog pretraživanja

Informirana tehnika pretraživanja koristi specifična znanja o problemu kako bi dala naznaku za rješenje problema. Ova vrsta strategije pretraživanja zapravo sprečava algoritme da se spotaknu o cilju i smjeru rješenja. Informirano pretraživanje može biti korisno u pogledu troškova kada se optimalnost postiže uz niže troškove pretraživanja.

Za pretraživanje optimalnog troška puta u grafikonu primjenom informirane strategije pretraživanja najperspektivniji čvorovi n ubačeni su u heurističku funkciju h (n). Tada funkcija vraća negativni realni broj koji je približan trošak puta izračunato od čvora n do ciljanog čvora.

Ovdje je najvažniji dio informirane tehnike heuristička funkcija koja olakšava prijenos dodatnih znanja o algoritmu. Kao rezultat, pomaže u pronalaženju puta do cilja kroz različite susjedne čvorove. Postoje razni algoritmi koji se temelje na informiranoj potrazi poput heurističke dubinske prve pretrage, heurističke širine prve pretrage, A * pretrage i slično. Hajde da sada razumemo heurističko prvo dubinsko pretraživanje.

Prva heuristička dubina

Slično kao i prva metoda dubine pretraživanja dana ispod heurističke dubine, prvo pretraživanje odabire put, ali prelazi sve putove odabranog puta prije odabira drugog puta. Međutim, lokalno bira najbolji put. U slučajevima kada je najmanja heuristička vrijednost prioritet za granicu, tada je ona poznata kao najbolje prvo pretraživanje.

Drugi algoritam informiranog pretraživanja je A * pretraživanje koje spaja koncept najnižih troškova prve i najbolje prve pretrage. Ova metoda uzima u obzir i troškove puta i heurističke informacije u procesu pretraživanja i odabira putanje koju treba proširiti. Procijenjeni ukupni trošak puta koji se koristi za svaku stazu koja se nalazi na granici od početka do ciljanog čvora. Stoga istovremeno koristi dvije funkcije - trošak (p) je trošak otkrivene putanje i h (p) je procijenjena vrijednost troška putanje od početnog čvora do ciljanog čvora.

Definicija neinformiranog pretraživanja

Neinformirana pretraga razlikuje se od informiranog pretraživanja na način što samo daje definiciju problema, ali ne i daljnji korak ka pronalaženju rješenja problema. Osnovni cilj neinformirane potrage je razlikovati ciljno i neciljno stanje, a on potpuno zanemaruje odredište na koje se upućuje na putu dok ne otkrije cilj i ne izvjesti nasljednika. Ova je strategija poznata i kao slijepa potraga.

U ovoj kategoriji postoje razni algoritmi pretraživanja, kao što su prvo pretraživanje dubine, jednoobrazno pretraživanje troškova, prvo pretraživanje širine i tako dalje. Razjasnimo sada pojam koji stoji iza neinformiranog pretraživanja uz pomoć dubinskog pretraživanja.

Dubina prva pretraga

Pri prvom pretraživanju, snop Last in first out koristi se za dodavanje i uklanjanje čvorova. Samo se jedan čvor doda ili ukloni odjednom, a prvi element uklonjen s granice stola bi bio posljednji element koji je dodan u niz. Upotrebom snopa na granici, prvo se traži dubina pretraživanja staza. Kada se pretražuje najkraći i optimalni put pomoću prvog pretraživanja dubine, put koji kreiraju susjedni čvorovi prvo se dovršava, čak i ako nije željeni. Zatim se traži alternativni put povratnim trakom.

Drugim riječima, algoritam bira prvu alternativu na svakom čvoru, a zatim vraća drugu alternativu sve dok nije prešao sve staze iz prvog odabira. To također stvara problem kada pretraga može prestati prestati zbog beskonačnih petlji (ciklusa) prisutnih na grafikonu.

1. 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, ne postoje dodatne informacije o rješenju.
2. Učinkovitost informirane pretrage bolja je od neinformirane pretraživanja.
3. Neinformirana pretraga troši više vremena i troškova jer nema pojma o rješenju u odnosu na informirano pretraživanje.
4. Pretraživanje dubinom, prvo pretraživanje širine i prvo pretraživanje s najnižim cijenama algoritmi su pod kategoriju neinformiranog pretraživanja. Nasuprot tome, informirana pretraga obuhvaća algoritme kao što su heuristička dubina prvo, heuristička širina prvo pretraživanje i A * pretraga.

Zaključak

Informirana pretraga daje smjernice u vezi s rješenjem, dok u neinformiranom pretraživanju ne daju se prijedlozi rješenja. To čini neinformirano pretraživanje duljim kada se algoritam provodi.