close

C++의 클라우드 검색 (Cloud Search) 알고리즘- 설명, 예제 및 코드

Cloud Search 알고리즘은 종종 "클라우드"라고 하는 대규모 임의 솔루션 집합을 생성한 다음 이 집합 내에서 최상의 솔루션을 검색하는 검색 방법입니다. 이 접근 방식은 특정 지침을 사용할 수 없을 때 복잡한 문제에 대한 대략적인 솔루션을 찾는 데 일반적으로 사용됩니다.

작동 방식

  1. 클라우드 초기화: 대규모 무작위 솔루션 세트(클라우드)를 생성합니다.
  2. 평가: 목적 함수 또는 평가 기준에 따라 클라우드에 있는 각 솔루션의 품질을 평가합니다.
  3. 선택: 확률 또는 선택 기준에 따라 클라우드에서 최상의 솔루션 하위 집합을 선택합니다.
  4. 개선: 변환 또는 최적화를 적용하여 클라우드에서 솔루션의 품질을 개선합니다.
  5. 반복: 만족스러운 결과를 얻거나 미리 정의된 반복 횟수에 도달할 때까지 2~4단계를 반복합니다.

예: 외판원 문제에 대한 클라우드 검색

모든 도시를 방문하는 가장 짧은 Hamiltonian 주기를 찾는 것이 목표인 여행하는 외판원 문제(TSP)를 고려하십시오. Cloud Search 방법은 임의의 Hamiltonian 주기를 많이 생성한 다음 비용이 가장 낮은 주기를 선택할 수 있습니다.

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

이 예제에서는 Cloud Search 방법을 사용하여 TSP를 해결합니다. 무작위로 도시를 섞음으로써 많은 수의 무작위 해밀턴 사이클을 생성한 다음 각 사이클의 비용을 계산하고 비용이 가장 낮은 사이클을 선택합니다.