Vietinės paieškos (Local Search) algoritmas C++ kalboje – paaiškinimas, pavyzdys ir kodas

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

1. Inicijavimas: pradėkite nuo pradinės būsenos.
2. Generuoti kaimynus: generuokite kaimynines būsenas pakeisdami dabartinės būsenos komponentą.
3. Įvertinimas: Įvertinkite kaimyninių valstybių kokybę naudodami objektyvią funkciją.
4. Pasirinkite geriausią valstiją: pasirinkite kaimyninę valstybę, kurios objektyvi vertė yra geriausia.
5. 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++

#include <iostream>  
  
int fibonacci(int n) {  
    if(n <= 0) return 0;  
    if(n == 1) return 1;  
    return fibonacci(n- 1) + fibonacci(n- 2);  
}  
  
int localSearchFibonacci(int maxIterations) {  
    int bestX = 0;  
    int bestValue = 0;  
  
    for(int x = 0; x < maxIterations; ++x) {  
        int value = fibonacci(x);  
        if(value > bestValue) {  
            bestValue = value;  
            bestX = x;  
        }  
    }  
  
    return bestX;  
}  
  
int main() {  
    int maxIterations = 20;  
    int result = localSearchFibonacci(maxIterations);  
  
    std::cout << "Optimal x for maximum Fibonacci value: " << result << std::endl;  
  
    return 0;  
}  

Š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.