Algoritam pretraživanja u oblaku (Cloud Search) u C++- objašnjenje, primjer i kod

Algoritam pretraživanja u oblaku metoda je pretraživanja koja uključuje generiranje velikog skupa nasumičnih rješenja, koja se često nazivaju "oblak", a zatim traženje najboljih rješenja unutar tog skupa. Ovaj se pristup obično koristi za pronalaženje približnih rješenja za složene probleme kada nisu dostupne posebne smjernice.

Kako radi

1. Inicijalizacija oblaka: Stvorite veliki skup nasumičnih rješenja(oblak).
2. Evaluacija: Ocijenite kvalitetu svakog rješenja u oblaku na temelju funkcije cilja ili kriterija evaluacije.
3. Odabir: Odaberite podskup najboljih rješenja iz oblaka na temelju vjerojatnosti ili kriterija odabira.
4. Poboljšanje: Poboljšajte kvalitetu rješenja u oblaku primjenom transformacija ili optimizacija.
5. Ponavljanje: Ponavljajte korake 2 do 4 dok se ne postigne zadovoljavajući rezultat ili dok se ne postigne unaprijed definirani broj ponavljanja.

Primjer: Cloud Search za problem trgovačkog putnika

Razmotrimo problem trgovačkog putnika(TSP), gdje je cilj pronaći najkraći Hamiltonov ciklus koji posjećuje sve gradove. Metoda Cloud Search može generirati veliki broj slučajnih Hamiltonovih ciklusa, a zatim odabrati ciklus s najnižom cijenom.

Primjer koda u 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;  
}  

U ovom primjeru koristimo metodu Cloud Search za rješavanje TSP-a. Generiramo veliki broj nasumičnih Hamiltonovih ciklusa nasumičnim miješanjem gradova, zatim izračunavamo trošak za svaki ciklus i odabiremo ciklus s najnižim troškom.