Heuristic Algorytm wyszukiwania w C++- wyjaśnienie, przykład i kod

Heuristic Wyszukiwanie to potężne podejście algorytmiczne używane do znajdowania rozwiązań w złożonych przestrzeniach problemowych poprzez podejmowanie świadomych decyzji w oparciu o heurystykę lub praktyczne zasady. Jest to szczególnie przydatne, gdy wyczerpujące wyszukiwanie jest niepraktyczne ze względu na dużą przestrzeń wyszukiwania.

Jak to działa

1. Heuristic Ocena: Algorytm ocenia każdy stan w przestrzeni problemowej za pomocą heuristic funkcji. Ta funkcja szacuje „obiecywanie” każdego stanu pod względem jego bliskości do stanu docelowego.
2. Strategia wyszukiwania: Algorytm wybiera najbardziej obiecujący stan na podstawie heuristic oceny. Wykorzystuje strategię wyszukiwania, taką jak Best-First Wyszukiwanie, Wyszukiwanie A* lub Greedy Wyszukiwanie.
3. Ekspansja stanu: Wybrany stan jest rozszerzany poprzez generowanie sąsiednich stanów. To potencjalni kandydaci do następnego kroku.
4. Powtórz: Proces jest powtarzany iteracyjnie, wybierając i rozszerzając stany, aż do znalezienia stanu docelowego lub spełnienia warunku zakończenia.

Przykład: problem komiwojażera(TSP)

Rozważ problem komiwojażera, w którym sprzedawca musi odwiedzić zestaw miast i wrócić do miasta początkowego, minimalizując całkowitą przebytą odległość. Podejściem heuristic może być algorytm najbliższego sąsiedztwa:

1. Zacznij w losowym mieście.
2. Na każdym kroku wybierz najbliższe nieodwiedzone miasto jako następny cel podróży.
3. Powtarzaj, aż wszystkie miasta zostaną odwiedzone, a następnie wróć do miasta początkowego.

Przykład kodu w 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;  
}  

W tym przykładzie algorytm najbliższego sąsiada jest używany do rozwiązania problemu komiwojażera. Jest to heuristic podejście, które na każdym kroku wybiera najbliższe nieodwiedzone miasto, co skutkuje rozwiązaniem, które często jest bliskie optymalnemu.