Αλγόριθμος τυχαίας αναζήτησης (Random Search) σε C++- Επεξήγηση, Παράδειγμα και Κώδικας

Ο αλγόριθμος τυχαίας αναζήτησης είναι μια μέθοδος αναζήτησης που βασίζεται στην τυχαία επιλογή ενός συνόλου λύσεων από τον χώρο αναζήτησης και στον έλεγχο εάν μπορούν να λύσουν το πρόβλημα. Αυτή η προσέγγιση χρησιμοποιείται συχνά όταν δεν υπάρχουν συγκεκριμένες πληροφορίες ή στρατηγική που να καθοδηγούν την αναζήτηση.

Πως δουλεύει

1. Αρχικοποίηση: Ξεκινήστε με ένα τυχαία δημιουργημένο σύνολο αρχικών λύσεων.
2. Αξιολόγηση: Αξιολογήστε την ποιότητα κάθε λύσης με βάση την αντικειμενική λειτουργία ή τα κριτήρια αξιολόγησης.
3. Επιλογή: Επιλέξτε ένα υποσύνολο των καλύτερων λύσεων από το σύνολο με βάση πιθανότητες ή τυχαία επιλογή.
4. Δοκιμή: Ελέγξτε εάν οι επιλεγμένες λύσεις είναι ικανές να λύσουν το πρόβλημα.
5. Επαναλάβετε: Επαναλάβετε τα βήματα 2 έως 4 μέχρι να επιτευχθεί ένα ικανοποιητικό αποτέλεσμα ή να επιτευχθεί ένας προκαθορισμένος αριθμός επαναλήψεων.

Παράδειγμα: Βελτιστοποίηση της Fibonacci συνάρτησης

Θεωρήστε το πρόβλημα βελτιστοποίησης της Fibonacci συνάρτησης F(x) = F(x-1) + F(x-2) με F(0) = 0, F(1) = 1. Θέλουμε να βρούμε την τιμή του x για την οποία Το F(x) μεγιστοποιείται. Η μέθοδος Random Search μπορεί να επιλέξει τυχαία τιμές του x, να υπολογίσει την Fibonacci τιμή σε κάθε x και να επιλέξει την τιμή του x που αντιστοιχεί στην υψηλότερη Fibonacci τιμή που λαμβάνεται.

Παράδειγμα κώδικα σε 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;  
}  

Σε αυτό το παράδειγμα, χρησιμοποιούμε τη μέθοδο τυχαίας αναζήτησης για τη βελτιστοποίηση της Fibonacci συνάρτησης. Επιλέγουμε τυχαία τιμές του x, υπολογίζουμε την Fibonacci τιμή σε κάθε x και μετά επιλέγουμε την τιμή του x που αντιστοιχεί στην υψηλότερη Fibonacci τιμή που έχουμε υπολογίσει.