Rozdíl mezi informovaným a neinformovaným vyhledáváním
Obsah
- Srovnávací tabulka
- Definice informovaného vyhledávání
- Heuristické hloubkové první vyhledávání
- Definice neinformovaného vyhledávání
- Hloubka První vyhledávání
- Závěr
Hledání je proces hledání sekvence kroků potřebných k vyřešení jakéhokoli problému. Předchozí rozdíl mezi informovaným a neinformovaným vyhledáváním je 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 a neinformovanými vyhledávacími technikami je však informované vyhledávání efektivnější a nákladově efektivnější.
-
- Srovnávací tabulka
- Definice
- Klíčové rozdíly
- Závěr
Srovnávací tabulka
Základ pro srovnání | Informované vyhledávání | Neinformované vyhledávání |
---|---|---|
Základní | Využívá znalosti k nalezení kroků k řešení. | Žádné využití znalostí |
Účinnost | Vysoce efektivní, protože spotřebovává méně času a nákladů. | Účinnost je prostředník |
Náklady | Nízký | Poměrně vysoká |
Výkon | Najděte řešení rychleji | Rychlost je pomalejší než informované vyhledávání |
Algoritmy | Heuristická hloubka první a šířka-první hledání a A * hledání | Hloubkové první vyhledávání, první šířkové vyhledávání a první levné vyhledávání |
Definice informovaného vyhledávání
Technika informovaného vyhledávání 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 algoritmům, aby narazily na cíl a směr k řešení. Informované vyhledávání může být výhodné z hlediska nákladů, kdy je optimality dosaženo při nižších nákladech na vyhledávání.
Pro vyhledání optimální ceny cesty v grafu implementací informované vyhledávací strategie se do heuristické funkce h (n) vloží nejslibnější uzly n. Poté funkce vrací nezáporné reálné číslo, což je přibližná cena cesty vypočtená z uzlu n do cílového uzlu.
Zde je nejdůležitější součástí informované techniky heuristická funkce, která usnadňuje předávání algoritmu dodatečné 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í šířky, A * vyhledávání atd. Pojďme nyní pochopit heuristické hloubkové vyhledávání.
Heuristické hloubkové první vyhledávání
Podobně jako u metody hloubkového prvního vyhledávání, která je uvedena pod heuristickou hloubkou, první vyhledávání vybere cestu, ale před výběrem jiné cesty projde všechny cesty z vybrané cesty. Zvolí však nejlepší cestu lokálně. V případech, kdy je nejnižší hranicí heuristická hodnota prioritou hranice, je znám jako nejlepší první vyhledávání.
Dalším algoritmem informovaného vyhledávání je vyhledávání typu * *, které slučuje koncept prvního a prvního vyhledávání s nejnižšími náklady. Tato metoda bere v úvahu jak náklady na cestu, tak heuristické informace v procesu hledání a výběru cesty, která má být rozšířena. Odhadovaná celková cena cesty použitá pro každou cestu sídlící 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 nákladů na cestu od počáteční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í způsobem, který 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, ke kterému směřuje v cestě, dokud nezjistí cíl a nenahlásí nástupce. Tato strategie se také nazývá slepé vyhledávání.
V této kategorii jsou různé vyhledávací algoritmy, jako je hloubkové první hledání, jednotné hledání nákladů, první šíře vyhledávání atd. Pojďme nyní porozumět koncepci neinformovaného vyhledávání pomocí hloubkového vyhledávání.
Hloubka První vyhledávání
Při hloubkovém prvním hledání se k přidání a odebrání uzlů používá zásobník Last in first out. Najednou je 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 zásobníku v hranicích vyplynulo, že hledání cest proběhlo do hloubky jako první. Když je prohledávána nejkratší a optimální cesta pomocí hledání hloubkou, je cesta vytvořená sousedními uzly nejprve dokončena, i když to není požadovaná cesta. Poté se alternativní cesta prohledá zpětným sledováním.
Jinými slovy, algoritmus vybere první alternativu v každém uzlu a poté provede zpětnou cestu k jiné alternativě, dokud nepřekročí všechny cesty z prvního výběru. To také vyvolává problém, kdy se vyhledávání může zastavit z důvodu nekonečných smyček (cyklů) přítomných v grafu.
- Bývalá technika informovaného vyhledávání využívá k nalezení řešení znalosti. Na druhou stranu, tato neinformovaná vyhledávací technika nepoužívá znalosti. Zjednodušeně se neuvádějí žá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.
- Algoritmy, které spadají do kategorie neinformovaného vyhledávání, jsou hloubkovým prvním vyhledáváním, prvním šířkovým vyhledáváním a prvním vyhledáváním s nejnižší cenou. Naproti tomu informované vyhledávání zahrnuje algoritmy, jako je heuristická hloubka-první, heuristická šířka-první vyhledávání a A * vyhledávání.
Závěr
Informované vyhledávání poskytuje směr ohledně řešení, zatímco v neinformovaném vyhledávání není uveden žádný návrh řešení. Tím je neinformované vyhledávání zdlouhavější, když je algoritmus implementován.