Tilfeldig søkealgoritme (Random Search) i C++- Forklaring, eksempel og kode

Tilfeldig søk-algoritmen er en søkemetode basert på å tilfeldig velge et sett med løsninger fra søkeområdet og sjekke om de kan løse problemet. Denne tilnærmingen brukes ofte når det ikke er spesifikk informasjon eller strategi for å lede søket.

Hvordan det fungerer

1. Initialisering: Start med et tilfeldig generert sett med innledende løsninger.
2. Evaluering: Evaluer kvaliteten på hver løsning basert på den objektive funksjonen eller evalueringskriteriene.
3. Utvalg: Velg en delmengde av de beste løsningene fra settet basert på sannsynligheter eller tilfeldig utvalg.
4. Testing: Test om de valgte løsningene er i stand til å løse problemet.
5. Gjenta: Iterer gjennom trinn 2 til 4 til et tilfredsstillende resultat er oppnådd eller et forhåndsdefinert antall iterasjoner er nådd.

Eksempel: Optimalisering av Fibonacci funksjonen

Tenk på optimaliseringsproblemet til Fibonacci funksjonen F(x) = F(x-1) + F(x-2) med F(0) = 0, F(1) = 1. Vi ønsker å finne verdien av x som F(x) er maksimert. Tilfeldig søk-metoden kan tilfeldig velge verdier av x, beregne verdien Fibonacci ved hver x, og velge verdien av x som tilsvarer den høyeste Fibonacci verdien som er oppnådd.

Kodeeksempel i C++

#include <iostream>  
#include <cstdlib>  
#include <ctime>  
  
int fibonacci(int n) {  
    if(n <= 0) return 0;  
    if(n == 1) return 1;  
    return fibonacci(n- 1) + fibonacci(n- 2);  
}  
  
int randomSearchFibonacci(int maxIterations) {  
    int bestX = 0;  
    int bestValue = 0;  
  
    srand(time(0));  
  
    for(int i = 0; i < maxIterations; ++i) {  
        int x = rand() % maxIterations;  
        int value = fibonacci(x);  
        if(value > bestValue) {  
            bestValue = value;  
            bestX = x;  
        }  
    }  
  
    return bestX;  
}  
  
int main() {  
    int maxIterations = 20;  
    int result = randomSearchFibonacci(maxIterations);  
  
    std::cout << "Optimal x for maximum Fibonacci value: " << result << std::endl;  
  
    return 0;  
}  

I dette eksemplet bruker vi metoden tilfeldig søk for å optimalisere Fibonacci funksjonen. Vi velger tilfeldig verdier av x, beregner Fibonacci verdien ved hver x, og velger deretter verdien av x som tilsvarer den høyeste Fibonacci verdien vi har beregnet.