Algorytm wyszukiwania losowego (Random Search) w C++- wyjaśnienie, przykład i kod

Algorytm Wyszukiwania Losowego to metoda wyszukiwania polegająca na losowym wybraniu zestawu rozwiązań z przestrzeni poszukiwań i sprawdzeniu, czy mogą one rozwiązać problem. Takie podejście jest często stosowane, gdy nie ma konkretnych informacji ani strategii, które mogłyby poprowadzić wyszukiwanie.

Jak to działa

1. Inicjalizacja: zacznij od losowo wygenerowanego zestawu początkowych rozwiązań.
2. Ocena: Oceń jakość każdego rozwiązania na podstawie funkcji celu lub kryteriów oceny.
3. Wybór: wybierz podzbiór najlepszych rozwiązań ze zbioru na podstawie prawdopodobieństwa lub losowego wyboru.
4. Testowanie: Sprawdź, czy wybrane rozwiązania są w stanie rozwiązać problem.
5. Powtarzaj: powtarzaj kroki od 2 do 4, aż do uzyskania zadowalającego wyniku lub osiągnięcia określonej liczby iteracji.

Przykład: optymalizacja Fibonacci funkcji

Rozważmy problem optymalizacji funkcji Fibonacci F(x) = F(x-1) + F(x-2) gdzie F(0) = 0, F(1) = 1. Chcemy znaleźć wartość x dla której F(x) jest zmaksymalizowane. Metoda wyszukiwania losowego może losowo wybrać wartości x, obliczyć wartość Fibonacci dla każdego x i wybrać wartość x odpowiadającą najwyższej Fibonacci uzyskanej wartości.

Przykład kodu w 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;  
}  

W tym przykładzie używamy metody Wyszukiwanie losowe w celu optymalizacji Fibonacci funkcji. Losowo wybieramy wartości x, obliczamy Fibonacci wartość dla każdego x, a następnie wybieramy wartość x odpowiadającą najwyższej Fibonacci obliczonej wartości.