Lokální metody prohledávání

Samostatnou oblast metod pro prohledávání stavového prostoru jsou takzvané lokální metody prohledávání. Zmiňme si stručně alespoň dvě z nich a to horolezecké prohledávání (Hill climbing, slézání kopce, gradientní metoda prohledávání) a Simulated annealing (simulované žíhání). Společným znakem je, že tyto metody vyhodnocují jen své nejbližší okolí a vydají se při prohledávání zkrátka některým směrem, který se v tu chvíli zdá metodě lokálně optimální na základě vyhodnocení funkce Chovají se tedy podobně jako GS. Lokální metody ale zcela zapomínají předcházející uzly a postrádají tak možnost návratu.

Algoritmus simulovaného žíhání se oproti jednoduchému gradientnímu prohledávání liší v tom, že zavádí pojem teploty T. Tato teplota je na počátku prohledávání vysoká (umožňuje širší prohledání stavového prostoru v počátku běhu algoritmu) a v jeho průběhu postupně klesá až k nule (algoritmus konverguje k řešení). Při výběru následníka není v každém uzlu vždy zvolen jen následník nejvýhodnější, jako v případě gradientního prohledávání, ale s jistou pravděpodobností, která závisí na teplotě T, je zvolen přechod do uzlu jiného. S klesající teplotou pravděpodobnost volby neoptimálního následníka klesá, algoritmus postupně konverguje do ustáleného stavu. Algoritmus s větší pravděpodobností dosáhne globálního minima (cíle). Zavedením teploty je omezena možnost uváznutí algoritmu v lokálním minimu, protože s jistou pravděpodobností se z něj dokáže algoritmus vymanit a prohledat tak i ty části stavového prostoru, kam by prostá gradientní metoda nevstoupila. Často je tento algoritmus při neúspěchu startován opakovaně z rozdílných počátečních míst stavového prostoru.

Výhodami lokálních algoritmů je zejména jejich snadná implementace a minimální paměťové nároky. Nevýhodou je především jejich suboptimálnost a neúplnost, mohou snadno uváznout v lokálním minimu. Přesto jsou pro řadu problémů úspěšně využívány.