Algoritmi i kërkimit të rastësishëm (Random Search) në C++- Shpjegim, Shembull dhe Kodi

Algoritmi i kërkimit të rastësishëm është një metodë kërkimi e bazuar në zgjedhjen e rastësishme të një grupi zgjidhjesh nga hapësira e kërkimit dhe kontrollimin nëse ato mund ta zgjidhin problemin. Kjo qasje përdoret shpesh kur nuk ka informacion ose strategji specifike për të udhëhequr kërkimin.

Si punon

1. Inicializimi: Filloni me një grup zgjidhjesh fillestare të krijuara rastësisht.
2. Vlerësimi: Vlerësoni cilësinë e secilës zgjidhje bazuar në funksionin objektiv ose kriteret e vlerësimit.
3. Zgjedhja: Zgjidhni një nëngrup të zgjidhjeve më të mira nga grupi bazuar në probabilitete ose përzgjedhje të rastësishme.
4. Testimi: Provoni nëse zgjidhjet e zgjedhura janë të afta për të zgjidhur problemin.
5. Përsëriteni: Përsëriteni përmes hapave 2 deri në 4 derisa të arrihet një rezultat i kënaqshëm ose të arrihet një numër i paracaktuar përsëritjesh.

Shembull: Optimizimi i Fibonacci funksionit

Shqyrtoni problemin e optimizimit të Fibonacci funksionit F(x) = F(x-1) + F(x-2) me F(0) = 0, F(1) = 1. Ne duam të gjejmë vlerën e x për të cilën F(x) është maksimizuar. Metoda Random Search mund të zgjedhë rastësisht vlerat e x, të llogarisë vlerën Fibonacci në çdo x dhe të zgjedhë vlerën e x që korrespondon me Fibonacci vlerën më të lartë të marrë.

Shembull kodi 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ë këtë shembull, ne përdorim metodën e kërkimit të rastësishëm për të optimizuar Fibonacci funksionin. Ne zgjedhim rastësisht vlerat e x, llogarisim Fibonacci vlerën në çdo x dhe më pas zgjedhim vlerën e x që korrespondon me Fibonacci vlerën më të lartë që kemi llogaritur.