Paikallinen (Local Search) hakualgoritmi C++:ssa- selitys, esimerkki ja koodi

Paikallinen hakualgoritmi on menetelmä löytää paras ratkaisu nykyisen tilan läheisyydestä. Tätä tekniikkaa käytetään usein tarkentamaan likimääräisiä ratkaisuja muokkaamalla iteratiivisesti yksittäisiä komponentteja parempien tilojen löytämiseksi.

Kuinka se toimii

1. Alustus: Aloita alkutilasta.
2. Luo naapureita: Luo naapurivaltioita muuttamalla nykyisen tilan komponenttia.
3. Arviointi: Arvioi naapurivaltioiden laatua tavoitefunktion avulla.
4. Valitse paras osavaltio: Valitse naapurivaltio, jolla on paras tavoitearvo.
5. Toista: Toista vaiheet 2–4, kunnes parempaa naapuritilaa ei löydy.

Esimerkki: Fibonacci Toiminnon optimointi

Tarkastellaan funktion F(x) = F(x-1) + F(x-2) optimointitehtävää Fibonacci, jossa F(0) = 0, F(1) = 1. Haluamme löytää x:n arvon, jolle F(x) on maksimoitu. Voimme käyttää paikallishakua tutkiaksemme iteratiivisesti kauempana jokaisesta vaiheesta.

Esimerkki koodista C++:ssa

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

Tässä esimerkissä käytämme paikallishakumenetelmää toiminnon optimointiin Fibonacci. Iteroimme x:n eri arvot ja laskemme arvon Fibonacci jokaisessa x:ssä. Kun parempi arvo löytyy, päivitämme parhaan arvon ja sitä vastaavan x:n.