Fractional Napsack Problem: Grådig algoritme med eksempel

Hvad er Greedy Strategy?

Grådige algoritmer Vælg det bedste lokale valg i hvert trin i håb om, at en kæde af lokale optima producerer en globalt optimal løsning. Ligesom dynamisk programmering fokuserer de på optimeringsproblemer, men de ser aldrig tilbage for at genoverveje tidligere beslutninger.

Grådige algoritmer er normalt enkle at skrive, hurtige (ofte lineær eller kvadratisk tid), nemme at debugge og kræver kun lidt hukommelse. Ulempen er, at resultatet ikke altid er optimalt, så strategien fungerer kun for problemer, der har en dokumenteret grådig-sikker struktur.

Grådige strategier løser kombinatorisk optimering ved at bygge en løsning A med én komponent af AI ad gangen. Ved hvert trin vælger du AI optimalt under de nuværende begrænsninger og krymper problemet til et mindre delproblem.

To egenskaber skal være gældende for at en grådig metode kan være korrekt:

1. Ejendom med grådigt valg: Et lokalt optimum på hvert trin fører til et globalt optimum. Valget afhænger af tidligere beslutninger, men ikke af fremtidige.
2. Optimal understruktur: Den optimale løsning af hele problemet indeholder optimale løsninger af dets delproblemer.

En grådig algoritme har fem komponenter:

1. Et kandidatsæt, hvorfra løsninger bygges.
2. En udvælgelsesfunktion, der udvælger den bedste næste kandidat.
3. En gennemførlighedsfunktion, der kontrollerer, om en kandidat kan udvide den nuværende delvise løsning.
4. En objektiv funktion, der værdisætter en fuldstændig eller delvis løsning.
5. En evalueringsfunktion, der signalerer, når løsningen er færdig.

Idéen om Greedy One

Greedy One sorterer pakker udelukkende efter værdi:

• Sorter pakker i ikke-stigende rækkefølge efter værdi.
• Gå den sorterede liste, og tilføj hver pakke til rygsækken, hvis den resterende kapacitet kan rumme den.

Denne regel giver ikke altid det optimale svar. Modeksempel:

• Parametre: n = 3, M = 19.
• Pakker: {i = 1; W = 14; V = 20}, {i = 2; W = 6; V = 16}, {i = 3; W = 10; V = 8} — høj værdi, men også høj vægt.
• Den Grådige vælger pakke 1 med en samlet værdi på 20, mens det optimale valg (pakke 2, pakke 3) når 24.

Idéen om Greedy Two

Greedy Two sorterer pakker udelukkende efter vægt:

• Sorter pakkerne i ikke-faldende rækkefølge efter vægt.
• Gå den sorterede liste, og tilføj hver pakke til rygsækken, hvis den resterende kapacitet kan rumme den.

Denne regel er heller ikke optimal. Modeksempel:

• Parametre: n = 3, M = 11.
• Pakker: {i = 1; W = 5; V = 10}, {i = 2; W = 6; V = 16}, {i = 3; W = 10; V = 28} — letvægts, men lav værdi.
• To valg (pakke 1, pakke 2) med en samlet værdi på 26, mens det optimale valg (pakke 3) når 28.

Idéen om Greedy Three

Greedy Three retter begge fejl ved at kombinere værdi og vægt i en enkelt rangeringsnøgle. Det er standardmetoden for det brøkdelte rygsækproblem.

• Beregn enhedsomkostningerne V[i] / W[i] for hver pakke.
• Sorter pakker i ikke-stigende rækkefølge efter enhedspris.
• Gå den sorterede liste igennem, og tilføj hver pakke, hvis den resterende kapacitet kan rumme den.

Grådige Tre sorteringer efter enhedspris V[i] / W[i]

Ide: Beregn værdi-til-vægt-forholdet V[i] / W[i] for hver pakke, sorter i faldende rækkefølge, og tag det største tilgængelige forhold først, indtil rygsækken er fuld.

For det sande Fractional variant, når den næste pakke ikke kan være hel, tag en brøkdel, der præcist fylder den resterende kapacitet. Den ekstra regel er det, der gør Greedy Three beviseligt optimal på Fractional Knapsack.

Trin i algoritmen

For 0/1-varianten med forgrening og binding driver den sorterede enhedsprisliste et søgetræ:

• Trin 1: Rodnoden repræsenterer en tom rygsæk. TotalVærdi = 0. UpperBound = M × maksimal enhedspris.
• Trin 2: Forgren roden efter, hvor mange kopier af pakken med det største forhold der er plads til. For hvert barn genberegnes TotalValue, den resterende kapacitet M og UpperBound.
• Trin 3: Udvid først barnet med den største øvre grænse, i håb om hurtigt at finde en stærk løsning.
• Trin 4: Beskær enhver node, hvis UpperBound ikke er bedre end den nuværende bedste komplette løsning.
• Trin 5: Når hver node enten udvides eller beskæres, er den nuværende bedste komplette løsning optimal.

Pseudokode til den rene fraktionerede rygsæk-grådige algoritme:

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

Algoritmens kompleksitet:

• Brug af en simpel sortering (markering eller boble): O(n²).
• Brug af hurtig sortering eller sammenflettet sortering: O(n log n), domineret af sorteringstrinnet.

Java Code for de grådige tre

Definer KnapsackPackage klasse med vægt, værdi og afledte omkostninger (V/W-forholdet brugt til sortering):

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

Opret derefter den funktion, der implementerer 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);
}

Funktion knapsackGreProc() in Java

Forklaring af kode:

1. Pak hvert input ind i en KnapsackPackage så sorteringsnøglen (V/W-forholdet) er forudberegnet.
2. Sortér i faldende rækkefølge efter pris.
3. Tag hver pakke hel, hvis den passer.
4. Tag en brøkdel af den næste pakke for at fylde den resterende kapacitet.
5. Stop så snart den resterende kapacitet når nul.

Rettelse af bemærkning: den oprindelige Java avanceret løkke i kun når en pakke ikke passede, hvilket medførte, at den samme pakke blev taget gentagne gange. Ovenstående version flytter én pakke frem pr. iteration og tilføjer et brøkfyldningstrin, der matcher den ægte Brøkryggersregel.

Java driver, der kører algoritmen på et bearbejdet eksempel:

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 for de grådige tre

Definer først KnapsackPackage klasse. Det __lt__ Metoden gør det direkte sorterbart efter pris:

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

Implementer derefter den fraktionelle rygsækrutine:

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)

Funktion knapsackGreProc() in Python

Rettelse af bemærkning: den oprindelige Python klasse definerede en tom __init__ uden krop, som hæver IndentationErrorOvenstående version fjerner den tomme konstruktør, fordi ingen er nødvendig.

Driver, der kører algoritmen på det første eksempel:

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 for de grådige tre

Definer KnapsackPackage klasse:

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

Implementer Greedy Three med et brøkfyldningstrin:

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

Funktion KnapsackGreProc() i C#

Modeksempel: Grådige tre på 0/1 rygsæk

Grådige Tre er optimal til Brøkvarianten, men på 0/1 Rygsækken (hvor genstande ikke kan opdeles) kan den besejres. Modeksempel:

• Parametre: n = 3, M = 10.
• Pakker: {i = 1; W = 7; V = 9; pris = 9/7}, {i = 2; W = 6; V = 6; pris = 1}, {i = 3; W = 4; V = 4; pris = 1}.
• Greedy Three vælger pakke 1 for en samlet værdi på 9, mens det optimale 0/1-valg (pakke 2, pakke 3) når 10.

Lektionen: brug kun Greedy Three, når brøker er tilladt. For 0/1-varianten, brug Dynamisk programmering i stedet.

Anvendelser af fraktioneret rygsæk

• Lastning, hvor flydende, pulveriseret eller bulkgods kan opdeles efter vægt.
• Porteføljeallokering på tværs af investeringsmuligheder, der accepterer delvis finansiering.
• Deling af cloud-båndbredde, hvor flows kun kan forbruge en brøkdel af et link.
• CPU-planlægning under en delt tidsslice-model med delelige arbejdsbelastninger.
• AI-ressourceallokering, hvor et træningsjob kun kan bruge en brøkdel af en GPU.

Ofte Stillede Spørgsmål