Algoritem naključnega iskanja (Random Search) v C++ – razlaga, primer in koda

Algoritem naključnega iskanja je metoda iskanja, ki temelji na naključnem izbiranju niza rešitev iz iskalnega prostora in preverjanju, ali lahko rešijo problem. Ta pristop se pogosto uporablja, kadar ni posebnih informacij ali strategije, ki bi vodila iskanje.

Kako deluje

1. Inicializacija: Začnite z naključno ustvarjenim nizom začetnih rešitev.
2. Vrednotenje: Ocenite kakovost vsake rešitve na podlagi ciljne funkcije ali kriterijev vrednotenja.
3. Izbor: izberite podmnožico najboljših rešitev iz niza na podlagi verjetnosti ali naključnega izbora.
4. Testiranje: Preizkusite, ali so izbrane rešitve sposobne rešiti problem.
5. Ponavljanje: Ponavljajte korake od 2 do 4, dokler ne dosežete zadovoljivega rezultata ali dokler ne dosežete vnaprej določenega števila ponovitev.

Primer: Optimizacija Fibonacci funkcije

Razmislite o optimizacijskem problemu funkcije Fibonacci F(x) = F(x-1) + F(x-2) s F(0) = 0, F(1) = 1. Želimo najti vrednost x, za katero F(x) je maksimiziran. Metoda naključnega iskanja lahko naključno izbere vrednosti x, izračuna vrednost Fibonacci pri vsakem x in izbere vrednost x, ki ustreza najvišji Fibonacci dobljeni vrednosti.

Primer kode v 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;  
}  

V tem primeru uporabljamo metodo naključnega iskanja za optimizacijo funkcije Fibonacci. Naključno izberemo vrednosti x, izračunamo Fibonacci vrednost pri vsakem x in nato izberemo vrednost x, ki ustreza najvišji Fibonacci vrednosti, ki smo jo izračunali.