Αλγόριθμος τοπικής αναζήτησης (Local 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) μεγιστοποιείται. Μπορούμε να χρησιμοποιήσουμε την προσέγγιση Τοπικής αναζήτησης για να εξερευνήσουμε επαναληπτικά μακρύτερα από κάθε βήμα.

Παράδειγμα κώδικα σε C++

#include <iostream>  
  
int fibonacci(int n) {  
    if(n <= 0) return 0;  
    if(n == 1) return 1;  
    return fibonacci(n- 1) + fibonacci(n- 2);  
}  
  
int localSearchFibonacci(int maxIterations) {  
    int bestX = 0;  
    int bestValue = 0;  
  
    for(int x = 0; x < maxIterations; ++x) {  
        int value = fibonacci(x);  
        if(value > bestValue) {  
            bestValue = value;  
            bestX = x;  
        }  
    }  
  
    return bestX;  
}  
  
int main() {  
    int maxIterations = 20;  
    int result = localSearchFibonacci(maxIterations);  
  
    std::cout << "Optimal x for maximum Fibonacci value: " << result << std::endl;  
  
    return 0;  
}  

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