Lokální vyhledávací (Local Search) algoritmus v C++- vysvětlení, příklad a kód

Algoritmus místního vyhledávání je metoda pro nalezení nejlepšího řešení v blízkosti aktuálního stavu. Tato technika se často používá k upřesnění přibližných řešení opakovaným modifikováním jednotlivých komponent za účelem objevení lepších stavů.

Jak to funguje

1. Inicializace: Začněte s počátečním stavem.
2. Generovat sousedy: Vygenerujte sousední státy změnou součásti aktuálního stavu.
3. Hodnocení: Hodnotit kvalitu sousedních států pomocí objektivní funkce.
4. Select Best State: Vyberte sousední stát s nejlepší objektivní hodnotou.
5. Opakujte: Opakujte kroky 2 až 4, dokud nenajdete lepší sousední stát.

Příklad: Optimalizace Fibonacci funkce

Uvažujme optimalizační problém funkce Fibonacci F(x) = F(x-1) + F(x-2) s F(0) = 0, F(1) = 1. Chceme najít hodnotu x, pro kterou F(x) je maximalizováno. Můžeme použít přístup Local Search k iterativnímu prozkoumání dále od každého kroku.

Příklad kódu v 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;  
}  

V tomto příkladu používáme k optimalizaci Fibonacci funkce metodu místního vyhledávání. Iterujeme přes různé hodnoty x a vypočítáme Fibonacci hodnotu pro každé x. Když je nalezena lepší hodnota, aktualizujeme nejlepší hodnotu a jí odpovídající x.