Algoritmi i Kërkimit Lokal (Local Search) në C++- Shpjegim, Shembull dhe Kodi

Algoritmi i Kërkimit Lokal është një metodë për të gjetur zgjidhjen më të mirë brenda një afërsie të gjendjes aktuale. Kjo teknikë përdoret shpesh për të rafinuar zgjidhjet e përafërta duke modifikuar në mënyrë të përsëritur komponentë individualë për të zbuluar gjendje më të mira.

Si punon

1. Inicializimi: Filloni me një gjendje fillestare.
2. Generate Neighbors: Gjeneroni shtete fqinje duke ndryshuar një komponent të gjendjes aktuale.
3. Vlerësimi: Vlerësoni cilësinë e shteteve fqinje duke përdorur një funksion objektiv.
4. Zgjidh shtetin më të mirë: Zgjidhni shtetin fqinj me vlerën më të mirë objektive.
5. Përsëriteni: Përsëritni hapat 2 deri në 4 derisa të mos gjendet një shtet fqinj më i mirë.

Shembull: Optimizimi i Fibonacci funksionit

Shqyrtoni problemin e optimizimit të Fibonacci funksionit F(x) = F(x-1) + F(x-2) me F(0) = 0, F(1) = 1. Ne duam të gjejmë vlerën e x për të cilën F(x) është maksimizuar. Ne mund të përdorim qasjen e Kërkimit Lokal për të eksploruar në mënyrë të përsëritur më larg nga çdo hap.

Shembull kodi në 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;  
}  

Në këtë shembull, ne përdorim metodën Local Search për të optimizuar funksionin Fibonacci. Ne përsërisim vlerat e ndryshme të x dhe llogarisim Fibonacci vlerën në çdo x. Kur gjendet një vlerë më e mirë, ne përditësojmë vlerën më të mirë dhe x-në e saj korresponduese.