Heuristic Algoritmus hledání v C++- vysvětlení, příklad a kód

Heuristic Vyhledávání je výkonný algoritmický přístup používaný k nalezení řešení ve složitých problémových prostorech pomocí informovaných rozhodnutí na základě heuristiky nebo orientačních pravidel. Je to zvláště užitečné, když je vyčerpávající vyhledávání nepraktické kvůli velkému prostoru pro vyhledávání.

Jak to funguje

1. Heuristic Vyhodnocení: Algoritmus vyhodnotí každý stav v problémovém prostoru pomocí heuristic funkce. Tato funkce odhaduje „nadějnost“ každého stavu z hlediska jeho blízkosti k cílovému stavu.
2. Strategie vyhledávání: Algoritmus vybere nejslibnější stav na základě vyhodnocení heuristic. Využívá vyhledávací strategii jako Best-First Search, A* Search nebo Greedy Search.
3. Rozšíření stavu: Vybraný stát se rozšíří vygenerováním sousedních stavů. To jsou potenciální kandidáti na další postup.
4. Opakovat: Proces se iterativně opakuje, vybírá a rozšiřuje stavy, dokud není nalezen cílový stav nebo je splněna podmínka ukončení.

Příklad: Problém cestujícího prodejce(TSP)

Zvažte problém cestujícího obchodníka, kdy obchodník potřebuje navštívit řadu měst a vrátit se do výchozího města a zároveň minimalizovat celkovou ujetou vzdálenost. Přístupem heuristic by mohl být algoritmus nejbližšího souseda:

1. Začněte v náhodném městě.
2. V každém kroku zvolte jako další cíl nejbližší nenavštívené město.
3. Opakujte, dokud nenavštívíte všechna města, a poté se vraťte do výchozího města.

Příklad kódu v 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;  
}  

V tomto příkladu je k vyřešení problému cestujícího obchodníka použit algoritmus nejbližšího souseda. Je to heuristic přístup, který na každém kroku vybírá nejbližší nenavštívené město, což vede k řešení, které se často blíží optimálnímu.