Paieškos debesyje (Cloud Search) algoritmas C++ – paaiškinimas, pavyzdys ir kodas

Cloud Search algoritmas yra paieškos metodas, kurio metu generuojamas didelis atsitiktinių sprendimų rinkinys, dažnai vadinamas „debesimi“, o tada ieškoma geriausių sprendimų šiame rinkinyje. Šis metodas dažniausiai naudojamas ieškant apytikslių sudėtingų problemų sprendimų, kai nėra konkrečių nurodymų.

Kaip tai veikia

1. Debesų inicijavimas: sukurkite didelį atsitiktinių sprendimų rinkinį(debesį).
2. Įvertinimas: įvertinkite kiekvieno debesyje esančio sprendimo kokybę pagal tikslo funkciją arba vertinimo kriterijus.
3. Pasirinkimas: iš debesies pasirinkite geriausių sprendimų poaibį pagal tikimybes arba atrankos kriterijus.
4. Tobulinimas: pagerinkite sprendimų kokybę debesyje taikydami transformacijas arba optimizavimus.
5. Iteracija: kartokite 2–4 veiksmus, kol bus pasiektas patenkinamas rezultatas arba iš anksto nustatytas pakartojimų skaičius.

Pavyzdys: Keliaujančio pardavėjo problema paieška debesyje

Apsvarstykite keliaujančio pardavėjo problemą(TSP), kurios tikslas yra rasti trumpiausią Hamiltono ciklą, aplankantį visus miestus. Cloud Search metodas gali sugeneruoti daug atsitiktinių Hamiltono ciklų, tada pasirinkti ciklą su mažiausia kaina.

Kodo pavyzdys 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;  
}  

Šiame pavyzdyje mes naudojame debesies paieškos metodą, kad išspręstume TSP. Sugeneruojame daug atsitiktinių Hamiltono ciklų, atsitiktinai sumaišydami miestus, tada apskaičiuojame kiekvieno ciklo kainą ir pasirenkame ciklą su mažiausia kaina.