Doporučená, 2024

Redakce Choice

Rozdíl mezi informovaným a neinformovaným vyhledáváním

Vyhledávání je proces hledání kroků potřebných k vyřešení jakéhokoliv problému. Předcházející rozdíl mezi informovaným a neinformovaným hledáním spočívá v tom, že informované vyhledávání poskytuje návod, kde a jak najít řešení. Naopak neinformované vyhledávání neposkytuje žádné další informace o problému kromě jeho specifikace.

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ákladyNízkýPoměrně vysoká
VýkonVyhledává řešení rychlejiRychlost je pomalejší než informované vyhledávání
Algoritmy
Hloubkové vyhledávání, vyhledávání v prvním a nejnižším nákladuHeuristická 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

  1. 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í.
  2. Účinnost informovaného vyhledávání je lepší než neinformované vyhledávání.
  3. 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.
  4. 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.

Top