Πρόβλημα κλασματικού σακιδίου: Άπληστος αλγόριθμος με Παράδειγμα

Τι είναι η Greedy Strategy;

Άπληστοι αλγόριθμοι επιλέγουν την καλύτερη τοπική επιλογή σε κάθε βήμα με την ελπίδα ότι μια αλυσίδα τοπικών βέλτιστων παράγει μια καθολικά βέλτιστη λύση. Όπως και ο Δυναμικός Προγραμματισμός, στοχεύουν σε προβλήματα βελτιστοποίησης, αλλά ποτέ δεν κοιτάζουν πίσω για να επανεξετάσουν προηγούμενες αποφάσεις.

Οι άπληστοι αλγόριθμοι είναι συνήθως απλοί στη σύνταξη, γρήγοροι (συχνά γραμμικοί ή τετραγωνικοί χρόνοι), εύκολοι στην αποσφαλμάτωση και καταναλώνουν λίγο μνήμη. Το μειονέκτημα είναι ότι το αποτέλεσμα δεν είναι πάντα το βέλτιστο, επομένως η στρατηγική λειτουργεί μόνο για προβλήματα που έχουν αποδεδειγμένα ασφαλή δομή για άπληστους.

Οι άπληστες στρατηγικές επιλύουν τη συνδυαστική βελτιστοποίηση δημιουργώντας μια λύση A με ένα στοιχείο ΤΝ κάθε φορά. Σε κάθε βήμα επιλέγετε το ΤΝ βέλτιστα υπό τους τρέχοντες περιορισμούς και συρρικνώνετε το πρόβλημα σε ένα μικρότερο υποπρόβλημα.

Δύο ιδιότητες πρέπει να ισχύουν για να είναι σωστή μια άπληστη μέθοδος:

1. Ιδιοκτησία με άπληστη επιλογή: Ένα τοπικό βέλτιστο σε κάθε βήμα οδηγεί σε ένα καθολικό βέλτιστο. Η επιλογή εξαρτάται από προηγούμενες αποφάσεις αλλά όχι από μελλοντικές.
2. Βέλτιστη υποδομή: Η βέλτιστη λύση ολόκληρου του προβλήματος περιέχει βέλτιστες λύσεις των υποπροβλημάτων του.

Ένας άπληστος αλγόριθμος έχει πέντε στοιχεία:

1. Ένα υποψήφιο σύνολο από το οποίο κατασκευάζονται λύσεις.
2. Μια συνάρτηση επιλογής που επιλέγει τον καλύτερο επόμενο υποψήφιο.
3. Μια συνάρτηση σκοπιμότητας που ελέγχει εάν ένας υποψήφιος μπορεί να επεκτείνει την τρέχουσα μερική λύση.
4. Μια αντικειμενική συνάρτηση που δίνει τιμές σε μια πλήρη ή μερική λύση.
5. Μια συνάρτηση αξιολόγησης που σηματοδοτεί πότε η λύση είναι πλήρης.

The Idea of ​​Greedy One

Το Greedy One ταξινομεί τα πακέτα μόνο με βάση την αξία τους:

• Ταξινομήστε τα πακέτα σε μη αύξουσα σειρά αξίας.
• Περπατήστε στην ταξινομημένη λίστα και προσθέστε κάθε πακέτο στο σακίδιο, αν η υπόλοιπη χωρητικότητα το χωράει.

Αυτός ο κανόνας δεν δίνει πάντα τη βέλτιστη απάντηση. Αντιπαράδειγμα:

• Παράμετροι: n = 3, M = 19.
• Πακέτα: {i = 1; W = 14; V = 20}, {i = 2; W = 6; V = 16}, {i = 3; W = 10; V = 8} — υψηλή αξία αλλά και υψηλό βάρος.
• Ο Greedy One επιλέγει το πακέτο 1 με συνολική αξία 20, ενώ η βέλτιστη επιλογή (πακέτο 2, πακέτο 3) φτάνει το 24.

The Idea of ​​Greedy Two

Άπληστοι Δύο τύποι δεμάτων μόνο κατά βάρος:

• Ταξινομήστε τα πακέτα σε μη φθίνουσα σειρά βάρους.
• Περπατήστε στην ταξινομημένη λίστα και προσθέστε κάθε πακέτο στο σακίδιο, αν η υπόλοιπη χωρητικότητα το χωράει.

Αυτός ο κανόνας επίσης δεν είναι βέλτιστος. Αντιπαράδειγμα:

• Παράμετροι: n = 3, M = 11.
• Πακέτα: {i = 1; W = 5; V = 10}, {i = 2; W = 6; V = 16}, {i = 3; W = 10; V = 28} — ελαφρύ αλλά χαμηλής αξίας.
• Greedy Two επιλογές (πακέτο 1, πακέτο 2) με συνολική αξία 26, ενώ η βέλτιστη επιλογή (πακέτο 3) φτάνει τα 28.

The Idea of ​​Greedy Three

Το Greedy Three διορθώνει και τις δύο αποτυχίες συνδυάζοντας την τιμή και το βάρος σε ένα μόνο κλειδί κατάταξης. Είναι η τυπική μέθοδος για το πρόβλημα του κλασματικού σακιδίου.

• Υπολογίστε το κόστος μονάδας V[i] / W[i] για κάθε πακέτο.
• Ταξινομήστε τα πακέτα σε μη αύξουσα σειρά κόστους μονάδας.
• Περπατήστε στην ταξινομημένη λίστα και προσθέστε κάθε πακέτο αν η υπόλοιπη χωρητικότητα το χωράει.

Άπληστοι Τρεις ταξινομήσεις ανά κόστος μονάδας V[i] / W[i]

Ιδέα: Υπολογίστε την αναλογία αξίας προς βάρος V[i] / W[i] για κάθε συσκευασία, ταξινομήστε την κατά φθίνουσα σειρά και επιλέξτε πρώτα τη μεγαλύτερη διαθέσιμη αναλογία μέχρι να γεμίσει ο σάκος.

Για το αληθινό Κλασματικός παραλλαγή, όταν το επόμενο πακέτο δεν μπορεί να χωρέσει ολόκληρο, πάρτε ένα κλάσμα που γεμίζει ακριβώς την υπόλοιπη χωρητικότητα. Αυτός ο επιπλέον κανόνας είναι που κάνει το Greedy Three αποδεδειγμένα βέλτιστο στο Fractional Knapsack.

Βήματα του Αλγορίθμου

Για την παραλλαγή διακλάδωσης και δέσμευσης 0/1, η ταξινομημένη λίστα κόστους μονάδας οδηγεί ένα δέντρο αναζήτησης:

• Βήμα 1: Ο ριζικός κόμβος αντιπροσωπεύει ένα άδειο σακίδιο. Συνολική Τιμή = 0. Άνω Όριο = M × μέγιστο μοναδιαίο κόστος.
• Βήμα 2: Διακλαδώστε τη ρίζα με βάση τον αριθμό των αντιγράφων του πακέτου με τη μεγαλύτερη αναλογία που μπορεί να χωρέσει. Για κάθε θυγατρικό, υπολογίστε ξανά την TotalValue, την υπολειπόμενη χωρητικότητα M και το UpperBound.
• Βήμα 3: Αναπτύξτε πρώτα το παιδί με το μεγαλύτερο UpperBound, με την ελπίδα να βρείτε γρήγορα μια ισχυρή λύση.
• Βήμα 4: Κλαδέψτε οποιονδήποτε κόμβο του οποίου το UpperBound δεν είναι καλύτερο από την τρέχουσα καλύτερη ολοκληρωμένη λύση.
• Βήμα 5: Όταν κάθε κόμβος είτε επεκτείνεται είτε κλαδεύεται, η τρέχουσα καλύτερη ολοκληρωμένη λύση είναι η βέλτιστη.

Ψευδοκώδικας για τον καθαρό αλγόριθμο Fractional Knapsack greedy:

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

Στη συνέχεια, δημιουργήστε τη συνάρτηση που υλοποιεί το Greedy Three:

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 μόνο όταν ένα πακέτο δεν ταίριαζε, γεγονός που προκαλούσε την επανειλημμένη λήψη του ίδιου πακέτου. Η παραπάνω έκδοση προωθεί ένα πακέτο ανά επανάληψη και προσθέτει ένα βήμα κλασματικής συμπλήρωσης, που ταιριάζει με τον πραγματικό κανόνα Fractional Knapsack.

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

Στη συνέχεια, εφαρμόστε τη ρουτίνα Fractional Knapsack:

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

Το Greedy Three είναι ιδανικό για την παραλλαγή Fractional, αλλά στο Knapsack 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}.
• Ο Greedy Three επιλέγει το πακέτο 1 για συνολική αξία 9, ενώ η βέλτιστη επιλογή 0/1 (πακέτο 2, πακέτο 3) φτάνει το 10.

Το μάθημα: χρησιμοποιήστε το Greedy Three μόνο όταν επιτρέπονται κλάσματα. Για την παραλλαγή 0/1, χρησιμοποιήστε Δυναμικός προγραμματισμός Αντιθέτως.

Εφαρμογές του κλασματικού σακιδίου πλάτης

• Φόρτωση φορτίου όπου υγρά, κονιοποιημένα ή χύμα εμπορεύματα μπορούν να χωριστούν κατά βάρος.
• Κατανομή χαρτοφυλακίου μεταξύ επενδυτικών επιλογών που δέχονται μερική χρηματοδότηση.
• Κοινή χρήση εύρους ζώνης στο cloud όπου οι ροές μπορούν να καταναλώσουν ένα κλάσμα ενός συνδέσμου.
• Χρονοπρογραμματισμός CPU βάσει μοντέλου κοινόχρηστου χρονικού διαστήματος με διαιρούμενα φόρτα εργασίας.
• Κατανομή πόρων τεχνητής νοημοσύνης όπου μια εκπαιδευτική εργασία μπορεί να χρησιμοποιήσει ένα κλάσμα μιας GPU.

Συχνές Ερωτήσεις