Heuristic Algorithme de recherche en C++- Explication, exemple et code

Heuristic La recherche est une approche algorithmique puissante utilisée pour trouver des solutions dans des espaces de problèmes complexes en prenant des décisions éclairées basées sur des heuristiques ou des règles empiriques. C'est particulièrement utile lorsqu'une recherche exhaustive n'est pas pratique en raison du grand espace de recherche.

Comment ça fonctionne

1. Heuristic Évaluation: L'algorithme évalue chaque état dans l'espace du problème à l'aide d'une heuristic fonction. Cette fonction estime le "caractère prometteur" de chaque état en fonction de sa proximité avec l'état cible.
2. Stratégie de recherche : l'algorithme sélectionne l'état le plus prometteur en fonction de l' heuristic évaluation. Il utilise une stratégie de recherche telle que Best-First Search, A* Search ou Greedy Search.
3. Extension d'état : l'état sélectionné est étendu en générant ses états voisins. Ce sont des candidats potentiels pour la prochaine étape.
4. Répéter : le processus est répété de manière itérative, en sélectionnant et en développant les états jusqu'à ce que l'état d'objectif soit trouvé ou qu'une condition de fin soit remplie.

Exemple: problème du voyageur de commerce(TSP)

Considérez le problème du voyageur de commerce, où un vendeur doit visiter un ensemble de villes et revenir à la ville de départ tout en minimisant la distance totale parcourue. Une heuristic approche pourrait être l'algorithme du plus proche voisin:

1. Commencez dans une ville au hasard.
2. A chaque étape, choisissez la ville non visitée la plus proche comme prochaine destination.
3. Répétez jusqu'à ce que toutes les villes soient visitées, puis revenez à la ville de départ.

Exemple de code en 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;  
}  

Dans cet exemple, l'algorithme du plus proche voisin est utilisé pour résoudre le problème du voyageur de commerce. C'est une heuristic approche qui choisit la ville non visitée la plus proche à chaque étape, ce qui donne une solution souvent proche de l'optimale.