C++'da Açgözlü Arama (Greedy Search) Algoritması- Açıklama, Örnek ve Kod

Açgözlü Arama algoritması, kararın uzun vadeli etkisini dikkate almadan her adımda her zaman mevcut olan en iyi seçeneği seçen bir problem çözme yaklaşımıdır. Genel olarak en uygun çözümü bulmayı garanti etmese de, bu yöntem genellikle hızlı çalışır ve uygulanması kolaydır.

Nasıl çalışır

1. Başlatma: Boş veya ilk çözümle başlayın.
2. Yerel Optimal Seçim: Her adımda, amaç fonksiyonuna veya tanımlanmış kriterlere dayalı olarak yerel olarak en uygun seçimi seçin.
3. Seçimi Uygula: Mevcut çözüme en uygun seçimi uygulayın.
4. Tekrarla: Daha iyi bir yerel seçim yapılamayana kadar 2 ila 4 arasındaki adımları yineleyin.

Örnek: Knapsack Problem

Knapsack Problem Maksimum ağırlığa sahip bir sırt çantamız ve ağırlıkları ve değerleri olan öğelerin bir listesine sahip olduğumuz, düşünün. Amaç, sırt çantasındaki toplam değeri en üst düzeye çıkaracak öğeleri seçmektir. Bu problem için Açgözlü Arama yaklaşımı, öğeleri en yüksek değer-ağırlık oranına göre seçmektir.

C++'da Kod Örneği

#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;  
}  

Bu örnekte, sorunu çözmek için Greedy Search yaklaşımını kullanıyoruz Knapsack Problem. Öğeleri azalan değer-ağırlık oranına göre sıralıyoruz ve en yüksek orana sahip olan ve hala sırt çantasının ağırlık limitine uyan öğeleri seçiyoruz.