Obsah:
Definícia - Čo znamená Hill Climbing?
Horolezectvo je matematická optimalizačná heuristická metóda používaná na riešenie výpočtovo náročných problémov, ktoré majú viacero riešení. Ide o iteratívnu metódu patriacu do rodiny miestnych vyhľadávaní, ktorá začína náhodným riešením a potom iteratívne vylepšuje toto riešenie po jednom prvku, kým nedôjde k viac alebo menej optimalizovanému riešeniu.
Techopedia vysvetľuje Hill Climbing
Horolezectvo je optimalizačná technika, ktorá sa používa na nájdenie „lokálneho optimálneho“ riešenia počítačového problému. Začína sa riešením, ktoré je v porovnaní s optimálnym riešením veľmi zlé a potom sa z neho iteratívne zlepšuje. Robí to tak, že vytvára „susedné“ riešenia, ktoré sú relatívne o krok lepšie ako súčasné riešenie, vyberie najlepšie a potom opakuje proces, kým nedôjde k najoptimálnejšiemu riešeniu, pretože už nemôže nájsť žiadne zlepšenia.
varianty:
- Jednoduché - Vyberie sa prvý najbližší uzol alebo riešenie.
- Najstrmší výstup - Zvážia sa všetky dostupné nástupnícke riešenia a vyberie sa najbližšie.
- Stochastic - susedné riešenie sa vyberá náhodne a potom sa rozhodne, či sa k tomuto riešeniu má pristúpiť na základe množstva vylepšení v súčasnom uzle.
Horolezectvo sa uskutočňuje iteratívne - prechádza celým postupom a konečné riešenie sa uloží. Ak iná iterácia nájde lepšie konečné riešenie, uložené riešenie alebo stav sa nahradí. Toto sa tiež nazýva lezenie na brokovnicu, pretože sa jednoducho snažia vyskúšať rôzne cesty, až kým nenarazí na najlepšiu, rovnako ako brokovnica je nepresná, ale stále môže zasiahnuť svoj cieľ kvôli širokému šíreniu projektilov. Funguje to veľmi dobre v mnohých prípadoch, pretože sa ukáže, že je lepšie minúť prostriedky CPU na skúmanie rôznych ciest než starostlivo optimalizovať z počiatočných podmienok.
