Heuristic Algoritma Carian dalam C++- Penjelasan, Contoh dan Kod

Heuristic Carian ialah pendekatan algoritma yang berkuasa yang digunakan untuk mencari penyelesaian dalam ruang masalah yang kompleks dengan membuat keputusan termaklum berdasarkan heuristik atau peraturan praktikal. Ia amat berguna apabila carian menyeluruh tidak praktikal kerana ruang carian yang besar.

Bagaimana ia berfungsi

1. Heuristic Penilaian: Algoritma menilai setiap keadaan dalam ruang masalah menggunakan heuristic fungsi. Fungsi ini menganggarkan "janji" setiap negeri dari segi kedekatannya dengan keadaan matlamat.
2. Strategi Carian: Algoritma memilih keadaan yang paling menjanjikan berdasarkan heuristic penilaian. Ia menggunakan strategi carian seperti Best-First Carian, Carian A* atau Greedy Carian.
3. Peluasan Negeri: Negeri yang dipilih dikembangkan dengan menjana negeri jirannya. Ini adalah calon yang berpotensi untuk langkah seterusnya.
4. Ulang: Proses diulang secara berulang, memilih dan mengembangkan keadaan sehingga keadaan matlamat ditemui atau syarat penamatan dipenuhi.

Contoh: Masalah Jurujual Perjalanan(TSP)

Pertimbangkan Masalah Jurujual Perjalanan, di mana jurujual perlu melawat satu set bandar dan kembali ke bandar permulaan sambil meminimumkan jumlah jarak perjalanan. Pendekatan heuristic boleh menjadi Algoritma Jiran Terdekat:

1. Mulakan di bandar rawak.
2. Pada setiap langkah, pilih bandar terdekat yang belum dikunjungi sebagai destinasi seterusnya.
3. Ulang sehingga semua bandar dilawati, kemudian kembali ke bandar permulaan.

Contoh Kod dalam 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 Masalah Jurujual Perjalanan. Ini adalah heuristic pendekatan yang memilih bandar terdekat yang belum dilawati pada setiap langkah, menghasilkan penyelesaian yang selalunya hampir optimum.