Algoritma Carian Awan (Cloud Search) dalam C++- Penjelasan, Contoh dan Kod

Algoritma Carian Awan ialah kaedah carian yang melibatkan penjanaan set besar penyelesaian rawak, sering dirujuk sebagai "awan", dan kemudian mencari penyelesaian terbaik dalam set ini. Pendekatan ini biasanya digunakan untuk mencari penyelesaian anggaran bagi masalah yang kompleks apabila tiada panduan khusus tersedia.

Bagaimana ia berfungsi

1. Permulaan Awan: Cipta satu set besar penyelesaian rawak(awan).
2. Penilaian: Nilaikan kualiti setiap penyelesaian dalam awan berdasarkan fungsi objektif atau kriteria penilaian.
3. Pemilihan: Pilih subset penyelesaian terbaik daripada awan berdasarkan kebarangkalian atau kriteria pemilihan.
4. Penambahbaikan: Tingkatkan kualiti penyelesaian dalam awan dengan menggunakan transformasi atau pengoptimuman.
5. Lelaran: Ulang langkah 2 hingga 4 sehingga hasil yang memuaskan dicapai atau bilangan lelaran yang telah ditetapkan dicapai.

Contoh: Carian Awan untuk Masalah Jurujual Perjalanan

Pertimbangkan Masalah Jurujual Perjalanan(TSP), di mana matlamatnya adalah untuk mencari kitaran Hamiltonian terpendek yang melawat semua bandar. Kaedah Carian Awan boleh menjana sejumlah besar kitaran Hamiltonian rawak, kemudian pilih kitaran dengan kos terendah.

Contoh Kod dalam 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;  
}  

Dalam contoh ini, kami menggunakan kaedah Carian Awan untuk menyelesaikan TSP. Kami menjana sejumlah besar kitaran Hamiltonian rawak dengan merombak bandar secara rawak, kemudian mengira kos untuk setiap kitaran dan memilih kitaran dengan kos terendah.