Odporúčaná, 2019

Redakcia Choice

Rozdiel medzi informovaným a neinformovaným vyhľadávaním

Vyhľadávanie je proces vyhľadávania postupnosti krokov potrebných na vyriešenie akéhokoľvek problému. Predchádzajúci rozdiel medzi informovaným a neinformovaným vyhľadávaním spočíva v tom, že informované vyhľadávanie poskytuje informácie o tom, kde a ako nájsť riešenie. Naopak neinformované vyhľadávanie neobsahuje žiadne ďalšie informácie o probléme s výnimkou jeho špecifikácie.

Medzi informovanými a neinformovanými vyhľadávacími technikami je však informované vyhľadávanie efektívnejšie a nákladovo efektívnejšie.

Porovnávacia tabuľka

Základ pre porovnanieInformované vyhľadávanieNeinformované vyhľadávanie
základné
Používa poznatky na nájdenie krokov k riešeniu.Žiadne využitie vedomostí
efektívnosť
Vysoko efektívny, pretože spotrebuje menej času a nákladov.Účinnosť je sprostredkovateľská
nákladynízkyPorovnateľne vysoká
výkonVyhľadáva riešenie rýchlejšieRýchlosť je pomalší ako informované vyhľadávanie
algoritmy
Vyhľadávanie v hĺbke - prvé vyhľadávanie, vyhľadávanie na prvom mieste a najnižšie náklady na prvé vyhľadávanieHeuristická hĺbka prvý a šírka-prvé vyhľadávanie, a A * vyhľadávanie

Definícia informovaného vyhľadávania

Technika informovaného vyhľadávania využíva znalosti špecifické pre daný problém s cieľom poskytnúť kľúč k riešeniu problému. Tento typ stratégie vyhľadávania skutočne zabraňuje tomu, aby sa algoritmy zmietali o cieľ a smer smerom k riešeniu. Informované vyhľadávanie môže byť výhodné z hľadiska nákladov, pri ktorých sa optimalizácia dosiahne pri nižších nákladoch na vyhľadávanie.

Na vyhľadanie optimálnej ceny cesty v grafe implementáciou informovanej stratégie vyhľadávania sa najsľubnejšie uzly n vkladajú do heuristickej funkcie h (n). Potom funkcia vracia negatívne skutočné číslo, čo je približná cena cesty vypočítaná z uzla n do cieľového uzla.

Tu je najdôležitejšou súčasťou informovanej techniky heuristická funkcia, ktorá uľahčuje dodatočné vedomosti o probléme algoritmu. V dôsledku toho pomáha pri hľadaní cesty k cieľu prostredníctvom rôznych susedných uzlov. Existujú rôzne algoritmy založené na informovanom vyhľadávaní, ako je heuristická hĺbková prieskum, heuristická šírka - prvé vyhľadávanie, vyhľadávanie A *, atď. Chápeme teraz heuristické hĺbkové vyhľadávanie.

Heuristická hĺbka prvé vyhľadávanie

Podobne ako v hĺbkovom prvom spôsobe vyhľadávania uvedenom nižšie, heuristické hĺbkové prvé vyhľadávanie si vyberie cestu, ale prejde po všetkých cestách z vybranej cesty pred výberom inej cesty. Vyberá však najlepšiu cestu lokálne. V prípadoch, kde najmenšia heuristická hodnota je prioritou pre hranicu, je známa ako najlepšie prvé vyhľadávanie.

Ďalším informovaným algoritmom vyhľadávania je vyhľadávanie A *, ktoré spája najskôr koncept najnižších cien a najlepšie prvé vyhľadávania. Táto metóda zohľadňuje ako cestu aj heuristické informácie v procese vyhľadávania a výber cesty, ktorá sa má rozšíriť. Odhadované celkové náklady na cestu použité pre každú cestu, ktorá sa nachádza na hranici od začiatku až po cieľový uzol. Preto používa súčasne dve funkcie - cena (p) je cena objavenej cesty a h (p) je odhadovaná hodnota nákladov na cestu z východiskového uzla do cieľového uzla.

Definícia neinformovaného vyhľadávania

Neinformované vyhľadávanie sa odlišuje od informovaného vyhľadávania tak, že poskytuje iba definíciu problému, ale žiadny ďalší krok k nájdeniu riešenia problému. Primárnym cieľom neinformovaného vyhľadávania je rozlišovať medzi cieľovým a necieľovým stavom a úplne ignoruje cieľ, ktorým smeruje smerom k ceste, kým nezískal cieľ a hlási nástupcu. Táto stratégia je tiež známa ako slepé vyhľadávanie.

Existujú rôzne algoritmy vyhľadávania v rámci tejto kategórie, ako je vyhľadávanie v hĺbke, jednotné vyhľadávanie nákladov, vyhľadávanie na šírku, atď. Chápeme teraz koncept neinformovaného vyhľadávania pomocou hĺbkového vyhľadávania.

Hĺbka prvého vyhľadávania

Pri hĺbkovom prvom vyhľadávaní sa na pridávanie a odstraňovanie uzlov používa posledný zásobník s prvým výstupom. Pridáva sa alebo odstráni naraz iba jeden uzol a prvý prvok odstránený z frontu stohu by bol posledným prvkom pridaným do zásobníka. Použitím zásobníka v hraničných výsledkoch pri vyhľadávaní ciest prebiehala hĺbka. Keď sa najskôr hľadá najkratšia a optimálna cesta pomocou hĺbkového vyhľadávania, cesta vytvorená priľahlými uzlami sa skončí ako prvá, aj keď to nie je požadovaná cesta. Potom sa alternatívna cesta hľadá cez spätnú väzbu.

Inými slovami, algoritmus si vyberie prvú alternatívu v každom uzle, potom sa vráti k inej alternatíve, kým neprechádza všetky cesty od prvého výberu. To tiež vyvoláva problém, pri ktorom sa vyhľadávanie môže zastaviť kvôli nekonečným slučkám (cyklov) prítomným v grafe.

Kľúčové rozdiely medzi informovaným a neinformovaným vyhľadávaním

  1. Bývalá informovaná technika vyhľadávania používa vedomosti, aby našla riešenie. Na druhej strane druhá neinformovaná vyhľadávacia technika nepoužíva vedomosti. Zjednodušene povedané, neexistujú žiadne ďalšie informácie o riešení.
  2. Účinnosť informovaného vyhľadávania je lepšia ako neinformované vyhľadávanie.
  3. Neinformované vyhľadávanie spotrebuje viac času a nákladov, pretože nemá žiadne informácie o riešení v porovnaní s informovaným vyhľadávaním.
  4. Hĺbka - prvé vyhľadávanie, hľadanie šírky - prvé vyhľadávanie a najnižšie náklady na prvé vyhľadávanie sú algoritmy spadajúce pod kategóriu neinformovaného vyhľadávania. Naproti tomu informované vyhľadávanie pokrýva algoritmy, ako je napríklad heuristická hĺbka - prvá, heuristická šírka - prvé vyhľadávanie a vyhľadávanie A *.

záver

Informované vyhľadávanie poskytuje smerovanie riešenia, kým v neinformovanom hľadaní nie je uvedený návrh týkajúci sa riešenia. Toto spôsobuje, že neinformované vyhľadávanie je dlhšie, keď je implementovaný algoritmus.

Top