Heuristic Algoritmo de Pesquisa em C++- Explicação, Exemplo e Código

Heuristic A pesquisa é uma abordagem algorítmica poderosa usada para encontrar soluções em espaços de problemas complexos, tomando decisões informadas com base em heurísticas ou regras práticas. É particularmente útil quando uma pesquisa exaustiva é impraticável devido ao grande espaço de pesquisa.

Como funciona

1. Heuristic Avaliação: O algoritmo avalia cada estado no espaço do problema usando uma heuristic função. Essa função estima a "promessa" de cada estado em termos de sua proximidade com o estado objetivo.
2. Estratégia de Busca: O algoritmo seleciona o estado mais promissor com base na heuristic avaliação. Ele usa uma estratégia de pesquisa como Best-First Search, A* Search ou Greedy Search.
3. Expansão de estado: O estado selecionado é expandido gerando seus estados vizinhos. Estes são candidatos potenciais para a próxima etapa.
4. Repetir: o processo é repetido iterativamente, selecionando e expandindo os estados até que o estado objetivo seja encontrado ou uma condição de término seja atendida.

Exemplo: Problema do Caixeiro Viajante(TSP)

Considere o Problema do Caixeiro Viajante, onde um vendedor precisa visitar um conjunto de cidades e retornar à cidade inicial minimizando a distância total percorrida. Uma heuristic abordagem poderia ser o algoritmo do vizinho mais próximo:

1. Comece em uma cidade aleatória.
2. A cada passo, escolha a cidade não visitada mais próxima como próximo destino.
3. Repita até que todas as cidades sejam visitadas e, em seguida, retorne à cidade inicial.

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

Neste exemplo, o Algoritmo do Vizinho Mais Próximo é usado para resolver o Problema do Caixeiro Viajante. É uma heuristic abordagem que escolhe a cidade não visitada mais próxima a cada etapa, resultando em uma solução geralmente próxima do ideal.