Heuristic Cari Algoritma di C++- Penjelasan, Contoh dan Kode

Heuristic Pencarian adalah pendekatan algoritmik yang kuat yang digunakan untuk menemukan solusi dalam ruang masalah yang kompleks dengan membuat keputusan berdasarkan heuristik atau aturan praktis. Ini sangat berguna ketika pencarian lengkap tidak praktis karena ruang pencarian yang besar.

Bagaimana itu bekerja

1. Heuristic Evaluasi: Algoritme mengevaluasi setiap status dalam ruang masalah menggunakan heuristic fungsi. Fungsi ini memperkirakan "janji" dari setiap negara dalam hal kedekatannya dengan negara tujuan.
2. Strategi Pencarian: Algoritme memilih status yang paling menjanjikan berdasarkan heuristic evaluasi. Ini menggunakan strategi pencarian seperti Best-First Search, A* Search, atau Greedy Search.
3. Ekspansi Status: Status yang dipilih diperluas dengan menghasilkan status tetangganya. Ini adalah kandidat potensial untuk langkah selanjutnya.
4. Ulangi: Proses diulang secara iteratif, memilih dan memperluas status hingga status tujuan ditemukan atau kondisi terminasi terpenuhi.

Contoh: Travelling Salesman Problem(TSP)

Pertimbangkan Masalah Penjual Perjalanan, di mana seorang penjual perlu mengunjungi sekumpulan kota dan kembali ke kota awal sambil meminimalkan total jarak yang ditempuh. Suatu heuristic pendekatan bisa menjadi Algoritma Tetangga Terdekat:

1. Mulai dari kota acak.
2. Di setiap langkah, pilih kota terdekat yang belum dikunjungi sebagai tujuan selanjutnya.
3. Ulangi sampai semua kota dikunjungi, lalu kembali ke kota awal.

Contoh Kode di C++

#include <iostream>  
#include <vector>  
#include <cmath>  
#include <algorithm>  
  
struct City {  
    int x, y;  
};  
  
double distance(const City& city1, const City& city2) {  
    return std::sqrt(std::pow(city1.x- city2.x, 2) + std::pow(city1.y- city2.y, 2));  
}  
  
std::vector<int> nearestNeighbor(const std::vector<City>& cities) {  
    int numCities = cities.size();  
    std::vector<int> path(numCities);  
    std::vector<bool> visited(numCities, false);  
  
    path[0] = 0;  
    visited[0] = true;  
  
    for(int i = 1; i < numCities; ++i) {  
        int currentCity = path[i- 1];  
        double minDist = std::numeric_limits<double>::max();  
        int nextCity = -1;  
  
        for(int j = 0; j < numCities; ++j) {  
            if(!visited[j]) {  
                double dist = distance(cities[currentCity], cities[j]);  
                if(dist < minDist) {  
                    minDist = dist;  
                    nextCity = j;  
                }  
            }  
        }  
  
        path[i] = nextCity;  
        visited[nextCity] = true;  
    }  
  
    path.push_back(0); // Return to the starting city  
    return path;  
}  
  
int main() {  
    std::vector<City> cities = {{0, 0}, {1, 3}, {4, 2}, {3, 6}, {7, 1}};  
    std::vector<int> path = nearestNeighbor(cities);  
  
    std::cout << "Traveling Salesman Path: ";  
    for(int city: path) {  
        std::cout << city << ";  
    }  
    std::cout << std::endl;  
  
    return 0;  
}  

Dalam contoh ini, Algoritma Nearest Neighbor digunakan untuk menyelesaikan Travelling Salesman Problem. Ini adalah heuristic pendekatan yang memilih kota terdekat yang belum dikunjungi di setiap langkah, menghasilkan solusi yang seringkali mendekati optimal.