Gradientní algoritmus: Porovnání verzí
Smazaný obsah Přidaný obsah
m typo |
rozšíření značka: editace z Vizuálního editoru |
||
Řádek 1:
'''Gradientní algoritmus''' ('''Hill-climbing''', horolezecký algoritmus) je nejjednodušší [[prohledávání stavového prostoru#Informované metody|informovaná metoda prohledávání stavového prostoru]]. Vstupem algoritmu je uzel, ze kterého se má prohledávání zahájit. Nejprve je uzel expandován - jsou vygenerovány jeho sousední uzly a tyto uzly jsou ohodnoceny. Algoritmus vybere z nich nejlépe ohodnocený uzel a ten je nadále expandován. Pokračuje se jako na začátku. Algoritmus tak expanduje uzly se stále vyšším ohodnocením, dokud nenarazí na uzel, po jehož expanzi mají všechny jeho sousední uzly horší ohodnocení. V tu chvíli se algoritmus ukončí s výsledkem posledního expandovaného uzlu. Algoritmus si během svého běhu nepotřebuje udržovat informaci o navštívených uzlech.
Gradientní algoritmy jsou jednoduché a rychlé, ale nemusí nalézt globálním maximum, pokud není prostor možných řešení [[Konvexní funkce|konvexní]]. Při průchodu mohou zůstat v [[lokální extrém|lokálním extrému]], ze kterého se již nedostanou. Gradientní algoritmus je obvykle spouštěn z náhodného místa stavového prostoru. Nevýhoda uvíznutí v lokálním extrému jde částečně omezit opakovaným spouštěním tohoto algoritmu z různých míst stavového prostoru. Při každém spuštění může algoritmus uvíznout v jiném lokálním extrému a pak lze jednoduše vybrat nejvýhodnější z nich. Tímto způsobem se také zvyšuje šance na nalezení globálního maxima.
{{pahýl}}
| |||