ღრუბლოვანი ძიების (Cloud Search) ალგორითმი C++-ში- ახსნა, მაგალითი და კოდი

ღრუბლოვანი ძიების ალგორითმი არის ძიების მეთოდი, რომელიც მოიცავს შემთხვევითი გადაწყვეტილებების დიდი ნაკრების გენერირებას, რომელსაც ხშირად „ღრუბელს“ უწოდებენ და შემდეგ ამ ნაკრების ფარგლებში საუკეთესო გადაწყვეტილებების ძიებას. ეს მიდგომა ჩვეულებრივ გამოიყენება რთული პრობლემების მიახლოებითი გადაწყვეტილებების მოსაძებნად, როდესაც არ არსებობს კონკრეტული სახელმძღვანელო.

Როგორ მუშაობს

1. ღრუბლის ინიციალიზაცია: შექმენით შემთხვევითი გადაწყვეტილებების დიდი ნაკრები(ღრუბელი).
2. შეფასება: შეაფასეთ ღრუბელში თითოეული გადაწყვეტის ხარისხი ობიექტური ფუნქციის ან შეფასების კრიტერიუმების საფუძველზე.
3. შერჩევა: შეარჩიეთ საუკეთესო გადაწყვეტილებების ქვეჯგუფი ღრუბლიდან, ალბათობის ან შერჩევის კრიტერიუმების საფუძველზე.
4. გაუმჯობესება: გააუმჯობესეთ გადაწყვეტილებების ხარისხი ღრუბელში ტრანსფორმაციების ან ოპტიმიზაციის გამოყენებით.
5. გამეორება: გაიმეორეთ ნაბიჯები 2-დან 4-მდე, სანამ არ მიიღწევა დამაკმაყოფილებელი შედეგი ან არ მიიღწევა გამეორებების წინასწარ განსაზღვრული რაოდენობა.

მაგალითი: Cloud Search მოგზაური გამყიდველის პრობლემისთვის

განვიხილოთ მოგზაური გამყიდველის პრობლემა(TSP), სადაც მიზანია იპოვოთ უმოკლეს ჰამილტონის ციკლი, რომელიც სტუმრობს ყველა ქალაქს. Cloud Search მეთოდს შეუძლია ჰამილტონის შემთხვევითი ციკლების დიდი რაოდენობის გენერირება, შემდეგ კი ყველაზე დაბალი ღირებულების მქონე ციკლის შერჩევა.

კოდის მაგალითი 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-ის გადასაჭრელად. ჩვენ ვქმნით შემთხვევითი ჰამილტონის ციკლების დიდ რაოდენობას ქალაქების შემთხვევით არევით, შემდეგ გამოვთვალოთ თითოეული ციკლის ღირებულება და ვირჩევთ ციკლს ყველაზე დაბალი ღირებულებით.