Heuristic Cuardaigh Algartam i C++- Míniú, Sampla agus Cód

Heuristic Is cur chuige cumhachtach algartamach é cuardach a úsáidtear chun réitigh a aimsiú i spásanna casta fadhbanna trí chinntí eolasacha a dhéanamh bunaithe ar heorastaíocht nó ar rialacha ordóige. Tá sé úsáideach go háirithe nuair nach mbíonn cuardach uileghabhálach praiticiúil mar gheall ar an spás cuardaigh mór.

Conas a oibríonn sé

1. Heuristic Meastóireacht: Déanann an t-algartam measúnú ar gach staid sa spás fadhbanna ag baint úsáide as heuristic feidhm. Déanann an fheidhm seo meastachán ar "gealltanas" gach stáit i dtéarmaí a chóngaraí atá sé don spriocstát.
2. Straitéis Chuardaigh: Roghnaíonn an algartam an stát is bisiúla bunaithe ar an heuristic meastóireacht. Úsáideann sé straitéis chuardaigh cosúil le Best-First Cuardach, Cuardach A*, nó Greedy Cuardach.
3. Leathnú Stáit: Déantar an stát roghnaithe a leathnú trí na stáit chomharsanachta a ghiniúint. Is iarrthóirí ionchasacha iad seo don chéad chéim eile.
4. Déan: Déantar an próiseas arís agus arís eile, ag roghnú agus ag leathnú stáit go dtí go bhfaightear an sprioc-staid nó go gcomhlíontar coinníoll foirceanta.

Sampla: Fadhb Díoltóra Taistil(TSP)

Smaoinigh ar Fhadhb an Díoltóra Taistil, áit a gcaithfidh díoltóir cuairt a thabhairt ar shraith cathracha agus filleadh ar an gcathair thosaigh agus an fad iomlán a thaistiltear a íoslaghdú. D’fhéadfadh cur heuristic chuige a bheith san Algartam Comharsanachta is gaire:

1. Tosaigh ag cathair randamach.
2. Ag gach céim, roghnaigh an chathair is gaire gan cuairt mar an chéad cheann scríbe eile.
3. Déan arís go dtí go dtugtar cuairt ar na cathracha go léir, ansin ar ais go dtí an chathair tosaigh.

Sampla Cód i 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;  
}  

Sa sampla seo, úsáidtear an Algartam Comharsanachta is gaire chun Fadhb an Díoltóra Taistil a réiteach. Is heuristic cur chuige é a roghnaíonn an chathair is gaire gan cuairt ag gach céim, agus mar thoradh air sin tá réiteach atá gar don bharrmhaith.