(Greedy Search) C++ میں لالچی تلاش کا الگورتھم- وضاحت، مثال اور کوڈ

لالچی تلاش الگورتھم ایک مسئلہ حل کرنے کا طریقہ ہے جو فیصلے کے طویل مدتی اثرات پر غور کیے بغیر ہمیشہ ہر قدم پر بہترین دستیاب آپشن کا انتخاب کرتا ہے۔ اگرچہ یہ عالمی سطح پر بہترین حل تلاش کرنے کی ضمانت نہیں دیتا، لیکن یہ طریقہ اکثر تیزی سے کام کرتا ہے اور اس پر عمل درآمد کرنا سیدھا ہے۔

یہ کیسے کام کرتا ہے

1. ابتداء: خالی یا ابتدائی حل کے ساتھ شروع کریں۔
2. مقامی بہترین انتخاب: ہر قدم پر، مقصدی فنکشن یا متعین معیار کی بنیاد پر مقامی طور پر بہترین انتخاب کا انتخاب کریں۔
3. انتخاب کا اطلاق کریں: موجودہ حل پر بہترین انتخاب کا اطلاق کریں۔
4. دہرائیں: اقدامات 2 سے 4 تک دہرائیں جب تک کہ کوئی بہتر مقامی انتخاب نہ کیا جائے۔

مثال: Knapsack Problem

غور کریں Knapsack Problem ، جہاں ہمارے پاس زیادہ سے زیادہ وزن کے ساتھ ایک نیپ سیک اور وزن اور قدروں والی اشیاء کی فہرست ہے۔ مقصد یہ ہے کہ نیپ سیک میں کل قیمت کو زیادہ سے زیادہ کرنے کے لیے آئٹمز کا انتخاب کیا جائے۔ اس مسئلے کے لیے ایک لالچی تلاش کا طریقہ یہ ہے کہ سب سے زیادہ قدر سے وزن کے تناسب کی بنیاد پر اشیاء کا انتخاب کیا جائے۔

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

اس مثال میں، ہم حل کرنے کے لیے لالچی تلاش کا طریقہ استعمال کرتے ہیں Knapsack Problem ۔ ہم نزولی قدر سے وزن کے تناسب کی بنیاد پر آئٹمز کو ترتیب دیتے ہیں اور اعلیٰ ترین تناسب کے ساتھ آئٹمز منتخب کرتے ہیں جو اب بھی نیپ سیک کے وزن کی حد میں فٹ ہوں۔