Algoritem iskanja v oblaku (Cloud Search) v C++ – razlaga, primer in koda

Algoritem iskanja v oblaku je metoda iskanja, ki vključuje generiranje velikega niza naključnih rešitev, ki se pogosto imenujejo "oblak", in nato iskanje najboljših rešitev znotraj tega niza. Ta pristop se običajno uporablja za iskanje približnih rešitev za zapletene težave, kadar ni na voljo posebnih navodil.

Kako deluje

1. Inicializacija oblaka: ustvarite velik nabor naključnih rešitev(oblak).
2. Vrednotenje: Ocenite kakovost posamezne rešitve v oblaku na podlagi ciljne funkcije ali kriterijev vrednotenja.
3. Izbira: izberite podmnožico najboljših rešitev iz oblaka na podlagi verjetnosti ali izbirnih meril.
4. Izboljšava: Izboljšajte kakovost rešitev v oblaku z uporabo transformacij ali optimizacij.
5. Ponovitev: Ponavljajte korake od 2 do 4, dokler ne dosežete zadovoljivega rezultata ali dokler ne dosežete vnaprej določenega števila ponovitev.

Primer: iskanje v oblaku za problem trgovskega potnika

Razmislite o problemu trgovskega potnika(TSP), kjer je cilj najti najkrajši Hamiltonov cikel, ki obišče vsa mesta. Metoda Cloud Search lahko ustvari veliko število naključnih Hamiltonovih ciklov, nato pa izbere cikel z najnižjo ceno.

Primer kode v 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;  
}  

V tem primeru za rešitev TSP uporabljamo metodo Cloud Search. Generiramo veliko število naključnih Hamiltonovih ciklov z naključnim premešanjem mest, nato izračunamo stroške za vsak cikel in izberemo cikel z najnižjimi stroški.