Helyi keresési (Local Search) algoritmus C++ nyelven – magyarázat, példa és kód

A Helyi keresési algoritmus egy módszer a legjobb megoldás megtalálására az aktuális állapot közelében. Ezt a technikát gyakran használják közelítő megoldások finomításához az egyes komponensek iteratív módosításával, hogy jobb állapotokat fedezzenek fel.

Hogyan működik

1. Inicializálás: Kezdje egy kezdeti állapottal.
2. Szomszédok létrehozása: Szomszédos állapotok létrehozása az aktuális állapot egy összetevőjének megváltoztatásával.
3. Értékelés: A szomszédos államok minőségének értékelése célfüggvény segítségével.
4. A legjobb állapot kiválasztása: Válassza ki a szomszédos államot a legjobb objektív értékkel.
5. Ismételje meg: Ismételje meg a 2–4. lépéseket, amíg nem talál jobb szomszédos állapotot.

Példa: A Fibonacci funkció optimalizálása

Tekintsük az F(x) = F(x-1) + F(x-2) függvény optimalizálási problémáját, Fibonacci ahol F(0) = 0, F(1) = 1. Meg akarjuk találni az x értékét, amelyre F(x) maximalizált. Használhatjuk a Helyi keresés megközelítést, hogy iteratív módon minden lépéstől távolabbra tekintsünk.

Kódpélda C++ nyelven

#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;  
}  

Ebben a példában a helyi keresés módszerét használjuk a Fibonacci funkció optimalizálására. Megismételjük x különböző értékeit, és Fibonacci minden x-nél kiszámítjuk az értéket. Ha jobb értéket találunk, frissítjük a legjobb értéket és a hozzá tartozó x-et.