Heuristic Algoritm de căutare în C++- Explicație, Exemplu și Cod

Heuristic Căutarea este o abordare algoritmică puternică folosită pentru a găsi soluții în spații de probleme complexe, luând decizii informate bazate pe euristică sau reguli generale. Este deosebit de util atunci când o căutare exhaustivă nu este practică din cauza spațiului mare de căutare.

Cum functioneaza

1. Heuristic Evaluare: algoritmul evaluează fiecare stare din spațiul problemei folosind o heuristic funcție. Această funcție estimează „promițăbilitatea” fiecărei stări în ceea ce privește apropierea de starea scopului.
2. Strategie de căutare: algoritmul selectează starea cea mai promițătoare pe baza heuristic evaluării. Utilizează o strategie de căutare precum Best-First Căutare, Căutare A* sau Greedy Căutare.
3. Extinderea stării: starea selectată este extinsă prin generarea stărilor învecinate. Aceștia sunt potențiali candidați pentru următorul pas.
4. Repetare: Procesul se repetă în mod iterativ, selectând și extinzând stările până când este găsită starea obiectivului sau este îndeplinită o condiție de terminare.

Exemplu: Problema vânzătorului ambulant(TSP)

Luați în considerare problema vânzătorului călător, în care un vânzător trebuie să viziteze un set de orașe și să se întoarcă la orașul de plecare, reducând în același timp distanța totală parcursă. O heuristic abordare ar putea fi algoritmul celui mai apropiat vecin:

1. Începeți dintr-un oraș aleatoriu.
2. La fiecare pas, alegeți cel mai apropiat oraș nevizitat ca următoarea destinație.
3. Repetați până când toate orașele sunt vizitate, apoi reveniți la orașul de plecare.

Exemplu de cod în 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;  
}  

În acest exemplu, algoritmul celui mai apropiat vecin este utilizat pentru a rezolva problema vânzătorului ambulant. Este o heuristic abordare care alege cel mai apropiat oraș nevizitat la fiecare pas, rezultând o soluție care este adesea aproape de optimă.