خوارزمية البحث الجشع (Greedy Search) في C ++- شرح ومثال ورمز

تعد خوارزمية البحث الجشع طريقة لحل المشكلات تختار دائمًا أفضل خيار متاح في كل خطوة دون مراعاة التأثير طويل المدى للقرار. على الرغم من أنها لا تضمن العثور على الحل الأمثل عالميًا ، إلا أن هذه الطريقة غالبًا ما تعمل بسرعة ويسهل تنفيذها.

كيف تعمل

1. التهيئة: ابدأ بحل فارغ أو مبدئي.
2. Local Optimal Choice: في كل خطوة ، اختر الخيار الأمثل محليًا بناءً على الوظيفة الموضوعية أو المعايير المحددة.
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. نقوم بفرز العناصر بناءً على نسبة القيمة إلى الوزن التنازلي ونختار العناصر ذات النسبة الأعلى التي لا تزال تتناسب مع حد وزن الحقيبة على الظهر.