Algoritma Carian Tamak (Greedy Search) dalam C++- Penjelasan, Contoh dan Kod

Algoritma Greedy Search ialah pendekatan penyelesaian masalah yang sentiasa memilih pilihan terbaik yang tersedia pada setiap langkah tanpa mengambil kira kesan jangka panjang keputusan tersebut. Walaupun ia tidak menjamin mencari penyelesaian yang optimum secara global, kaedah ini selalunya berfungsi dengan cepat dan mudah untuk dilaksanakan.

Bagaimana ia berfungsi

1. Permulaan: Mulakan dengan penyelesaian kosong atau awal.
2. Pilihan Optimum Tempatan: Pada setiap langkah, pilih pilihan optimum setempat berdasarkan fungsi objektif atau kriteria yang ditentukan.
3. Guna Pilihan: Guna pilihan optimum pada penyelesaian semasa.
4. Ulang: Ulangi langkah 2 hingga 4 sehingga tiada pilihan tempatan yang lebih baik boleh dibuat.

Contoh: Knapsack Problem

Pertimbangkan Knapsack Problem, di mana kami mempunyai ransel dengan berat maksimum dan senarai item dengan berat dan nilai. Matlamatnya adalah untuk memilih item untuk memaksimumkan jumlah nilai dalam ransel. Pendekatan Greedy Search untuk masalah ini ialah memilih item berdasarkan nisbah nilai-ke-berat yang tertinggi.

Contoh Kod dalam C++

#include <iostream>  
#include <vector>  
#include <algorithm>  
  
struct Item {  
    int weight;  
    int value;  
};  
  
bool compare(Item a, Item b) {  
    double ratioA =(double)a.value / a.weight;  
    double ratioB =(double)b.value / b.weight;  
    return ratioA > ratioB;  
}  
  
double greedyKnapsack(int maxWeight, std::vector<Item>& items) {  
    double totalValue = 0.0;  
  
    std::sort(items.begin(), items.end(), compare);  
  
    for(const Item& item: items) {  
        if(maxWeight >= item.weight) {  
            totalValue += item.value;  
            maxWeight -= item.weight;  
        } else {  
            totalValue +=(double)maxWeight / item.weight * item.value;  
            break;  
        }  
    }  
  
    return totalValue;  
}  
  
int main() {  
    int maxWeight = 10;  
    std::vector<Item> items = {{2, 6}, {5, 12}, {3, 8}, {7, 14}, {4, 10}};  
    double maxValue = greedyKnapsack(maxWeight, items);  
  
    std::cout << "Max value in knapsack: " << maxValue << std::endl;  
  
    return 0;  
}  

Dalam contoh ini, kami menggunakan pendekatan Greedy Search untuk menyelesaikan Knapsack Problem. Kami mengisih item berdasarkan nisbah nilai kepada berat yang menurun dan memilih item dengan nisbah tertinggi yang masih muat dalam had berat ransel.