Atsitiktinės paieškos (Random Search) algoritmas C++ – paaiškinimas, pavyzdys ir kodas

Atsitiktinės paieškos algoritmas yra paieškos metodas, pagrįstas atsitiktiniu sprendimų rinkinio parinkimu iš paieškos erdvės ir patikrinimu, ar jie gali išspręsti problemą. Šis metodas dažnai naudojamas, kai nėra konkrečios informacijos ar strategijos, kuri padėtų ieškoti.

Kaip tai veikia

1. Inicijavimas: pradėkite nuo atsitiktinai sugeneruoto pradinių sprendimų rinkinio.
2. Įvertinimas: įvertinkite kiekvieno sprendimo kokybę pagal tikslinę funkciją arba vertinimo kriterijus.
3. Pasirinkimas: pagal tikimybes arba atsitiktinę atranką iš rinkinio pasirinkite geriausių sprendimų poaibį.
4. Testavimas: patikrinkite, ar pasirinkti sprendimai gali išspręsti problemą.
5. Pakartokite: kartokite nuo 2 iki 4 žingsnių, kol pasieksite patenkinamą rezultatą arba pasieksite iš anksto nustatytą pakartojimų skaičių.

Pavyzdys: Fibonacci funkcijos optimizavimas

Apsvarstykite funkcijos F(x) = F(x-1) + F(x-2) optimizavimo uždavinį Fibonacci, kai F(0) = 0, F(1) = 1. Norime rasti x reikšmę, kuriai F(x) yra maksimalus. Atsitiktinės paieškos metodas gali atsitiktinai pasirinkti x reikšmes, apskaičiuoti Fibonacci kiekvieno x reikšmę ir pasirinkti x reikšmę, atitinkančią didžiausią Fibonacci gautą reikšmę.

Kodo pavyzdys 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;  
}  

Šiame pavyzdyje funkcijai optimizuoti naudojame atsitiktinės paieškos metodą Fibonacci. Atsitiktinai pasirenkame x reikšmes, apskaičiuojame Fibonacci kiekvieno x reikšmę, tada pasirenkame x reikšmę, atitinkančią didžiausią Fibonacci mūsų apskaičiuotą reikšmę.