Véletlenszerű keresési (Random Search) algoritmus C++ nyelven – magyarázat, példa és kód

A Véletlenszerű keresés algoritmusa egy olyan keresési módszer, amely a keresési térből véletlenszerűen kiválaszt egy megoldáskészletet, és ellenőrzi, hogy azok meg tudják-e oldani a problémát. Ezt a megközelítést gyakran alkalmazzák, ha nincs konkrét információ vagy stratégia a keresés irányítására.

Hogyan működik

1. Inicializálás: Kezdje a kezdeti megoldások véletlenszerűen generált halmazával.
2. Értékelés: Értékelje az egyes megoldások minőségét a célfüggvény vagy az értékelési szempontok alapján.
3. Kiválasztás: Válassza ki a legjobb megoldások egy részhalmazát a halmazból valószínűségek vagy véletlenszerű kiválasztás alapján.
4. Tesztelés: Tesztelje, hogy a kiválasztott megoldások alkalmasak-e a probléma megoldására.
5. Ismételje meg: Ismételje meg a 2–4. lépéseket, amíg kielégítő eredményt nem ér el, vagy el nem éri az előre meghatározott számú iterációt.

Példa: A Fibonacci funkció optimalizálása

Tekintsük az F(x) = F(x-1) + F(x-2) függvény optimalizálási problémáját, Fibonacci ahol F(0) = 0, F(1) = 1. Meg akarjuk találni az x értékét, amelyre F(x) maximalizált. A Véletlenszerű keresés módszere véletlenszerűen kiválaszthatja x értékeit, kiszámíthatja az értéket minden x-nél, és kiválaszthatja a legmagasabb kapott értéknek Fibonacci megfelelő x értéket. Fibonacci

Kódpélda C++ nyelven

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

Ebben a példában a Véletlenszerű keresés módszerét használjuk a Fibonacci függvény optimalizálására. Véletlenszerűen kiválasztjuk x értékeit, kiszámítjuk az Fibonacci értéket minden x-nél, majd kiválasztjuk az Fibonacci általunk számított legmagasabb értéknek megfelelő x értéket.