Algoritm de căutare aleatorie (Random Search) în C++- Explicație, Exemplu și Cod

Algoritmul de căutare aleatorie este o metodă de căutare bazată pe selectarea aleatorie a unui set de soluții din spațiul de căutare și verificarea dacă pot rezolva problema. Această abordare este adesea folosită atunci când nu există informații sau strategie specifice care să ghideze căutarea.

Cum functioneaza

1. Inițializare: Începeți cu un set generat aleatoriu de soluții inițiale.
2. Evaluare: Evaluați calitatea fiecărei soluții pe baza funcției obiective sau a criteriilor de evaluare.
3. Selectare: Selectați un subset al celor mai bune soluții din set pe baza probabilităților sau a selecției aleatorii.
4. Testare: Testați dacă soluțiile selectate sunt capabile să rezolve problema.
5. Repetați: Repetați pașii de la 2 la 4 până când se obține un rezultat satisfăcător sau se ajunge la un număr predefinit de iterații.

Exemplu: Optimizarea Fibonacci funcției

Se consideră problema de optimizare a Fibonacci funcției F(x) = F(x-1) + F(x-2) cu F(0) = 0, F(1) = 1. Vrem să aflăm valoarea lui x pentru care F(x) este maximizat. Metoda de căutare aleatorie poate selecta aleatoriu valori ale lui x, poate calcula Fibonacci valoarea la fiecare x și poate alege valoarea lui x corespunzătoare celei mai mari Fibonacci valori obținute.

Exemplu de cod în 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;  
}  

În acest exemplu, folosim metoda de căutare aleatorie pentru a optimiza Fibonacci funcția. Selectăm aleatoriu valorile lui x, calculăm Fibonacci valoarea la fiecare x și apoi alegem valoarea lui x corespunzătoare celei mai mari Fibonacci valori pe care am calculat-o.