Tilfældig søgealgoritme (Random Search) i C++- Forklaring, eksempel og kode

Random Search-algoritmen er en søgemetode, der er baseret på tilfældigt at vælge et sæt løsninger fra søgeområdet og kontrollere, om de kan løse problemet. Denne tilgang bruges ofte, når der ikke er nogen specifik information eller strategi til at guide søgningen.

Hvordan det virker

1. Initialisering: Start med et tilfældigt genereret sæt indledende løsninger.
2. Evaluering: Evaluer kvaliteten af ​​hver løsning baseret på den objektive funktion eller evalueringskriterier.
3. Udvælgelse: Vælg en delmængde af de bedste løsninger fra sættet baseret på sandsynligheder eller tilfældig udvælgelse.
4. Test: Test om de valgte løsninger er i stand til at løse problemet.
5. Gentag: Gentag gennem trin 2 til 4, indtil et tilfredsstillende resultat er opnået eller et foruddefineret antal iterationer er nået.

Eksempel: Optimering af Fibonacci funktionen

Overvej optimeringsproblemet for Fibonacci funktionen F(x) = F(x-1) + F(x-2) med F(0) = 0, F(1) = 1. Vi ønsker at finde værdien af ​​x for hvilken F(x) er maksimeret. Tilfældig søgning-metoden kan tilfældigt vælge værdier af x, beregne værdien Fibonacci ved hver x og vælge værdien af ​​x svarende til den højeste Fibonacci opnåede værdi.

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 eksempel bruger vi metoden tilfældig søgning til at optimere funktionen Fibonacci. Vi udvælger tilfældigt værdier af x, beregner Fibonacci værdien ved hvert x, og vælger derefter værdien af ​​x svarende til den højeste Fibonacci værdi, vi har beregnet.