Heuristic Tafuta Algorithm katika C++- Maelezo, Mfano na Kanuni

Heuristic Utafutaji ni mkabala wenye nguvu wa algoriti unaotumiwa kupata suluhu katika nafasi changamano za matatizo kwa kufanya maamuzi sahihi kulingana na utabiri au sheria za dole gumba. Ni muhimu hasa wakati utafutaji wa kina hauwezekani kwa sababu ya nafasi kubwa ya utafutaji.

Inavyofanya kazi

1. Heuristic Tathmini: Kanuni hutathmini kila hali katika nafasi ya tatizo kwa kutumia heuristic kipengele cha kukokotoa. Chaguo hili la kukokotoa linakadiria "kuahidi" kwa kila jimbo kulingana na ukaribu wake na hali ya lengo.
2. Mkakati wa Utafutaji: Algorithm huchagua hali ya kuahidi zaidi kulingana na heuristic tathmini. Inatumia mbinu ya utafutaji kama vile Best-First Utafutaji, Utafutaji wa A* au Greedy Utafutaji.
3. Upanuzi wa Jimbo: Jimbo lililochaguliwa linapanuliwa kwa kuzalisha majimbo jirani. Hawa ni wagombea wanaotarajiwa kwa hatua inayofuata.
4. Rudia: Mchakato unarudiwa mara kwa mara, kuchagua na kupanua majimbo hadi hali ya lengo ipatikane au sharti la kukomesha litimizwe.

Mfano: Tatizo la Wafanyabiashara wa Kusafiri(TSP)

Fikiria Tatizo la Muuzaji Msafiri, ambapo muuzaji anahitaji kutembelea seti ya miji na kurudi kwenye jiji la kuanzia huku akipunguza umbali wote uliosafiri. Njia heuristic inaweza kuwa Algorithm ya Karibu ya Jirani:

1. Anza katika jiji lisilo la kawaida.
2. Katika kila hatua, chagua jiji la karibu ambalo halijatembelewa kama eneo linalofuata.
3. Rudia hadi miji yote itembelewe, kisha urudi kwenye jiji la kuanzia.

Mfano wa Msimbo katika 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;  
}  

Katika mfano huu, Algorithm ya Karibu ya Jirani inatumiwa kutatua Tatizo la Muuzaji Anayesafiri. Ni heuristic mbinu inayochagua jiji la karibu ambalo halijatembelewa kwa kila hatua, na kusababisha suluhisho ambalo mara nyingi huwa karibu na mojawapo.