Murdkotiprobleem: Ahne algoritm koos näitega

Mis on ahne strateegia?

Ahned algoritmid valivad igal sammul parima lokaalse valiku lootuses, et lokaalsete optimumite ahel annab globaalselt optimaalse lahenduse. Nagu dünaamiline programmeerimine, on nende eesmärk optimeerimisprobleemid, kuid nad ei vaata kunagi tagasi, et varasemaid otsuseid ümber hinnata.

Ahned algoritmid on tavaliselt lihtsalt kirjutatavad, kiired (sageli lineaarse või ruutajaga), kergesti silutavad ja mäluvaesed. Kompromissiks on see, et tulemus ei ole alati optimaalne, seega töötab strateegia ainult probleemide puhul, millel on tõestatult ahne algoritmikindel struktuur.

Ahned strateegiad lahendavad kombinatoorse optimeerimise, luues lahenduse A ühe komponendi Ai kaupa. Igal sammul valitakse Ai optimaalselt praeguste piirangute piires ja kahandatakse probleem väiksemaks alamprobleemiks.

Ahne meetodi korrektseks toimimiseks peavad kehtima kaks omadust:

1. Ahne valiku vara: Igal sammul olev lokaalne optimum viib globaalse optimumini. Valik sõltub varasematest otsustest, mitte tulevastest.
2. Optimaalne alusstruktuur: Kogu probleemi optimaalne lahendus sisaldab ka selle alamprobleemide optimaalseid lahendusi.

Ahne algoritm koosneb viiest komponendist:

1. Kandidaatide komplekt, millest lahendused ehitatakse.
2. Valikufunktsioon, mis valib järgmise parima kandidaadi.
3. Teostatavusfunktsioon, mis kontrollib, kas kandidaat saab praegust osalist lahendust laiendada.
4. Eesmärgifunktsioon, mis väärtustab täielikku või osalist lahendit.
5. Hindamisfunktsioon, mis annab märku lahenduse valmimisest.

Ahne idee

Greedy One sorteerib pakke ainult väärtuse järgi:

• Sorteeri pakke väärtuse mittekasvavas järjekorras.
• Kõnni sorteeritud nimekirja järgi ja lisa iga pakk seljakotti, kui järelejäänud maht seda mahutab.

See reegel ei anna alati optimaalset vastust. Vastunäide:

• Parameetrid: n = 3, M = 19.
• Paketid: {i = 1; W = 14; V = 20}, {i = 2; W = 6; V = 16}, {i = 3; W = 10; V = 8} — suur väärtus, aga ka suur kaal.
• Ahne valib paketi 1 koguväärtusega 20, samas kui optimaalne valik (pakett 2, pakett 3) ulatub väärtuseni 24.

Ahne kahe idee

Greedy Two sorteerib pakke ainult kaalu järgi:

• Sorteeri pakid kaalu järgi mittekahanevas järjekorras.
• Kõnni sorteeritud nimekirja järgi ja lisa iga pakk seljakotti, kui järelejäänud maht seda mahutab.

See reegel ei ole samuti optimaalne. Vastunäide:

• Parameetrid: n = 3, M = 11.
• Paketid: {i = 1; W = 5; V = 10}, {i = 2; W = 6; V = 16}, {i = 3; W = 10; V = 28} — kerged, aga madala väärtusega.
• Ahne Kaks valikut (pakett 1, pakett 2) koguväärtusega 26, samas kui optimaalne valik (pakett 3) ulatub 28-ni.

Ahne Kolmiku idee

Ahne Kolmas parandab mõlemad vead, ühendades väärtuse ja kaalu üheks järjestusvõtmeks. See on murdosa seljakotiprobleemi standardmeetod.

• Arvutage iga paki ühikmaksumus V[i] / W[i].
• Sorteeri pakid ühikuhinna järgi mittekasvavas järjekorras.
• Kõnni sorteeritud nimekirjas ringi ja lisa iga pakend, kui järelejäänud mahutavus seda mahutab.

Ahne Kolm sorti ühikuhinna järgi V[i] / W[i]

Idee: Arvutage iga paki väärtuse ja kaalu suhe V[i] / W[i], sorteerige kahanevas järjekorras ja alustage suurimast saadaolevast suhtest, kuni seljakott on täis.

Tõelise jaoks Osaline variandi puhul, kui järgmine pakk ei mahu tervelt ära, võetakse murdosa, mis täpselt täidab ülejäänud mahutavuse. See lisareegel teebki Ahne Kolme tõestatavalt optimaalseks Murdosalise Seljakoti puhul.

Algoritmi sammud

0/1 hargnemis-ja-seotud variandi puhul käivitab sorteeritud ühikkulude loend otsingupuu:

• Samm 1: Juursõlm esindab tühja seljakotti. Koguväärtus = 0. Ülempiir = M × maksimaalne ühikuhind.
• Samm 2: Harusta juur selle järgi, mitu koopiat suurima suhtega paketist mahub. Iga lapse jaoks arvuta uuesti TotalValue, järelejäänud maht M ja UpperBound.
• Samm 3: Laienda esmalt suurima ülemise piiriga last, lootes leida kiiresti tugev lahendus.
• Samm 4: Kärbi välja kõik sõlmed, mille UpperBound (ülempiir) ei ole parem kui praegune parim täielik lahendus.
• Samm 5: Kui iga sõlme kas laiendatakse või kärbitakse, on praegune parim terviklahendus optimaalne.

Pseudokood puhta Fractional Knapsack ahne algoritmi jaoks:

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

Algoritmi keerukus:

• Lihtsa sortimise (valiku või mulli) abil: O(n²).
• Kiirsortimise või liitsortimise kasutamine: O(n log n), domineerib sortimisetapp.

Java Code Ahne Kolme jaoks

Määratlege KnapsackPackage klass koos kaalu, väärtuse ja tuletatud maksumusega (sortimiseks kasutatav V/W suhe):

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

Seejärel loo funktsioon, mis rakendab Greedy Three'i:

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

Funktsioon knapsackGreProc() in Java

Koodi selgitus:

1. Mähi iga sisend sisse KnapsackPackage seega on sortimisvõti (V/W suhe) eelnevalt arvutatud.
2. Sorteeri kulude kahanevas järjekorras.
3. Võtke iga pakend tervelt, kui see sobib.
4. Ülejäänud mahutavuse täitmiseks võtke murdosa järgmisest pakist.
5. Lõpetage kohe, kui järelejäänud maht langeb nulli.

Paranda märkus: originaal Java tsükkel edasijõudnutele i ainult siis, kui pakett ei sobinud, mis põhjustas sama paketi korduva võtmise. Ülaltoodud versioon liigub ühe paketi võrra edasi iteratsiooni kohta ja lisab murdosa täitmise sammu, mis vastab tegelikule murdosa seljakoti reeglile.

Java draiver, mis käivitab algoritmi töötatud näitel:

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 Ahne Kolme jaoks

Esmalt defineeri KnapsackPackage klass. The __lt__ meetod muudab selle otse hinna järgi sorteeritavaks:

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

Seejärel rakenda murdosalise seljakoti rutiini:

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)

Funktsioon knapsackGreProc() in Python

Paranda märkus: originaal Python klass defineeris tühja __init__ ilma kehata, mis tõstab IndentationErrorÜlaltoodud versioon eemaldab tühja konstruktori, kuna seda pole vaja.

Draiver, mis käivitab algoritmi esimeses näites:

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 Ahne Kolme jaoks

Määratlege KnapsackPackage klass:

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

Rakenda Greedy Three murdosa täitmise sammuga:

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

Funktsioon KnapsackGreProc() C#-s

Vastunäide: Ahne kolmik 0/1 seljakotil

Ahne Kolmik on optimaalne Murdvariandi jaoks, aga 0/1 Seljakoti puhul (kus esemeid ei saa jagada) saab selle võita. Vastunäide:

• Parameetrid: n = 3, M = 10.
• Paketid: {i = 1; W = 7; V = 9; maksumus = 9/7}, {i = 2; W = 6; V = 6; maksumus = 1}, {i = 3; W = 4; V = 4; maksumus = 1}.
• Ahne Kolmik valib paketi 1 koguväärtusega 9, samas kui optimaalne 0/1 valik (pakett 2, pakett 3) ulatub 10-ni.

Õppetund: kasuta Ahnet Kolmi ainult siis, kui murrud on lubatud. Variandi 0/1 puhul kasuta Dünaamiline programmeerimine asemel.

Murdosa seljakoti rakendused

• Kauba laadimine, kus vedelaid, pulbrilisi või lahtiseid kaupu saab kaalu järgi jagada.
• Portfelli jaotus osalist rahastamist aktsepteerivate investeerimisvõimaluste vahel.
• Pilve ribalaiuse jagamine, kus vood võivad tarbida murdosa lingist.
• Protsessori ajastamine jagatud ajaviilu mudeli alusel jagatavate töökoormustega.
• Tehisintellekti ressursside eraldamine, kus treeningtöö saab kasutada murdosa GPU-st.

KKK