Heuristic Zoekalgoritme in C++- Uitleg, voorbeeld en code

Heuristic Zoeken is een krachtige algoritmische benadering die wordt gebruikt om oplossingen te vinden in complexe probleemgebieden door weloverwogen beslissingen te nemen op basis van heuristieken of vuistregels. Het is vooral handig wanneer een uitgebreide zoekopdracht onpraktisch is vanwege de grote zoekruimte.

Hoe het werkt

1. Heuristic Evaluatie: het algoritme evalueert elke toestand in de probleemruimte met behulp van een heuristic functie. Deze functie schat de "veelbelovende" van elke toestand in termen van de nabijheid van de doeltoestand.
2. Zoekstrategie: het algoritme selecteert de meest veelbelovende staat op basis van de heuristic evaluatie. Het gebruikt een zoekstrategie zoals Best-First Zoeken, A* Zoeken of Greedy Zoeken.
3. Staatsuitbreiding: de geselecteerde staat wordt uitgebreid door zijn aangrenzende staten te genereren. Dit zijn potentiële kandidaten voor de volgende stap.
4. Herhalen: het proces wordt iteratief herhaald, waarbij statussen worden geselecteerd en uitgebreid totdat de doelstatus is gevonden of aan een beëindigingsvoorwaarde is voldaan.

Voorbeeld: handelsreizigerprobleem(TSP)

Overweeg het handelsreizigersprobleem, waarbij een verkoper een reeks steden moet bezoeken en moet terugkeren naar de startstad terwijl hij de totale afgelegde afstand minimaliseert. Een heuristic benadering zou het dichtstbijzijnde buuralgoritme kunnen zijn:

1. Begin bij een willekeurige stad.
2. Kies bij elke stap de dichtstbijzijnde onbezochte stad als volgende bestemming.
3. Herhaal dit totdat alle steden zijn bezocht en keer dan terug naar de startstad.

Codevoorbeeld in 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;  
}  

In dit voorbeeld wordt het Nearest Neighbor-algoritme gebruikt om het handelsreizigersprobleem op te lossen. Het is een heuristic aanpak die bij elke stap de dichtstbijzijnde niet-bezochte stad kiest, wat resulteert in een oplossing die vaak bijna optimaal is.