Přestože neinformované metody prohledávání jsou při hledání cílů úspěšné, pro velké stavové prostory není jejich použití ani v optimalizovaných variantách s ohledem na časovou a prostorovou složitost použitelné. Tyto algoritmy řešícími prohledávání stavového prostoru hrubou silou se tedy snažíme nahradit algoritmy „chytřejšími“. Chceme nalézt metodu, která by využila nějakou další znalost o řešeném problému a na základě ní použila heuristickou metodu, která povede s vysokou nadějí k rychlejšímu nalezení hledané cesty s co nejmenšími prostředky. Metody se snaží tedy postupovat na základě nějaké heuristiky podobně jako lidé, kteří například zabloudí v lese a hledají z něj cestu ven. Mohou postupovat podle různých algoritmů, například vždy směřovat tam, kde jsou stromy nejméně husté, sledovat vodní toky atd. Zdaleka nemohou vědět, že tato cesta vede k cíli či dokonce zda je nejkratší, nicméně s vysokou mírou pravděpodobnosti je vhodná heuristika nakonec dovede k cíli.

V případě informovaného prohledávání tedy opět hledáme cestu ze stavu počátečního do stavů cílových. Ke generování potencionální cesty k cíli však využíváme nějakou další apriorní informaci o řešené úloze. Zavádíme ohodnocení každého n-tého uzlu funkcí

(13)

kde je odhad ceny cesty z n-tého uzlu do cíle a představuje cenu cesty z počátečního stavu do aktuálního n-tého uzlu.

Pořadí prohledávaných uzlů je pak určeno podle hodnoty funkce tak, aby byly nejdříve prověřeny nadějné stavy s nejmenší hodnotou Hodnotu funkce je možné vyjádřit pro aktuální stav přesně, představuje ohodnocení již absolvované cesty. Funkce představuje odhad ceny cesty do cílového stavu. Čím nižší je hodnota tím blíže se daný stav pravděpodobně nachází k cíli. Funkce je tedy jen odhadem, metodu jejího výpočtu určuje člověk na základě svých zkušeností a znalostí řešeného problému. Na kvalitě heuristické funkce pak přímo závisí efektivita nalezení řešení.

Volba optimální heuristické funkce nemusí být triviální. Zpravidla při jejím hledání postupujeme metodou relaxace problému. Relaxace problému představuje mechanismus, jak nalézt přípustnou heuristiku. Za přípustnou (optimistickou) heuristiku považujeme takovou, která nenadhodnocuje cenu cesty k cíli, tedy reálné ohodnocení ceny cesty do cíle bude vždy vyšší, než je výsledek heuristické funkce.

Relaxace problému spočívá v jeho podstatném zjednodušení, tedy vlastně ignorujeme jistá omezení úlohy, která činí problém složitější. Nalezená heuristika ale nemusí být zdaleka optimální a nemusí tedy vést k podstatnému zlepšení vlastností prohledávacího algoritmu. Nalezení dobré heuristické funkce je tedy pro efektivitu řešení velmi podstatné. Ukažme si vše opět na příkladu hlavolamu „Loydova patnáctka“, kdy máme za úkol v matici 4x4 prvky seřadit 15 očíslovaných kamenů pomocí jejich přesunu s využitím jednoho volného pole. Zvažujeme, který kámen přesunout a do kterého následného stavu tedy přejít. Chceme určit heuristiku která bude odhadovat, jak je daný stav vzdálen od cíle. Možností je více - můžeme například pro každý stav vyčíslit počet chybně rozložených kamenů, nebo vyčíslit sumu vzdáleností kamenů od jejich korektních pozic. V následujícím tahu pak můžeme volit takový přesun kamene, který povede do stavu s minimální hodnotou této funkce, jak si ukážeme následně u metody Greedy search.

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