Cloud-Suchalgorithmus (Cloud Search) in C++ – Erklärung, Beispiel und Code

Der Cloud-Suchalgorithmus ist eine Suchmethode, bei der eine große Menge zufälliger Lösungen, oft als „Wolke“ bezeichnet, generiert und dann innerhalb dieser Menge nach den besten Lösungen gesucht wird. Dieser Ansatz wird häufig verwendet, um Näherungslösungen für komplexe Probleme zu finden, wenn keine spezifische Anleitung verfügbar ist.

Wie es funktioniert

1. Cloud-Initialisierung: Erstellen Sie eine große Menge zufälliger Lösungen(die Cloud).
2. Bewertung: Bewerten Sie die Qualität jeder Lösung in der Cloud anhand der Zielfunktion oder der Bewertungskriterien.
3. Auswahl: Wählen Sie anhand von Wahrscheinlichkeiten oder Auswahlkriterien eine Teilmenge der besten Lösungen aus der Cloud aus.
4. Verbesserung: Verbessern Sie die Qualität von Lösungen in der Cloud durch die Anwendung von Transformationen oder Optimierungen.
5. Iteration: Wiederholen Sie die Schritte 2 bis 4, bis ein zufriedenstellendes Ergebnis erzielt wird oder eine vordefinierte Anzahl von Iterationen erreicht ist.

Beispiel: Cloud-Suche für das Problem des Handlungsreisenden

Betrachten Sie das Traveling Salesman Problem(TSP), bei dem das Ziel darin besteht, den kürzesten Hamilton-Zyklus zu finden, der alle Städte besucht. Die Cloud Search-Methode kann eine große Anzahl zufälliger Hamilton-Zyklen generieren und dann den Zyklus mit den niedrigsten Kosten auswählen.

Codebeispiel in 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;  
}  

In diesem Beispiel verwenden wir die Cloud Search-Methode, um den TSP zu lösen. Wir erzeugen eine große Anzahl zufälliger Hamilton-Zyklen, indem wir die Städte zufällig mischen, berechnen dann die Kosten für jeden Zyklus und wählen den Zyklus mit den niedrigsten Kosten aus.