Heuristic Algoritmi i kërkimit në C++- Shpjegim, Shembull dhe Kodi

Heuristic Kërkimi është një qasje e fuqishme algoritmike e përdorur për të gjetur zgjidhje në hapësira komplekse problemore duke marrë vendime të informuara bazuar në heuristikë ose rregulla të gishtit. Është veçanërisht i dobishëm kur një kërkim shterues është jopraktik për shkak të hapësirës së madhe të kërkimit.

Si punon

1. Heuristic Vlerësimi: Algoritmi vlerëson çdo gjendje në hapësirën e problemit duke përdorur një heuristic funksion. Ky funksion vlerëson "premtueshmërinë" e çdo shteti për sa i përket afërsisë së tij me gjendjen e qëllimit.
2. Strategjia e Kërkimit: Algoritmi zgjedh gjendjen më premtuese bazuar në heuristic vlerësimin. Ai përdor një strategji kërkimi si Best-First Search, A* Search ose Greedy Search.
3. Zgjerimi i Shtetit: Shteti i zgjedhur zgjerohet duke gjeneruar shtetet fqinje. Këta janë kandidatë potencialë për hapin tjetër.
4. Përsëriteni: Procesi përsëritet në mënyrë të përsëritur, duke zgjedhur dhe zgjeruar gjendjet derisa të gjendet gjendja e qëllimit ose të plotësohet një kusht përfundimi.

Shembull: Problemi i shitësit udhëtues(TSP)

Merrni parasysh problemin e shitësit udhëtues, ku një shitës duhet të vizitojë një grup qytetesh dhe të kthehet në qytetin fillestar duke minimizuar distancën totale të përshkuar. Një heuristic qasje mund të jetë Algoritmi i fqinjit më të afërt:

1. Filloni në një qytet të rastësishëm.
2. Në çdo hap, zgjidhni qytetin më të afërt të pavizituar si destinacion tjetër.
3. Përsëriteni derisa të vizitohen të gjitha qytetet, pastaj kthehuni në qytetin fillestar.

Shembull kodi në 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;  
}  

Në këtë shembull, Algoritmi i fqinjit më të afërt përdoret për të zgjidhur problemin e shitësit udhëtues. Është një heuristic qasje që zgjedh qytetin më të afërt të pavizituar në çdo hap, duke rezultuar në një zgjidhje që shpesh është afër optimales.