Algorithm ya Utafutaji wa Uchoyo (Greedy Search) katika C++- Maelezo, Mfano na Msimbo

Kanuni ya Utafutaji wa Tamaa ni mbinu ya kutatua matatizo ambayo kila mara huchagua chaguo bora zaidi katika kila hatua bila kuzingatia athari ya muda mrefu ya uamuzi. Ingawa haitoi hakikisho la kupata suluhisho bora zaidi ulimwenguni, njia hii mara nyingi hufanya kazi haraka na ni rahisi kutekeleza.

Inavyofanya kazi

1. Uanzishaji: Anza na suluhu tupu au la awali.
2. Chaguo Bora la Ndani: Katika kila hatua, chagua chaguo bora zaidi la ndani kulingana na utendakazi lengwa au vigezo vilivyobainishwa.
3. Tumia Chaguo: Tumia chaguo bora kwa suluhisho la sasa.
4. Rudia: Rudia kupitia hatua ya 2 hadi 4 hadi hakuna chaguo bora la eneo linaloweza kufanywa.

Mfano: Knapsack Problem

Fikiria Knapsack Problem, ambapo tuna knapsack na uzito wa juu na orodha ya vitu na uzito na maadili. Lengo ni kuchagua vitu ili kuongeza thamani ya jumla kwenye kifuko. Mbinu ya Utafutaji wa Tamaa kwa tatizo hili ni kuchagua bidhaa kulingana na uwiano wa juu zaidi wa thamani hadi uzani.

Mfano wa Msimbo katika 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;  
}  

Katika mfano huu, tunatumia mbinu ya Utafutaji wa Tamaa kutatua Knapsack Problem. Tunapanga vipengee kulingana na uwiano wa kushuka wa thamani hadi uzani na kuchagua vipengee vilivyo na uwiano wa juu zaidi ambao bado unafaa ndani ya kikomo cha uzito cha gunia.