Vietinės paieškos algoritmas yra būdas rasti geriausią sprendimą šalia esamos būsenos. Šis metodas dažnai naudojamas apytiksliems sprendimams patikslinti, pakartotinai modifikuojant atskirus komponentus, siekiant atrasti geresnes būsenas.
Kaip tai veikia
- Inicijavimas: pradėkite nuo pradinės būsenos.
- Generuoti kaimynus: generuokite kaimynines būsenas pakeisdami dabartinės būsenos komponentą.
- Įvertinimas: Įvertinkite kaimyninių valstybių kokybę naudodami objektyvią funkciją.
- Pasirinkite geriausią valstiją: pasirinkite kaimyninę valstybę, kurios objektyvi vertė yra geriausia.
- Pakartokite: kartokite 2–4 veiksmus, kol nerasite geresnės kaimyninės būsenos.
Pavyzdys: Fibonacci funkcijos optimizavimas
Apsvarstykite funkcijos F(x) = F(x-1) + F(x-2) optimizavimo uždavinį Fibonacci, kai F(0) = 0, F(1) = 1. Norime rasti x reikšmę, kuriai F(x) yra maksimalus. Galime naudoti vietinės paieškos metodą, norėdami pakartotinai tyrinėti toliau nuo kiekvieno veiksmo.
Kodo pavyzdys C++
Šiame pavyzdyje funkcijai optimizuoti naudojame vietinės paieškos metodą Fibonacci. Pakartojame skirtingas x reikšmes ir apskaičiuojame Fibonacci kiekvieno x reikšmę. Kai randama geresnė reikšmė, atnaujiname geriausią vertę ir ją atitinkančią x.