Lokal sökalgoritm (Local Search) i C++- Förklaring, exempel och kod

Den lokala sökalgoritmen är en metod för att hitta den bästa lösningen i närheten av det aktuella tillståndet. Denna teknik används ofta för att förfina ungefärliga lösningar genom att iterativt modifiera enskilda komponenter för att upptäcka bättre tillstånd.

Hur det fungerar

1. Initialisering: Börja med ett initialt tillstånd.
2. Generera grannar: Generera angränsande tillstånd genom att ändra en komponent i det aktuella tillståndet.
3. Utvärdering: Utvärdera kvaliteten på grannstater med hjälp av en objektiv funktion.
4. Välj bästa tillstånd: Välj den angränsande staten med det bästa objektiva värdet.
5. Upprepa: Iterera genom steg 2 till 4 tills du inte kan hitta någon bättre grannstat.

Exempel: Optimera Fibonacci funktionen

Betrakta optimeringsproblemet för Fibonacci funktionen F(x) = F(x-1) + F(x-2) med F(0) = 0, F(1) = 1. Vi vill hitta värdet på x för vilket F(x) är maximerad. Vi kan använda metoden för lokal sökning för att iterativt utforska längre från varje steg.

Kodexempel i 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;  
}  

I det här exemplet använder vi metoden lokal sökning för att optimera funktionen Fibonacci. Vi itererar genom olika värden på x och beräknar Fibonacci värdet vid varje x. När ett bättre värde hittas uppdaterar vi det bästa värdet och dess motsvarande x.