Sadržaj:
Definicija - Što znači penjanje na brdo?
Penjanje na brdo je heuristička metoda matematičke optimizacije koja se koristi za rješavanje računalno zahtjevnih problema koji imaju višestruka rješenja. To je iterativna metoda koja pripada lokalnoj obitelji pretraživanja koja započinje slučajnim rješenjem, a zatim iterativno poboljšava to rješenje jedan po jedan dok ne dođe do manje-više optimiziranog rješenja.
Techopedia objašnjava penjanje na brdo
Penjanje na brdo je tehnika optimizacije koja se koristi za pronalaženje "lokalnog optimalnog" rješenja računskog problema. Započinje s vrlo lošim rješenjem u odnosu na optimalno rješenje, a zatim se iterativno poboljšava. To čini generiranjem "susjedskih" rješenja koja su relativno korak bolja od trenutnog rješenja, odabire najbolje i zatim ponavlja postupak dok ne dođe do najoptimalnijeg rješenja, jer više ne može naći poboljšanja.
varijante:
- Jednostavno - odabran je prvi najbliži čvor ili rješenje koje se pronalazi.
- Najstežiji uspon - razmatraju se sva dostupna nasljednička rješenja i tada se bira najbliže.
- Stohastičko - Susjedsko rješenje odabire se nasumično i tada se odlučuje hoće li se prijeći na to rješenje na temelju količine poboljšanja u trenutnom čvoru.
Penjanje na brdo vrši se iterativno - prolazi čitav postupak i sprema se konačno rješenje. Ako drugačija iteracija nađe bolje konačno rješenje, pohranjuje se spremljeno rješenje ili stanje. To se također naziva penjanje na brdo sačmarica, jer ono jednostavno isprobava različite staze dok ne pogodi najbolju, baš kao i kako je sačmarica neprecizna, ali ipak može pogoditi svoju metu zbog širokog širenja projektila. To djeluje vrlo dobro u mnogim slučajevima, jer ispada da je bolje potrošiti resurse CPU-a istražujući različite staze nego pažljivo optimiziranje od inicijalnog stanja.