Zufallssuchalgorithmus (Random Search) in C++ – Erklärung, Beispiel und Code

Der Zufallssuchalgorithmus ist eine Suchmethode, die darauf basiert, zufällig eine Reihe von Lösungen aus dem Suchraum auszuwählen und zu prüfen, ob sie das Problem lösen können. Dieser Ansatz wird häufig verwendet, wenn keine spezifischen Informationen oder Strategien zur Steuerung der Suche vorliegen.

Wie es funktioniert

1. Initialisierung: Beginnen Sie mit einem zufällig generierten Satz anfänglicher Lösungen.
2. Bewertung: Bewerten Sie die Qualität jeder Lösung anhand der Zielfunktion oder der Bewertungskriterien.
3. Auswahl: Wählen Sie anhand von Wahrscheinlichkeiten oder zufälliger Auswahl eine Teilmenge der besten Lösungen aus der Menge aus.
4. Testen: Testen Sie, ob die ausgewählten Lösungen das Problem lösen können.
5. Wiederholen: Wiederholen Sie die Schritte 2 bis 4, bis ein zufriedenstellendes Ergebnis erzielt wird oder eine vordefinierte Anzahl von Iterationen erreicht ist.

Beispiel: Optimierung der Fibonacci Funktion

Betrachten Sie das Optimierungsproblem der Fibonacci Funktion F(x) = F(x-1) + F(x-2) mit F(0) = 0, F(1) = 1. Wir wollen den Wert von x finden, für den F(x) wird maximiert. Die Zufallssuchmethode kann Werte von x zufällig auswählen, den Fibonacci Wert an jedem x berechnen und den Wert von x auswählen, der dem höchsten Fibonacci erhaltenen Wert entspricht.

Codebeispiel in 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;  
}  

In diesem Beispiel verwenden wir die Zufallssuchmethode, um die Fibonacci Funktion zu optimieren. Wir wählen zufällig Werte von x aus, berechnen den Fibonacci Wert an jedem x und wählen dann den Wert von x aus, der dem höchsten Fibonacci von uns berechneten Wert entspricht.