Mezi informovanými i neinformovanými vyhledávacími technikami je však informované vyhledávání efektivnější a hospodárnější.
Srovnávací graf
| Základ pro srovnání | Informované vyhledávání | Neinformované vyhledávání |
|---|---|---|
| Základní | Používá znalosti k nalezení kroků k řešení. | Žádné znalosti |
| Účinnost | Vysoce efektivní, protože spotřebovává méně času a nákladů. | Účinnost je zprostředkovatelem |
| Náklady | Nízký | Poměrně vysoká |
| Výkon | Vyhledává řešení rychleji | Rychlost je pomalejší než informované vyhledávání |
| Algoritmy | Hloubkové vyhledávání, vyhledávání v prvním a nejnižším nákladu | Heuristická hloubka první a šířka-první hledání, a A * hledání |
Definice informovaného vyhledávání
Informovaná vyhledávací technika využívá znalosti specifické pro daný problém, aby poskytla vodítko k řešení problému. Tento typ strategie vyhledávání ve skutečnosti zabraňuje tomu, aby algoritmy narazily na cíl a směr k řešení. Informované vyhledávání může být výhodné z hlediska nákladů, kde je optimality dosaženo při nižších nákladech na vyhledávání.
Pro hledání optimální ceny cesty v grafu implementací informované strategie vyhledávání jsou nejslibnější uzly n vloženy do heuristické funkce h (n). Funkce pak vrací nezáporné reálné číslo, které je přibližnou cenou cesty vypočítanou z uzlu n do cílového uzlu.
Nejdůležitější částí informované techniky je zde heuristická funkce, která algoritmu usnadňuje další znalosti problému. V důsledku toho pomáhá při hledání cesty k cíli prostřednictvím různých sousedních uzlů. Existují různé algoritmy založené na informovaném vyhledávání, jako je heuristické hloubkové vyhledávání, heuristické vyhledávání na prvním místě, vyhledávání A * atd. Pojďme pochopit heuristické hloubkové vyhledávání.
Heuristické hloubkové první vyhledávání
Podobně jako metoda vyhledávání hloubky první uvedená pod heuristickou hloubkou nejprve vybere cestu, ale přejde všechny cesty z vybrané cesty před volbou jiné cesty. Vybere však nejlepší cestu místně. V případech, kdy je nejmenší heuristická hodnota prioritou pro hranici, je znám jako nejlepší první vyhledávání.
Dalším informovaným vyhledávacím algoritmem je vyhledávání A *, které spojuje koncept nejnižších nákladů a nejlepších prvních vyhledávání. Tato metoda zvažuje jak náklady na cestu, tak heuristické informace v procesu vyhledávání a výběru cesty, kterou chcete rozšířit. Odhadované celkové náklady na cestu použité pro každou cestu na hranici od začátku do cílového uzlu. Proto používá současně dvě funkce - cena (p) je cena objevené cesty a h (p) je odhadovaná hodnota ceny cesty od výchozího uzlu k cílovému uzlu.
Definice neinformovaného vyhledávání
Neinformované vyhledávání se liší od informovaného vyhledávání tak, že poskytuje pouze definici problému, ale žádný další krok k nalezení řešení problému. Primárním cílem neinformovaného vyhledávání je rozlišovat mezi cílovým a necílovým stavem a zcela ignoruje cíl, kterým směřuje do cesty, dokud nezjistí nástupce cíle a zprávy. Tato strategie je také známa jako slepé vyhledávání.
V této kategorii existují různé vyhledávací algoritmy, jako je hloubkové vyhledávání, jednotné vyhledávání nákladů, vyhledávání v první šířce a podobně. Pojďme nyní pochopit koncept neinformovaného vyhledávání pomocí hloubkového vyhledávání.
Depth First Search
V prvním hloubkovém vyhledávání se pro přidání a odebrání uzlů použije zásobník Last in first out. Přidán nebo odebrán pouze jeden uzel a první prvek odebraný z hranice zásobníku by byl posledním prvkem přidaným do zásobníku. Využitím svazku v hranicích vede výsledek hledání cest do hloubky. Při hledání nejkratší a optimální cesty pomocí hloubkového vyhledávání je cesta vytvořená sousedními uzly dokončena jako první, i když to není požadovaná cesta. Potom je alternativní cesta vyhledávána zpětným doprovodem.
Jinými slovy, algoritmus vybere první alternativu v každém uzlu a pak se vrátí do jiné alternativy, dokud neprošel všemi cestami od prvního výběru. To také vyvolává problém, kdy hledání může přestat zastavovat kvůli nekonečným smyčkám (cyklům) přítomným v grafu.
Klíčové rozdíly mezi informovaným a neinformovaným vyhledáváním
- Bývalá informovaná vyhledávací technika využívá k nalezení řešení znalosti. Na druhé straně, tato neinformovaná vyhledávací technika nepoužívá znalosti. Zjednodušeně nejsou k dispozici žádné další informace o řešení.
- Účinnost informovaného vyhledávání je lepší než neinformované vyhledávání.
- Neinformované vyhledávání spotřebovává více času a nákladů, protože nemá ponětí o řešení ve srovnání s informovaným vyhledáváním.
- Hloubka-první vyhledávání, šířka-první vyhledávání a nejnižší náklady první vyhledávání jsou algoritmy spadají do kategorie neinformované vyhledávání. Na rozdíl od toho, informované vyhledávání pokrývá algoritmy, jako je heuristická hloubka-první, heuristická šířka-první vyhledávání a A * hledání.
Závěr
Informované vyhledávání poskytuje směr týkající se řešení, zatímco v neinformovaném vyhledávání není uveden žádný návrh týkající se řešení. Díky tomu je neinformované vyhledávání zdlouhavější při implementaci algoritmu.
