Kazalo:
Opredelitev - Kaj pomeni plezanje po hribu?
Plezanje po hribu je hevristična metoda matematične optimizacije, ki se uporablja za reševanje računalniško zahtevnih problemov, ki imajo več rešitev. Gre za iterativno metodo, ki pripada lokalni iskalni družini, ki se začne z naključno raztopino in nato iterativno izboljša to rešitev po en element, dokler ne pride do bolj ali manj optimizirane rešitve.
Tehopedija razlaga plezanje po hribu
Plezanje po hribu je tehnika optimizacije, ki se uporablja za iskanje "lokalnega optimalnega" rešitve računalniške težave. Začne se z raztopino, ki je v primerjavi z optimalno raztopino zelo slaba, nato pa se od nje iterativno izboljša. To stori tako, da ustvari "sosednje" rešitve, ki so razmeroma korak boljše od trenutne rešitve, izbere najboljše in nato postopek ponavlja, dokler ne pride do najbolj optimalne rešitve, ker ne najde več nobenih izboljšav.
Variante:
- Enostavno - izbere se prvo najbližje vozlišče ali rešitev.
- Najbolj strm vzpon - upoštevajo se vse razpoložljive rešitve naslednika in nato se izbere najbližji.
- Stohastična - sosedova rešitev se izbere naključno in nato se odloči, ali se premaknete na to rešitev na podlagi višine izboljšave v trenutnem vozlišču.
Plezanje po hribu poteka itrativno - poteka skozi celoten postopek in končna rešitev je shranjena. Če drugačna iteracija najde boljšo končno rešitev, se shranjena raztopina ali stanje zamenja. Temu pravimo tudi plezanje po hribu s puško, saj preprosto preizkuša različne poti, dokler ne zadene najboljše, tako kot je puška netočna, vendar lahko še vedno zadene svoj cilj zaradi širokega širjenja izstrelkov. To v mnogih primerih deluje zelo dobro, ker se izkaže, da je bolje porabiti sredstva CPU-ja za raziskovanje različnih poti kot pazljivo optimizacijo iz začetnih pogojev.
