مشكلة حقيبة الظهر الجزئية: خوارزمية جشعة مع مثال

ما هي استراتيجية الجشع؟

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

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

تحلّ الاستراتيجيات الجشعة مسائل التحسين التوافقي من خلال بناء حلٍّ واحدٍ (Ai) في كل خطوة. في كل خطوة، يتم اختيار (Ai) على النحو الأمثل في ظل القيود الحالية، ويتم تقليص المسألة إلى مسألة فرعية أصغر.

يجب أن تتوافر خاصيتان لكي تكون الطريقة الجشعة صحيحة:

1. خاصية الاختيار الجشع: يؤدي الوصول إلى الحل الأمثل المحلي في كل خطوة إلى الوصول إلى الحل الأمثل العالمي. يعتمد الاختيار على القرارات السابقة وليس على القرارات المستقبلية.
2. البنية الفرعية المثلى: يحتوي الحل الأمثل للمشكلة بأكملها على الحلول المثلى لمشكلاتها الفرعية.

تحتوي الخوارزمية الجشعة على خمسة مكونات:

1. مجموعة مرشحة يتم بناء الحلول منها.
2. دالة اختيار تقوم بانتقاء أفضل مرشح تالٍ.
3. دالة جدوى تتحقق مما إذا كان بإمكان المرشح توسيع الحل الجزئي الحالي.
4. دالة هدف تُقيّم حلاً كاملاً أو جزئياً.
5. دالة تقييم تشير إلى اكتمال الحل.

فكرة الجشع واحد

يقوم الشخص الجشع بفرز الطرود حسب قيمتها فقط:

• قم بفرز الطرود بترتيب تنازلي حسب قيمتها.
• قم بجولة على القائمة المصنفة وأضف كل طرد إلى حقيبة الظهر إذا كانت السعة المتبقية تسمح بذلك.

لا تُعطي هذه القاعدة دائمًا الإجابة المثلى. مثال مضاد:

• المعلمات: ن = 3، م = 19.
• العبوات: {i = 1; W = 14; V = 20}، {i = 2; W = 6; V = 16}، {i = 3; W = 10; V = 8} — قيمة عالية ولكن وزن مرتفع أيضًا.
• يختار الشخص الجشع الحزمة رقم 1 بقيمة إجمالية قدرها 20، بينما يصل الاختيار الأمثل (الحزمة 2، الحزمة 3) إلى 24.

فكرة الجشع اثنين

يقوم "جريدي تو" بفرز الطرود حسب الوزن فقط:

• قم بفرز الطرود بترتيب تصاعدي حسب الوزن.
• قم بجولة على القائمة المصنفة وأضف كل طرد إلى حقيبة الظهر إذا كانت السعة المتبقية تسمح بذلك.

هذه القاعدة أيضاً ليست مثالية. مثال مضاد:

• المعلمات: ن = 3، م = 11.
• العبوات: {i = 1; W = 5; V = 10}، {i = 2; W = 6; V = 16}، {i = 3; W = 10; V = 28} — خفيفة الوزن ولكن ذات قيمة منخفضة.
• الخياران الجشعان (الحزمة 1، الحزمة 2) بقيمة إجمالية 26، بينما يصل الخيار الأمثل (الحزمة 3) إلى 28.

فكرة الجشع الثلاثة

تُعالج خوارزمية "الجشع الثلاثي" كلا العيبين من خلال دمج القيمة والوزن في مفتاح تصنيف واحد. وهي الطريقة القياسية لحل مسألة حقيبة الظهر الجزئية.

• احسب تكلفة الوحدة V[i] / W[i] لكل عبوة.
• قم بفرز الطرود بترتيب تنازلي حسب تكلفة الوحدة.
• قم بمراجعة القائمة المصنفة وأضف كل طرد إذا كانت السعة المتبقية تسمح بذلك.

يقوم برنامج Greedy Three بالفرز حسب تكلفة الوحدة V[i] / W[i]

فكرة: احسب نسبة القيمة إلى الوزن V[i] / W[i] لكل حزمة، ورتبها بترتيب تنازلي، وخذ أكبر نسبة متاحة أولاً حتى تمتلئ حقيبة الظهر.

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

خطوات الخوارزمية

بالنسبة لمتغير التفرع والتقييد 0/1، فإن قائمة تكلفة الوحدة المرتبة تقود شجرة البحث:

• الخطوة 1 : تمثل العقدة الجذرية حقيبة ظهر فارغة. القيمة الإجمالية = 0. الحد الأعلى = م × أقصى تكلفة للوحدة.
• الخطوة 2 : قم بتفرع الجذر حسب عدد نسخ الحزمة ذات النسبة الأكبر التي يمكن استيعابها. لكل فرع، أعد حساب القيمة الإجمالية، والسعة المتبقية M، والحد الأعلى.
• الخطوة 3 : قم بتوسيع الطفل ذي الحد الأعلى الأكبر أولاً، على أمل إيجاد حل قوي بسرعة.
• الخطوة 4 : قم بحذف أي عقدة لا يكون حدها الأعلى أفضل من أفضل حل كامل حالي.
• الخطوة 5 : عندما يتم توسيع كل عقدة أو تقليمها، يكون الحل الكامل الأفضل الحالي هو الحل الأمثل.

الشفرة الزائفة لخوارزمية حقيبة الظهر الجزئية الجشعة البحتة:

Fractional Knapsack (Array W, Array V, int M)
1. for i <- 1 to size(V)
2.     cost[i] <- V[i] / W[i]
3. Sort-Descending(cost)
4. total <- 0
5. i <- 1
6. while (i <= size(V) and M > 0)
7.     if W[i] <= M
8.         M <- M - W[i]
9.         total <- total + V[i]
10.        i <- i + 1
11.    else
12.        total <- total + V[i] * (M / W[i])
13.        M <- 0

مدى تعقيد الخوارزمية:

• باستخدام فرز بسيط (اختيار أو فرز فقاعي): O(n²).
• باستخدام الفرز السريع أو فرز الدمج: O(n log n)، تهيمن عليه خطوة الفرز.

Java Code للثلاثة الجشعين

تحديد KnapsackPackage فئة ذات وزن وقيمة وتكلفة مشتقة (نسبة القيمة إلى الوزن المستخدمة في الفرز):

public class KnapsackPackage {

    private double weight;
    private double value;
    private Double cost;

    public KnapsackPackage(double weight, double value) {
        super();
        this.weight = weight;
        this.value = value;
        this.cost = Double.valueOf(value / weight);
    }

    public double getWeight() { return weight; }

    public double getValue() { return value; }

    public Double getCost()  { return cost; }
}

ثم أنشئ الدالة التي تُنفذ خوارزمية "الثلاثة الجشعين":

public void knapsackGreProc(int W[], int V[], int M, int n) {
    KnapsackPackage[] packs = new KnapsackPackage[n];
    for (int i = 0; i < n; i++) {
        packs[i] = new KnapsackPackage(W[i], V[i]);
    }

    Arrays.sort(packs, new Comparator<KnapsackPackage>() {
        @Override
        public int compare(KnapsackPackage a, KnapsackPackage b) {
            return b.getCost().compareTo(a.getCost());
        }
    });

    double remain = M;
    double result = 0d;

    for (int i = 0; i < n && remain > 0; i++) {
        if (packs[i].getWeight() <= remain) {
            remain -= packs[i].getWeight();
            result += packs[i].getValue();
            System.out.println("Pack " + i + " - Weight " + packs[i].getWeight()
                             + " - Value " + packs[i].getValue());
        } else {
            double fraction = remain / packs[i].getWeight();
            result += packs[i].getValue() * fraction;
            System.out.println("Pack " + i + " - Fraction " + fraction
                             + " - Value " + packs[i].getValue() * fraction);
            remain = 0;
        }
    }

    System.out.println("Max Value:\t" + result);
}

وظيفة knapsackGreProc() في Java

شرح الكود:

1. قم بتغليف كل مدخل في KnapsackPackage لذا يتم حساب مفتاح الفرز (نسبة V/W) مسبقًا.
2. رتبها تنازلياً حسب التكلفة.
3. خذ كل عبوة كاملة إذا كانت مناسبة.
4. خذ جزءًا صغيرًا من العبوة التالية لملء المساحة المتبقية.
5. توقف بمجرد أن تصل السعة المتبقية إلى الصفر.

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

Java برنامج تشغيل يقوم بتشغيل الخوارزمية على مثال عملي:

public void run() {
    int W[] = new int[]{15, 10, 2, 4};
    int V[] = new int[]{30, 25, 2, 6};
    int M = 37;
    int n = V.length;
    knapsackGreProc(W, V, M, n);
}

Python3 Code للثلاثة الجشعين

أولاً، حدد KnapsackPackage صف دراسي. ال __lt__ تتيح هذه الطريقة إمكانية فرزها مباشرة حسب التكلفة:

class KnapsackPackage(object):
    """Knapsack Package Data Class"""

    def __init__(self, weight, value):
        self.weight = weight
        self.value  = value
        self.cost   = value / weight

    def __lt__(self, other):
        return self.cost < other.cost

ثم قم بتنفيذ روتين حقيبة الظهر الجزئية:

class FractionalKnapsack(object):

    def knapsackGreProc(self, W, V, M, n):
        packs = [KnapsackPackage(W[i], V[i]) for i in range(n)]
        packs.sort(reverse=True)

        remain = M
        result = 0

        for i in range(n):
            if remain == 0:
                break
            if packs[i].weight <= remain:
                remain -= packs[i].weight
                result += packs[i].value
                print("Pack", i, "- Weight", packs[i].weight, "- Value", packs[i].value)
            else:
                fraction = remain / packs[i].weight
                result += packs[i].value * fraction
                print("Pack", i, "- Fraction", fraction,
                      "- Value", packs[i].value * fraction)
                remain = 0

        print("Max Value:", result)

وظيفة knapsackGreProc() في Python

ملاحظة تصحيحية: الأصلي Python عرّفت الفئة كائنًا فارغًا __init__ بدون جسد، وهو ما يرفع IndentationError. الإصدار أعلاه يزيل المُنشئ الفارغ لأنه لا حاجة إليه.

برنامج التشغيل الذي يقوم بتشغيل الخوارزمية على المثال الأول:

if __name__ == "__main__":
    W = [15, 10, 2, 4]
    V = [30, 25, 2, 6]
    M = 37
    n = 4

    proc = FractionalKnapsack()
    proc.knapsackGreProc(W, V, M, n)

C# Code للثلاثة الجشعين

تحديد KnapsackPackage صف دراسي:

using System;

namespace KnapsackProblem
{
    public class KnapsackPackage
    {
        private double weight;
        private double value;
        private double cost;

        public KnapsackPackage(double weight, double value)
        {
            this.weight = weight;
            this.value  = value;
            this.cost   = value / weight;
        }

        public double Weight { get { return weight; } }
        public double Value  { get { return value; } }
        public double Cost   { get { return cost; } }
    }
}

قم بتنفيذ خوارزمية Greedy Three مع خطوة تعبئة جزئية:

public void KnapsackGreProc(int[] W, int[] V, int M, int n)
{
    KnapsackPackage[] packs = new KnapsackPackage[n];
    for (int k = 0; k < n; k++)
        packs[k] = new KnapsackPackage(W[k], V[k]);

    Array.Sort<KnapsackPackage>(packs,
        (a, b) => b.Cost.CompareTo(a.Cost));

    double remain = M;
    double result = 0d;

    for (int i = 0; i < n && remain > 0; i++)
    {
        if (packs[i].Weight <= remain)
        {
            remain -= packs[i].Weight;
            result += packs[i].Value;
            Console.WriteLine("Pack " + i + " - Weight " + packs[i].Weight
                            + " - Value " + packs[i].Value);
        }
        else
        {
            double fraction = remain / packs[i].Weight;
            result += packs[i].Value * fraction;
            Console.WriteLine("Pack " + i + " - Fraction " + fraction
                            + " - Value " + packs[i].Value * fraction);
            remain = 0;
        }
    }

    Console.WriteLine("Max Value:\t" + result);
}

الدالة KnapsackGreProc() في لغة C#

مثال مضاد: ثلاثة جشعين على حقيبة ظهر 0/1

تُعدّ استراتيجية "الجشع الثلاثي" مثاليةً للنسخة الكسرية، ولكن في نسخة "حقيبة الظهر 0/1" (حيث لا يمكن تقسيم العناصر) يُمكن التغلب عليها. مثال مضاد:

• المعلمات: ن = 3، م = 10.
• الحزم: {i = 1; W = 7; V = 9; cost = 9/7}، {i = 2; W = 6; V = 6; cost = 1}، {i = 3; W = 4; V = 4; cost = 1}.
• يختار اللاعب الجشع ثلاثة الحزمة رقم 1 بقيمة إجمالية قدرها 9، بينما يصل الاختيار الأمثل 0/1 (الحزمة 2، الحزمة 3) إلى 10.

الدرس المستفاد: استخدم خوارزمية "الجشع الثلاثي" فقط عندما تكون الكسور مسموحة. أما بالنسبة للنسخة 0/1، فاستخدم البرمجة الديناميكية بدلا من ذلك.

تطبيقات اختبار الحقيبة الجزئية

• تحميل البضائع حيث يمكن تقسيم البضائع السائلة أو المسحوقة أو السائبة حسب الوزن.
• توزيع المحفظة الاستثمارية عبر خيارات الاستثمار التي تقبل التمويل الجزئي.
• مشاركة عرض النطاق الترددي السحابي حيث يمكن للتدفقات أن تستهلك جزءًا من الرابط.
• جدولة وحدة المعالجة المركزية في ظل نموذج تقسيم الوقت المشترك مع أحمال عمل قابلة للتقسيم.
• تخصيص موارد الذكاء الاصطناعي حيث يمكن لمهمة التدريب استخدام جزء من وحدة معالجة الرسومات (GPU).

الأسئلة الشائعة