Heuristic Hakualgoritmi C++:ssa- selitys, esimerkki ja koodi

Heuristic Haku on tehokas algoritminen lähestymistapa, jota käytetään ratkaisujen löytämiseen monimutkaisiin ongelmatiloihin tekemällä tietoisia päätöksiä heuristiikkaan tai nyrkkisääntöihin perustuen. Se on erityisen hyödyllinen, kun kattava haku on epäkäytännöllistä suuren hakutilan vuoksi.

Kuinka se toimii

1. Heuristic Arviointi: Algoritmi arvioi jokaisen ongelmatilan tilan funktion avulla heuristic. Tämä funktio arvioi kunkin tilan "lupaavuuden" sen lähellä tavoitetilaa.
2. Hakustrategia: Algoritmi valitsee arvioinnin perusteella lupaavimman tilan heuristic. Se käyttää hakustrategiaa, kuten Best-First Search, A* Search tai Greedy Search.
3. Tilan laajennus: Valittua tilaa laajennetaan luomalla sen naapuritilat. Nämä ovat mahdollisia ehdokkaita seuraavaan vaiheeseen.
4. Toista: Prosessi toistetaan iteratiivisesti valitsemalla ja laajentamalla tiloja, kunnes tavoitetila löytyy tai lopetusehto täyttyy.

Esimerkki: Travelling Salesman Problem(TSP)

Harkitse Travelling Salesman -ongelmaa, jossa myyjän täytyy käydä joukossa kaupunkeja ja palata lähtökaupunkiin minimoimalla kuljetun kokonaismatkan. Lähestymistapa heuristic voisi olla lähin naapuri -algoritmi:

1. Aloita sattumanvaraisesta kaupungista.
2. Valitse jokaisessa vaiheessa seuraavaksi kohteeksi lähin vierailematon kaupunki.
3. Toista, kunnes kaikki kaupungit on käyty, ja palaa sitten aloituskaupunkiin.

Esimerkki koodista C++:ssa

#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;  
}  

Tässä esimerkissä Lähin naapuri -algoritmia käytetään ratkaisemaan Travelling Salesman -ongelma. Se on heuristic lähestymistapa, joka valitsee jokaisessa vaiheessa lähimmän vierailemattoman kaupungin, mikä johtaa ratkaisuun, joka on usein lähellä optimaalista.