Heuristic Sökalgoritm i C++- Förklaring, exempel och kod

Heuristic Sökning är ett kraftfullt algoritmiskt tillvägagångssätt som används för att hitta lösningar i komplexa problemområden genom att fatta välgrundade beslut baserat på heuristik eller tumregler. Det är särskilt användbart när en uttömmande sökning är opraktisk på grund av det stora sökutrymmet.

Hur det fungerar

1. Heuristic Utvärdering: Algoritmen utvärderar varje tillstånd i problemutrymmet med hjälp av en heuristic funktion. Denna funktion uppskattar varje stats "lovande" i termer av dess närhet till måltillståndet.
2. Sökstrategi: Algoritmen väljer det mest lovande tillståndet baserat på utvärderingen heuristic. Den använder en sökstrategi som Best-First Sök, A* Sök eller Greedy Sök.
3. Tillståndsexpansion: Det valda tillståndet utökas genom att generera dess närliggande tillstånd. Dessa är potentiella kandidater för nästa steg.
4. Upprepa: Processen upprepas iterativt, val och utvidgning av tillstånd tills måltillståndet hittas eller ett avslutningsvillkor är uppfyllt.

Exempel: Traveling Salesman Problem(TSP)

Tänk på problemet med resande säljare, där en säljare måste besöka en uppsättning städer och återvända till startstaden samtidigt som han minimerar det totala tillryggalagda avståndet. Ett heuristic tillvägagångssätt kan vara algoritmen för närmaste granne:

1. Börja i en slumpmässig stad.
2. Vid varje steg väljer du närmaste obesökta stad som nästa destination.
3. Upprepa tills alla städer har besökts och återvänd sedan till startstaden.

Kodexempel i 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;  
}  

I det här exemplet används algoritmen för närmaste granne för att lösa problemet med resande säljare. Det är ett heuristic tillvägagångssätt som väljer närmaste obesökta stad vid varje steg, vilket resulterar i en lösning som ofta är nära optimal.