Heuristic Suchalgorithmus in C++ – Erklärung, Beispiel und Code

Heuristic Die Suche ist ein leistungsstarker algorithmischer Ansatz, der dazu dient, Lösungen in komplexen Problembereichen zu finden, indem fundierte Entscheidungen auf der Grundlage von Heuristiken oder Faustregeln getroffen werden. Dies ist besonders nützlich, wenn eine umfassende Suche aufgrund des großen Suchraums unpraktisch ist.

Wie es funktioniert

1. Heuristic Auswertung: Der Algorithmus bewertet jeden Zustand im Problemraum mithilfe einer heuristic Funktion. Diese Funktion schätzt die „Vielversprechendheit“ jedes Zustands im Hinblick auf seine Nähe zum Zielzustand.
2. Suchstrategie: Der Algorithmus wählt anhand der Bewertung den vielversprechendsten Zustand aus heuristic. Es verwendet eine Suchstrategie wie Best-First „Suche“, „A*-Suche“ oder Greedy „Suche“.
3. Bundesstaatserweiterung: Der ausgewählte Bundesstaat wird durch die Generierung seiner Nachbarstaaten erweitert. Dies sind potenzielle Kandidaten für den nächsten Schritt.
4. Wiederholen: Der Prozess wird iterativ wiederholt, wobei Zustände ausgewählt und erweitert werden, bis der Zielzustand gefunden oder eine Beendigungsbedingung erfüllt ist.

Beispiel: Problem des Handlungsreisenden(TSP)

Betrachten Sie das Problem des Handlungsreisenden, bei dem ein Verkäufer eine Reihe von Städten besuchen und in die Ausgangsstadt zurückkehren muss, während er gleichzeitig die zurückgelegte Gesamtstrecke minimieren muss. Ein heuristic Ansatz könnte der Nearest-Neighbor-Algorithmus sein:

1. Beginnen Sie in einer zufälligen Stadt.
2. Wählen Sie bei jedem Schritt die nächstgelegene, noch nicht besuchte Stadt als nächstes Ziel aus.
3. Wiederholen Sie diesen Vorgang, bis alle Städte besucht sind, und kehren Sie dann zur Startstadt zurück.

Codebeispiel 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 diesem Beispiel wird der Nearest-Neighbor-Algorithmus verwendet, um das Problem des Handlungsreisenden zu lösen. Es handelt sich um einen heuristic Ansatz, der bei jedem Schritt die nächstgelegene, noch nicht besuchte Stadt auswählt, was zu einer Lösung führt, die oft nahezu optimal ist.