Algoritmi i Kërkimit në renë kompjuterike (Cloud Search) në C++- Shpjegim, Shembull dhe Kodi

Algoritmi i Kërkimit në Re është një metodë kërkimi që përfshin gjenerimin e një grupi të madh zgjidhjesh të rastësishme, shpesh të referuara si "cloud" dhe më pas kërkimin e zgjidhjeve më të mira brenda këtij grupi. Kjo qasje përdoret zakonisht për të gjetur zgjidhje të përafërta për probleme komplekse kur nuk ka udhëzim specifik.

Si punon

1. Inicializimi i resë kompjuterike: Krijo një grup të madh zgjidhjesh të rastësishme(cloud).
2. Vlerësimi: Vlerësoni cilësinë e secilës zgjidhje në cloud bazuar në funksionin objektiv ose kriteret e vlerësimit.
3. Përzgjedhja: Zgjidhni një nëngrup të zgjidhjeve më të mira nga cloud bazuar në probabilitetet ose kriteret e përzgjedhjes.
4. Përmirësimi: Përmirësoni cilësinë e zgjidhjeve në cloud duke aplikuar transformime ose optimizime.
5. Përsëritja: Përsëritni hapat 2 deri në 4 derisa të arrihet një rezultat i kënaqshëm ose të arrihet një numër i paracaktuar përsëritjesh.

Shembull: Kërkimi në renë kompjuterike për problemin e shitësit udhëtues

Merrni parasysh problemin e shitësit udhëtues(TSP), ku qëllimi është të gjeni ciklin më të shkurtër Hamiltonian që viziton të gjitha qytetet. Metoda e Kërkimit në renë kompjuterike mund të gjenerojë një numër të madh ciklesh të rastësishme Hamiltoniane, më pas të zgjedhë ciklin me koston më të ulët.

Shembull kodi në C++

#include <iostream>  
#include <vector>  
#include <algorithm>  
#include <ctime>  
#include <cstdlib>  
  
struct City {  
    int x;  
    int y;  
};  
  
double calculateDistance(const City& city1, const City& city2) {  
    return std::sqrt((city1.x- city2.x)*(city1.x- city2.x) +(city1.y- city2.y)*(city1.y- city2.y));  
}  
  
double cloudSearchTSP(std::vector<City>& cities, int maxIterations) {  
    int numCities = cities.size();  
    double bestDistance = std::numeric_limits<double>::max();  
  
    srand(time(0));  
  
    for(int i = 0; i < maxIterations; ++i) {  
        std::random_shuffle(cities.begin(), cities.end());  
  
        double totalDistance = 0.0;  
        for(int j = 0; j < numCities- 1; ++j) {  
            totalDistance += calculateDistance(cities[j], cities[j + 1]);  
        }  
        totalDistance += calculateDistance(cities[numCities- 1], cities[0]);  
  
        bestDistance = std::min(bestDistance, totalDistance);  
    }  
  
    return bestDistance;  
}  
  
int main() {  
    std::vector<City> cities = {{0, 0}, {1, 2}, {3, 1}, {4, 3}, {2, 4}};  
    int maxIterations = 1000;  
    double shortestDistance = cloudSearchTSP(cities, maxIterations);  
  
    std::cout << "Shortest distance in TSP: " << shortestDistance << std::endl;  
  
    return 0;  
}  

Në këtë shembull, ne përdorim metodën Cloud Search për të zgjidhur TSP. Ne gjenerojmë një numër të madh ciklesh të rastësishme Hamiltoniane duke i përzier qytetet në mënyrë të rastësishme, më pas llogarisim koston për çdo cikël dhe zgjedhim ciklin me koston më të ulët.