Satunnaishakualgoritmi (Random Search) C++:ssa- Selitys, esimerkki ja koodi

Satunnaishakualgoritmi on hakumenetelmä, joka perustuu satunnaisten ratkaisujen valintaan hakuavaruudesta ja sen tarkistamiseen, pystyvätkö ne ratkaisemaan ongelman. Tätä lähestymistapaa käytetään usein, kun hakua ohjaavaa tietoa tai strategiaa ei ole.

Kuinka se toimii

1. Alustus: Aloita satunnaisesti luodulla alkuratkaisujen joukolla.
2. Arviointi: Arvioi kunkin ratkaisun laatu tavoitefunktion tai arviointikriteerien perusteella.
3. Valinta: Valitse joukosta osajoukko parhaista ratkaisuista todennäköisyyksien tai satunnaisen valinnan perusteella.
4. Testaus: Testaa, pystyvätkö valitut ratkaisut ratkaisemaan ongelman.
5. Toista: Toista vaiheet 2–4, kunnes saavutetaan tyydyttävä tulos tai saavutetaan ennalta määritetty iteraatioiden määrä.

Esimerkki: Fibonacci Toiminnon optimointi

Tarkastellaan funktion F(x) = F(x-1) + F(x-2) optimointitehtävää Fibonacci, jossa F(0) = 0, F(1) = 1. Haluamme löytää x:n arvon, jolle F(x) on maksimoitu. Satunnaishakumenetelmä voi valita satunnaisesti x:n arvot, laskea arvon Fibonacci jokaisessa x:ssä ja valita x:n arvon, joka vastaa suurinta Fibonacci saatua arvoa.

Esimerkki koodista C++:ssa

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

Tässä esimerkissä käytämme satunnaishakumenetelmää funktion optimointiin Fibonacci. Valitsemme satunnaisesti x:n arvot, laskemme Fibonacci arvon jokaisessa x:ssä ja valitsemme sitten x:n arvon, joka vastaa suurinta Fibonacci laskemaamme arvoa.