Heuristic Algoritam pretraživanja u C++- objašnjenje, primjer i kod

Heuristic Pretraživanje je moćan algoritamski pristup koji se koristi za pronalaženje rješenja u složenim prostorima problema donošenjem informiranih odluka na temelju heuristike ili praktičnih pravila. Osobito je korisno kada je iscrpno pretraživanje nepraktično zbog velikog prostora za pretraživanje.

Kako radi

1. Heuristic Evaluacija: Algoritam procjenjuje svako stanje u problemskom prostoru pomoću heuristic funkcije. Ova funkcija procjenjuje "perspektivnost" svake države u smislu njezine blizine ciljnoj državi.
2. Strategija pretraživanja: Algoritam odabire stanje koje najviše obećava na temelju heuristic procjene. Koristi strategiju pretraživanja kao što je Best-First Search, A* Search ili Greedy Search.
3. Proširenje stanja: odabrano stanje se proširuje generiranjem susjednih stanja. Ovo su potencijalni kandidati za sljedeći korak.
4. Ponavljanje: proces se ponavlja iterativno, birajući i proširujući stanja dok se ne pronađe ciljno stanje ili dok se ne ispuni uvjet prekida.

Primjer: problem trgovačkog putnika(TSP)

Razmotrimo problem trgovačkog putnika, gdje trgovački putnik treba posjetiti skup gradova i vratiti se u početni grad dok minimalizira ukupnu prijeđenu udaljenost. Pristup heuristic bi mogao biti algoritam najbližeg susjeda:

1. Započnite u nasumično odabranom gradu.
2. Na svakom koraku odaberite najbliži neposjećeni grad kao sljedeće odredište.
3. Ponavljajte dok se ne posjete svi gradovi, zatim se vratite u početni grad.

Primjer koda u 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;  
}  

U ovom primjeru, algoritam najbližeg susjeda koristi se za rješavanje problema trgovačkog putnika. To je heuristic pristup koji odabire najbliži neposjećeni grad na svakom koraku, što rezultira rješenjem koje je često blizu optimalnog.