Pilvihaun (Cloud Search) algoritmi C++:ssa- selitys, esimerkki ja koodi

Cloud Search -algoritmi on hakumenetelmä, jossa luodaan suuri joukko satunnaisia ​​ratkaisuja, joita kutsutaan usein "pilviksi", ja sitten etsitään parhaita ratkaisuja tästä sarjasta. Tätä lähestymistapaa käytetään yleisesti likimääräisten ratkaisujen löytämiseen monimutkaisiin ongelmiin, kun erityisiä ohjeita ei ole saatavilla.

Kuinka se toimii

1. Pilven alustus: Luo suuri joukko satunnaisia ​​ratkaisuja(pilvi).
2. Arviointi: Arvioi jokaisen pilven ratkaisun laatu tavoitefunktion tai arviointikriteerien perusteella.
3. Valinta: Valitse pilvestä joukko parhaita ratkaisuja todennäköisyyksien tai valintakriteerien perusteella.
4. Parantaminen: Paranna ratkaisujen laatua pilvessä ottamalla käyttöön muunnoksia tai optimointeja.
5. Iterointi: Toista vaiheita 2–4, kunnes saavutetaan tyydyttävä tulos tai saavutetaan ennalta määritetty iteraatioiden määrä.

Esimerkki: Cloud Search for the Travelling Salesman -ongelma

Harkitse Travelling Salesman -ongelmaa(TSP), jossa tavoitteena on löytää lyhin Hamiltonin sykli, joka vierailee kaikissa kaupungeissa. Cloud Search -menetelmällä voidaan luoda suuri määrä satunnaisia ​​Hamiltonin syklejä ja valita sitten sykli, jonka kustannukset ovat edullisimmat.

Esimerkki koodista C++:ssa

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

Tässä esimerkissä käytämme Cloud Search -menetelmää TSP:n ratkaisemiseen. Luomme suuren määrän satunnaisia ​​Hamiltonin jaksoja sekoittamalla kaupungit satunnaisesti, laskemme sitten kunkin syklin kustannukset ja valitsemme syklin, jolla on alhaisin kustannuksin.