Algoritmus představuje nejjednodušší variantu informovaného prohledávání. Nesleduje cenu cesty do daného uzlu, funkce Ohodnocovací funkce se tedy redukuje pouze na odhad vzdálenosti z daného n-tého uzlu do cíle,

Algoritmus preferuje uzly s nejmenší odhadnutou vzdáleností do cíle. Expanduje tedy vždy uzel, který se dle funkce zdá nejbližší k cíli.

Algoritmus si budeme demonstrovat na klasickém příkladu hledání cesty na mapě Rumunských měst.

Obr. 8. Schematická mapa Rumunských měst.

Máme k dispozici mapu měst a silnic, které je propojují, včetně délky těchto silnic.

Dále máme k dispozici tabulku, která udává vzdušnou vzdálenost každého města od Bucharesti. Chceme, aby algoritmus nalezl cestu z Aradu (počáteční stav) do cíle v Bucharesti (cílový stav). Algoritmus se tedy musí rozhodnout, zda se z Aradu vydá do Timisoary, Sibiu, nebo Zerindu.

Uvědomme si, že algoritmus nevidí celou mapu, má k dispozici jen tabulku vzdušných vzdáleností. Algoritmus tedy v následujícím kroku zvolí to město, které je dle vzdušné vzdálenosti (heuristiky) k cíli nejblíže. Zde to tedy bude Sibiu. Dále algoritmus postupuje stejně, tedy ze Sibiu se vydá do Fagarase a z něj už do cíle v Bucharesti. Algoritmus tedy vždy hledá lokální minimum heuristické funkce a doufá, že dorazí do minima globálního.

Obr. 9. Postupné generování cesty – hladový algoritmus

Algoritmus byl tedy úspěšný a pomocí této heuristiky směřoval do cíle efektivněji, než v případě neinformovaného hledání, které by prověřovalo postupně celou mapu jen na základě její topologie.

Nalezená cesta ale není optimální, má délku 450km, zatímco nejkratší cesta pouze 418km. Hladový algoritmus se od optimálního řešení odchýlil ve městě Sibiu, kde zvolil hladově jako další uzel Fagaras místo celkově optimálnější cesty přes Rimnicu Vilcea. Hladové prohledávání se tedy snaží vždy ukousnout co největší kus zbývající cesty, bez ohledu na její celkovou délku. Nicméně tato strategie bývá nejen v případě prohledávání stavového prostoru relativně úspěšnou strategií vedoucí k vítězství.

Vlastnosti algoritmu

Algoritmus není úplný. Není ani optimální. Časová i prostorová složitost odpovídá neinformovanému prohledávání, v pesimistickém případě se heuristika v dané úloze vůbec neuplatní, tedy

(14)

Je třeba si ale uvědomit, že použitá heuristika dokáže reálně dobu prohledávání často významně zredukovat. Redukci času potřebného k nalezení cíle však nelze zaručit.

Výhody a nevýhody

Výhoda algoritmu je vlastně jediná – jde o informovaný algoritmus využívající heuristickou funkci, která dokáže významně redukovat reálnou časovou náročnost nalezení řešení. Nicméně není úplný, ani optimální a je zde nebezpečí uváznutí algoritmu v lokálním minimu. Představme si například úlohu hledání cesty z Neamtu do Fagarase. Metodou hladového prohledávání expandujeme z Neamtu nejprve jediný možný uzel, Lasi. Po vyhodnocení heuristiky pro obě sousední města, tedy Vasluje a Neamtu zjistíme, že vzdušná čára z Neamtu do Fagarase je kratší, než vzdušná vdálenost z Vasluje. Heuristika by algoritmus tedy opět vrátila do uzlu Neamt a tak stále dále. Proto je vhodné zavést například detekci opakovaných stavů a zamezit tak podobnému zacyklení. Tento problém řeší zavedení zmiňovaných množin OPEN a CLOSE, kdy uzly nacházející se v množině CLOSE nejsou již opakovaně procházeny a brání tak zacyklení algoritmu. Algoritmus má také poměrně velkou prostorovou složitost.

vytvořil Institut biostatistiky a analýz Lékařské fakulty Masarykovy univerzity