Heuristic Iskalni algoritem v C++- razlaga, primer in koda

Heuristic Iskanje je močan algoritemski pristop, ki se uporablja za iskanje rešitev v zapletenih problemskih prostorih s sprejemanjem premišljenih odločitev na podlagi hevristike ali praktičnih pravil. Še posebej je uporabno, kadar je izčrpno iskanje nepraktično zaradi velikega iskalnega prostora.

Kako deluje

1. Heuristic Vrednotenje: Algoritem ovrednoti vsako stanje v problemskem prostoru z uporabo heuristic funkcije. Ta funkcija oceni "obetavnost" vsakega stanja glede na njegovo bližino ciljnemu stanju.
2. Strategija iskanja: algoritem na podlagi ocene izbere najbolj obetavno stanje heuristic. Uporablja iskalno strategijo, kot je Best-First Iskanje, A* Iskanje ali Greedy Iskanje.
3. Razširitev stanja: izbrano stanje se razširi z generiranjem sosednjih stanj. To so potencialni kandidati za naslednji korak.
4. Ponavljanje: postopek se iterativno ponavlja, izbira in razširja stanja, dokler ni najdeno ciljno stanje ali izpolnjen pogoj za prekinitev.

Primer: problem trgovskega potnika(TSP)

Razmislite o problemu potujočega trgovca, kjer mora prodajalec obiskati niz mest in se vrniti v začetno mesto, medtem ko zmanjša skupno prevoženo razdaljo. Pristop heuristic bi lahko bil algoritem najbližjega soseda:

1. Začnite v naključnem mestu.
2. Na vsakem koraku kot naslednji cilj izberite najbližje neobiskano mesto.
3. Ponavljajte, dokler ne obiščete vseh mest, nato se vrnite v začetno mesto.

Primer kode 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 tem primeru se algoritem najbližjega soseda uporablja za reševanje problema trgovskega potnika. To je heuristic pristop, ki na vsakem koraku izbere najbližje neobiskano mesto, rezultat pa je rešitev, ki je pogosto blizu optimalne.