Algoritam nasumičnog pretraživanja (Random Search) u C++- objašnjenje, primjer i kod

Algoritam Random Search je metoda pretraživanja koja se temelji na nasumičnom odabiru skupa rješenja iz prostora pretraživanja i provjeri mogu li ona riješiti problem. Ovaj se pristup često koristi kada ne postoje određene informacije ili strategija za usmjeravanje pretraživanja.

Kako radi

1. Inicijalizacija: Započnite s nasumično generiranim skupom početnih rješenja.
2. Evaluacija: Ocijenite kvalitetu svakog rješenja na temelju funkcije cilja ili kriterija evaluacije.
3. Odabir: Odaberite podskup najboljih rješenja iz skupa na temelju vjerojatnosti ili slučajnog odabira.
4. Testiranje: Testirajte mogu li odabrana rješenja riješiti problem.
5. Ponavljanje: Ponavljajte korake od 2 do 4 dok se ne postigne zadovoljavajući rezultat ili dok se ne postigne unaprijed definirani broj ponavljanja.

Primjer: Optimiziranje Fibonacci funkcije

Razmotrimo problem optimizacije funkcije Fibonacci F(x) = F(x-1) + F(x-2) s F(0) = 0, F(1) = 1. Želimo pronaći vrijednost x za koju F(x) je maksimiziran. Metoda slučajnog pretraživanja može nasumično odabrati vrijednosti x, izračunati Fibonacci vrijednost za svaki x i odabrati vrijednost x koja odgovara najvišoj Fibonacci dobivenoj vrijednosti.

Primjer koda u 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;  
}  

U ovom primjeru koristimo metodu nasumičnog pretraživanja za optimizaciju Fibonacci funkcije. Nasumično biramo vrijednosti x, izračunavamo Fibonacci vrijednost za svaki x, a zatim biramo vrijednost x koja odgovara najvišoj Fibonacci vrijednosti koju smo izračunali.