Heuristic Algoritmo de búsqueda en C++- Explicación, ejemplo y código

Heuristic La búsqueda es un poderoso enfoque algorítmico que se utiliza para encontrar soluciones en espacios de problemas complejos al tomar decisiones informadas basadas en heurísticas o reglas generales. Es particularmente útil cuando una búsqueda exhaustiva no es práctica debido al gran espacio de búsqueda.

Cómo funciona

1. Heuristic Evaluación: el algoritmo evalúa cada estado en el espacio del problema usando una heuristic función. Esta función estima la "promesa" de cada estado en términos de su cercanía al estado objetivo.
2. Estrategia de búsqueda: el algoritmo selecciona el estado más prometedor en función de la heuristic evaluación. Utiliza una estrategia de búsqueda como Best-First Search, A* Search o Greedy Search.
3. Expansión de estado: el estado seleccionado se expande generando sus estados vecinos. Estos son candidatos potenciales para el siguiente paso.
4. Repetir: el proceso se repite iterativamente, seleccionando y expandiendo estados hasta que se encuentra el estado objetivo o se cumple una condición de terminación.

Ejemplo: Problema del viajante de comercio(TSP)

Considere el Problema del viajante de comercio, donde un vendedor necesita visitar un conjunto de ciudades y regresar a la ciudad de partida mientras minimiza la distancia total recorrida. Un heuristic enfoque podría ser el algoritmo del vecino más cercano:

1. Comienza en una ciudad al azar.
2. En cada paso, elija la ciudad no visitada más cercana como próximo destino.
3. Repita hasta que se visiten todas las ciudades, luego regrese a la ciudad de inicio.

Ejemplo de código 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;  
}  

En este ejemplo, se utiliza el algoritmo del vecino más cercano para resolver el problema del viajante de comercio. Es un heuristic enfoque que elige la ciudad no visitada más cercana en cada paso, lo que da como resultado una solución que suele ser casi óptima.