भिन्नात्मक बस्ता समस्या: उदाहरण के साथ लालची एल्गोरिथ्म

लालची रणनीति क्या है?

लालची एल्गोरिदम प्रत्येक चरण में सर्वोत्तम स्थानीय विकल्प का चयन इस उम्मीद में किया जाता है कि स्थानीय इष्टतमों की एक श्रृंखला वैश्विक रूप से इष्टतम समाधान प्रदान करेगी। डायनेमिक प्रोग्रामिंग की तरह, ये भी अनुकूलन समस्याओं को लक्षित करते हैं, लेकिन ये पहले लिए गए निर्णयों पर पुनर्विचार करने के लिए कभी पीछे मुड़कर नहीं देखते।

ग्रीडी एल्गोरिदम आमतौर पर लिखने में सरल, तेज़ (अक्सर लीनियर या क्वाड्रेटिक टाइम), डीबग करने में आसान और मेमोरी पर कम भार डालने वाले होते हैं। लेकिन इसका नुकसान यह है कि परिणाम हमेशा इष्टतम नहीं होता, इसलिए यह रणनीति केवल उन्हीं समस्याओं के लिए कारगर है जिनकी ग्रीडी-सेफ संरचना सिद्ध हो चुकी है।

लालची रणनीतियाँ एक समय में एक घटक Ai का निर्माण करके संयोजन अनुकूलन को हल करती हैं। प्रत्येक चरण में, आप वर्तमान बाधाओं के तहत इष्टतम रूप से Ai का चयन करते हैं और समस्या को एक छोटी उपसमस्या में संकुचित करते हैं।

किसी ग्रीडी विधि के सही होने के लिए दो गुणधर्मों का पूर्ण होना आवश्यक है:

1. लालची-विकल्प गुणधर्म: प्रत्येक चरण में एक स्थानीय इष्टतम स्थिति वैश्विक इष्टतम स्थिति की ओर ले जाती है। चुनाव पिछले निर्णयों पर निर्भर करता है, भविष्य के निर्णयों पर नहीं।
2. इष्टतम उपसंरचना: पूरी समस्या का इष्टतम समाधान, उसकी उपसमस्याओं के इष्टतम समाधानों को समाहित करता है।

एक लालची एल्गोरिथ्म में पांच घटक होते हैं:

1. संभावित उम्मीदवारों का एक समूह, जिनसे समाधान तैयार किए जाते हैं।
2. एक चयन फ़ंक्शन जो अगले सर्वश्रेष्ठ उम्मीदवार का चयन करता है।
3. एक व्यवहार्यता फ़ंक्शन जो यह जांचता है कि क्या कोई उम्मीदवार वर्तमान आंशिक समाधान का विस्तार कर सकता है।
4. एक उद्देश्य फलन जो पूर्ण या आंशिक समाधान का मूल्यांकन करता है।
5. एक मूल्यांकन फ़ंक्शन जो समाधान पूरा होने पर संकेत देता है।

लालची व्यक्ति का विचार

लालची व्यक्ति पैकेजों को केवल मूल्य के आधार पर छांटता है:

• पैकेजों को मूल्य के बढ़ते क्रम के विपरीत क्रम में व्यवस्थित करें।
• क्रमबद्ध सूची के अनुसार आगे बढ़ें और यदि शेष क्षमता हो तो प्रत्येक पैकेज को थैले में जोड़ें।

यह नियम हमेशा सर्वोत्तम उत्तर नहीं देता। प्रति-उदाहरण:

• पैरामीटर: n = 3, M = 19.
• पैकेज: {i = 1; W = 14; V = 20}, {i = 2; W = 6; V = 16}, {i = 3; W = 10; V = 8} — उच्च मूल्य लेकिन उच्च वजन भी।
• लालची व्यक्ति कुल मूल्य 20 वाले पैकेज 1 को चुनता है, जबकि इष्टतम विकल्प (पैकेज 2, पैकेज 3) 24 तक पहुंचता है।

लालची दो का विचार

लालची दो व्यक्ति केवल वजन के आधार पर पैकेजों को छांटता है:

• पैकेजों को वजन के घटते क्रम के विपरीत क्रम में व्यवस्थित करें।
• क्रमबद्ध सूची के अनुसार आगे बढ़ें और यदि शेष क्षमता हो तो प्रत्येक पैकेज को थैले में जोड़ें।

यह नियम भी सर्वोत्तम नहीं है। प्रति-उदाहरण:

• पैरामीटर: n = 3, M = 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] की गणना करें।
• पैकेजों को इकाई लागत के बढ़ते क्रम के विपरीत क्रम में व्यवस्थित करें।
• क्रमबद्ध सूची में आगे बढ़ें और यदि शेष क्षमता में जगह हो तो प्रत्येक पैकेज को जोड़ें।

इकाई लागत V[i] / W[i] के आधार पर लालची तीन प्रकार

आइडिया: प्रत्येक पैकेज के लिए मूल्य-से-वजन अनुपात V[i] / W[i] की गणना करें, अवरोही क्रम में क्रमबद्ध करें, और उपलब्ध सबसे बड़े अनुपात को पहले लें जब तक कि थैला भर न जाए।

सच के लिए आंशिक एक वैकल्पिक विधि के अनुसार, जब अगला पैकेज पूरी तरह से फिट नहीं हो पाता, तो शेष क्षमता को ठीक से भरने वाला एक अंश लें। यही अतिरिक्त नियम ग्रीडी थ्री को फ्रैक्शनल नैपसैक पर सिद्ध रूप से इष्टतम बनाता है।

एल्गोरिदम के चरण

0/1 ब्रांच-एंड-बाउंड वेरिएंट के लिए, सॉर्ट की गई यूनिट-कॉस्ट सूची एक सर्च ट्री को संचालित करती है:

• चरण १: मूल नोड एक खाली थैले को दर्शाता है। कुल मूल्य = 0. ऊपरी सीमा = M × अधिकतम इकाई लागत।
• चरण १: मूल शाखा को सबसे बड़े अनुपात वाले पैकेज की जितनी प्रतियाँ समाहित हो सकती हैं, उतनी शाखाओं में बाँटें। प्रत्येक शाखा के लिए, कुल मान, शेष क्षमता M और ऊपरी सीमा की पुनः गणना करें।
• चरण १: सबसे पहले उस बच्चे का विस्तार करें जिसकी ऊपरी सीमा सबसे बड़ी हो, ताकि शीघ्र ही एक ठोस समाधान मिल सके।
• चरण १: उन सभी नोड्स को हटा दें जिनकी ऊपरी सीमा वर्तमान सर्वोत्तम पूर्ण समाधान से बेहतर नहीं है।
• चरण १: जब प्रत्येक नोड का विस्तार या छंटाई की जाती है, तो वर्तमान सर्वोत्तम पूर्ण समाधान इष्टतम होता है।

शुद्ध फ्रैक्शनल नैपसैक ग्रीडी एल्गोरिदम के लिए स्यूडो कोड:

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 भार, मूल्य और व्युत्पन्न लागत (छँटाई के लिए प्रयुक्त V/W अनुपात) के साथ वर्ग:

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

फ्रैक्शनल-फिल स्टेप के साथ ग्रीडी थ्री को लागू करें:

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

C# में फ़ंक्शन KnapsackGreProc()

विपरीत उदाहरण: 0/1 नैपसैक पर लालची तीन

ग्रीडी थ्री, फ्रैक्शनल वेरिएंट के लिए सबसे अच्छा विकल्प है, लेकिन 0/1 नैपसैक (जहां आइटम को विभाजित नहीं किया जा सकता) पर यह विफल हो सकता है। प्रति-उदाहरण:

• पैरामीटर: n = 3, M = 10.
• पैकेज: {i = 1; W = 7; V = 9; लागत = 9/7}, {i = 2; W = 6; V = 6; लागत = 1}, {i = 3; W = 4; V = 4; लागत = 1}.
• ग्रीडी थ्री कुल मूल्य 9 के लिए पैकेज 1 का चयन करता है, जबकि इष्टतम 0/1 विकल्प (पैकेज 2, पैकेज 3) 10 तक पहुंचता है।

सबक: ग्रीडी थ्री का प्रयोग केवल तभी करें जब भिन्नों की अनुमति हो। 0/1 वाले विकल्प के लिए, इसका प्रयोग करें। गतिशील प्रोग्रामिंग बजाय.

फ्रैक्शनल नैपसैक के अनुप्रयोग

• माल की लोडिंग जहां तरल पदार्थ, पाउडर या थोक वस्तुओं को वजन के अनुसार विभाजित किया जा सकता है।
• निवेश विकल्पों में पोर्टफोलियो का आवंटन जो आंशिक वित्तपोषण स्वीकार करते हैं।
• क्लाउड बैंडविड्थ शेयरिंग जहां फ्लो लिंक के एक अंश का उपयोग कर सकते हैं।
• विभाज्य कार्यभार के साथ साझा-समय-स्लाइस मॉडल के तहत सीपीयू शेड्यूलिंग।
• एआई संसाधन आवंटन जहां एक प्रशिक्षण कार्य जीपीयू के एक अंश का उपयोग कर सकता है।

अक्सर पूछे जाने वाले प्रश्न