Algoritmus náhodného vyhledávání (Random Search) v C++- vysvětlení, příklad a kód

Algoritmus náhodného vyhledávání je metoda vyhledávání založená na náhodném výběru sady řešení z vyhledávacího prostoru a kontrole, zda mohou problém vyřešit. Tento přístup se často používá, když neexistují žádné konkrétní informace nebo strategie, které by vedly hledání.

Jak to funguje

1. Inicializace: Začněte s náhodně vygenerovanou sadou počátečních řešení.
2. Hodnocení: Vyhodnoťte kvalitu každého řešení na základě objektivní funkce nebo hodnotících kritérií.
3. Výběr: Vyberte podmnožinu nejlepších řešení ze sady na základě pravděpodobností nebo náhodného výběru.
4. Testování: Otestujte, zda jsou vybraná řešení schopna problém vyřešit.
5. Opakujte: Opakujte kroky 2 až 4, dokud nedosáhnete uspokojivého výsledku nebo předdefinovaného počtu iterací.

Příklad: Optimalizace Fibonacci funkce

Uvažujme optimalizační problém funkce Fibonacci F(x) = F(x-1) + F(x-2) s F(0) = 0, F(1) = 1. Chceme najít hodnotu x, pro kterou F(x) je maximalizováno. Metoda Random Search může náhodně vybrat hodnoty x, vypočítat Fibonacci hodnotu pro každé x a vybrat hodnotu x odpovídající nejvyšší Fibonacci získané hodnotě.

Příklad kódu 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 tomto příkladu používáme k optimalizaci Fibonacci funkce metodu Random Search. Náhodně vybereme hodnoty x, vypočítáme Fibonacci hodnotu u každého x a pak vybereme hodnotu x odpovídající nejvyšší Fibonacci hodnotě, kterou jsme vypočítali.