Preporučeno, 2019

Izbor Urednika

Razlika između informiranog i neinformiranog pretraživanja

Pretraživanje je proces pronalaženja niza koraka potrebnih za rješavanje bilo kojeg problema. Prethodna razlika između informiranog i neinformiranog pretraživanja je da informirano pretraživanje daje smjernice o tome gdje i kako pronaći rješenje. Nasuprot tome, neinformirana pretraga ne daje dodatne informacije o problemu osim njegove specifikacije.

Međutim, između informiranih i neinformiranih tehnika pretraživanja, informirana pretraga je učinkovitija i isplativija.

Tablica usporedbe

Osnova za usporedbuInformirano pretraživanjeNeinformirano 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
cijenanizakKomparativno visoka
IzvođenjeBrže pronalazi rješenjeBrzina je sporija od informiranog pretraživanja
algoritmi
Pretraživanje po dubini, pretraživanje po širini i prvo pretraživanje najniže cijeneHeuristič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

  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, nema dodatnih informacija o rješenju.
  2. Učinkovitost informiranog pretraživanja bolja je od neinformirane pretrage.
  3. Neinformirana pretraga troši više vremena i troškova jer nema pojma o rješenju u usporedbi s informiranim pretraživanjem.
  4. 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.

Top