Heuristic Algoritmo di ricerca in C++- Spiegazione, esempio e codice

Heuristic La ricerca è un potente approccio algoritmico utilizzato per trovare soluzioni in spazi problematici complessi prendendo decisioni informate basate su euristiche o regole empiriche. È particolarmente utile quando una ricerca esaustiva non è pratica a causa dell'ampio spazio di ricerca.

Come funziona

1. Heuristic Valutazione: l'algoritmo valuta ogni stato nello spazio del problema utilizzando una heuristic funzione. Questa funzione stima la "promettenza" di ogni stato in termini di vicinanza allo stato obiettivo.
2. Strategia di ricerca: l'algoritmo seleziona lo stato più promettente in base alla heuristic valutazione. Utilizza una strategia di ricerca come Best-First Ricerca, Ricerca A* o Greedy Ricerca.
3. Espansione dello stato: lo stato selezionato viene espanso generando gli stati vicini. Questi sono potenziali candidati per il passaggio successivo.
4. Ripeti: il processo viene ripetuto in modo iterativo, selezionando ed espandendo gli stati finché non viene trovato lo stato obiettivo o viene soddisfatta una condizione di terminazione.

Esempio: Problema del commesso viaggiatore(TSP)

Considera il problema del venditore ambulante, in cui un venditore deve visitare un insieme di città e tornare alla città di partenza riducendo al minimo la distanza totale percorsa. Un heuristic approccio potrebbe essere l'algoritmo del vicino più vicino:

1. Inizia in una città a caso.
2. Ad ogni passaggio, scegli la città non visitata più vicina come destinazione successiva.
3. Ripeti finché tutte le città non sono state visitate, quindi torna alla città di partenza.

Esempio di codice in 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;  
}  

In questo esempio, l'algoritmo del vicino più vicino viene utilizzato per risolvere il problema del commesso viaggiatore. È un heuristic approccio che sceglie ad ogni passo la città non visitata più vicina, ottenendo una soluzione spesso vicina all'ottimale.