Heuristic Αλγόριθμος αναζήτησης σε C++- Επεξήγηση, Παράδειγμα και Κώδικας

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

Πως δουλεύει

1. Heuristic Αξιολόγηση: Ο αλγόριθμος αξιολογεί κάθε κατάσταση στον προβληματικό χώρο χρησιμοποιώντας μια heuristic συνάρτηση. Αυτή η συνάρτηση εκτιμά την «υποσχέσεις» κάθε κράτους ως προς την εγγύτητά του με την κατάσταση στόχου.
2. Στρατηγική αναζήτησης: Ο αλγόριθμος επιλέγει την πιο υποσχόμενη κατάσταση με βάση την heuristic αξιολόγηση. Χρησιμοποιεί μια στρατηγική αναζήτησης όπως Best-First Search, A* Search ή Greedy Search.
3. Επέκταση κατάστασης: Η επιλεγμένη κατάσταση επεκτείνεται δημιουργώντας τις γειτονικές της πολιτείες. Αυτοί είναι πιθανοί υποψήφιοι για το επόμενο βήμα.
4. Επανάληψη: Η διαδικασία επαναλαμβάνεται επαναληπτικά, επιλέγοντας και επεκτείνοντας καταστάσεις μέχρι να βρεθεί η κατάσταση στόχου ή να εκπληρωθεί μια συνθήκη τερματισμού.

Παράδειγμα: Πρόβλημα ταξιδιώτη πωλητή(TSP)

Σκεφτείτε το Πρόβλημα του Ταξιδιώτη Πωλητή, όπου ένας πωλητής πρέπει να επισκεφτεί ένα σύνολο πόλεων και να επιστρέψει στην αρχική πόλη, ελαχιστοποιώντας παράλληλα τη συνολική απόσταση που διανύθηκε. Μια heuristic προσέγγιση θα μπορούσε να είναι ο αλγόριθμος του πλησιέστερου γείτονα:

1. Ξεκινήστε από μια τυχαία πόλη.
2. Σε κάθε βήμα, επιλέξτε την πλησιέστερη πόλη χωρίς επίσκεψη ως επόμενο προορισμό.
3. Επαναλάβετε μέχρι να επισκεφθείτε όλες τις πόλεις και μετά επιστρέψτε στην πόλη εκκίνησης.

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

#include <iostream>  
#include <vector>  
#include <cmath>  
#include <algorithm>  
  
struct City {  
    int x, y;  
};  
  
double distance(const City& city1, const City& city2) {  
    return std::sqrt(std::pow(city1.x- city2.x, 2) + std::pow(city1.y- city2.y, 2));  
}  
  
std::vector<int> nearestNeighbor(const std::vector<City>& cities) {  
    int numCities = cities.size();  
    std::vector<int> path(numCities);  
    std::vector<bool> visited(numCities, false);  
  
    path[0] = 0;  
    visited[0] = true;  
  
    for(int i = 1; i < numCities; ++i) {  
        int currentCity = path[i- 1];  
        double minDist = std::numeric_limits<double>::max();  
        int nextCity = -1;  
  
        for(int j = 0; j < numCities; ++j) {  
            if(!visited[j]) {  
                double dist = distance(cities[currentCity], cities[j]);  
                if(dist < minDist) {  
                    minDist = dist;  
                    nextCity = j;  
                }  
            }  
        }  
  
        path[i] = nextCity;  
        visited[nextCity] = true;  
    }  
  
    path.push_back(0); // Return to the starting city  
    return path;  
}  
  
int main() {  
    std::vector<City> cities = {{0, 0}, {1, 3}, {4, 2}, {3, 6}, {7, 1}};  
    std::vector<int> path = nearestNeighbor(cities);  
  
    std::cout << "Traveling Salesman Path: ";  
    for(int city: path) {  
        std::cout << city << ";  
    }  
    std::cout << std::endl;  
  
    return 0;  
}  

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