Slumpmässig sökalgoritm (Random Search) i C++- Förklaring, exempel och kod

Algoritmen för slumpmässig sökning är en sökmetod som bygger på att slumpmässigt välja en uppsättning lösningar från sökutrymmet och kontrollera om de kan lösa problemet. Detta tillvägagångssätt används ofta när det inte finns någon specifik information eller strategi för att vägleda sökningen.

Hur det fungerar

1. Initiering: Börja med en slumpmässigt genererad uppsättning initiala lösningar.
2. Utvärdering: Utvärdera kvaliteten på varje lösning baserat på den objektiva funktionen eller utvärderingskriterierna.
3. Urval: Välj en delmängd av de bästa lösningarna från uppsättningen baserat på sannolikheter eller slumpmässigt urval.
4. Testning: Testa om de valda lösningarna är kapabla att lösa problemet.
5. Upprepa: Iterera genom steg 2 till 4 tills ett tillfredsställande resultat uppnås eller ett fördefinierat antal iterationer har uppnåtts.

Exempel: Optimera Fibonacci funktionen

Betrakta optimeringsproblemet för Fibonacci funktionen F(x) = F(x-1) + F(x-2) med F(0) = 0, F(1) = 1. Vi vill hitta värdet på x för vilket F(x) är maximerad. Metoden för slumpmässig sökning kan slumpmässigt välja värden på x, beräkna värdet Fibonacci vid varje x och välja värdet på x som motsvarar det högsta Fibonacci värdet som erhållits.

Kodexempel 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 det här exemplet använder vi metoden Random Search för att optimera funktionen Fibonacci. Vi väljer slumpmässigt värden på x, beräknar Fibonacci värdet vid varje x och väljer sedan värdet på x som motsvarar det högsta Fibonacci värdet vi har beräknat.