Heuristic Søgealgoritme i C++- Forklaring, eksempel og kode

Heuristic Søgning er en kraftfuld algoritmisk tilgang, der bruges til at finde løsninger i komplekse problemområder ved at træffe informerede beslutninger baseret på heuristik eller tommelfingerregler. Det er især nyttigt, når en udtømmende søgning er upraktisk på grund af den store søgeplads.

Hvordan det virker

1. Heuristic Evaluering: Algoritmen evaluerer hver tilstand i problemrummet ved hjælp af en heuristic funktion. Denne funktion estimerer den "lovende" for hver stat i forhold til dens nærhed til måltilstanden.
2. Søgestrategi: Algoritmen vælger den mest lovende tilstand baseret på evalueringen heuristic. Den bruger en søgestrategi som Best-First Search, A* Search eller Greedy Search.
3. Tilstandsudvidelse: Den valgte tilstand udvides ved at generere dens nabotilstande. Disse er potentielle kandidater til næste trin.
4. Gentag: Processen gentages iterativt, idet tilstande udvælges og udvides, indtil måltilstanden er fundet, eller en afslutningsbetingelse er opfyldt.

Eksempel: Traveling Salesman Problem(TSP)

Overvej problemet med den rejsende sælger, hvor en sælger skal besøge et sæt byer og vende tilbage til startbyen og samtidig minimere den samlede tilbagelagte distance. En heuristic tilgang kunne være den nærmeste nabo-algoritme:

1. Start i en tilfældig by.
2. Ved hvert trin skal du vælge den nærmeste ubesøgte by som næste destination.
3. Gentag indtil alle byer er besøgt, og vend derefter tilbage til startbyen.

Kodeeksempel 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 dette eksempel bruges den nærmeste nabo-algoritme til at løse problemet med den rejsende sælger. Det er en heuristic tilgang, der vælger den nærmeste ubesøgte by ved hvert trin, hvilket resulterer i en løsning, der ofte er tæt på optimal.