Tört hátizsák probléma: Mohó algoritmus példával

Mi az a mohó stratégia?

Kapzsi algoritmusok Minden lépésben a legjobb lokális lehetőséget választják abban a reményben, hogy a lokális optimumok láncolata globálisan optimális megoldást eredményez. A dinamikus programozáshoz hasonlóan optimalizálási problémákat céloznak meg, de soha nem tekintenek vissza a korábbi döntéseik felülvizsgálatára.

A mohó algoritmusok általában egyszerűen megírhatók, gyorsak (gyakran lineáris vagy kvadratikus idejűek), könnyen hibakereshetők és kevés memóriát igényelnek. A kompromisszum az, hogy az eredmény nem mindig optimális, így a stratégia csak olyan problémáknál működik, amelyek bizonyítottan mohó algoritmus-biztos struktúrával rendelkeznek.

A mohó stratégiák a kombinatorikus optimalizálást úgy oldják meg, hogy egyszerre egy komponens Ai-t építenek fel. Minden lépésben az aktuális korlátok mellett optimálisan választják ki az Ai-t, és a problémát egy kisebb részproblémára zsugorítják.

Egy mohó metódus helyes működéséhez két tulajdonságnak kell teljesülnie:

1. Kapzsi választási tulajdonság: Egy lokális optimum minden lépésben globális optimumhoz vezet. A választás a múltbeli döntésektől függ, de nem a jövőbeliektől.
2. Optimális alépítmény: A teljes probléma optimális megoldása tartalmazza a részproblémáinak optimális megoldásait.

Egy mohó algoritmusnak öt összetevője van:

1. Egy jelöltkészlet, amelyből a megoldások épülnek fel.
2. Egy kiválasztó függvény, amely kiválasztja a legjobb következő jelöltet.
3. Egy megvalósíthatósági függvény, amely azt vizsgálja, hogy egy jelölt kiterjesztheti-e a jelenlegi részmegoldást.
4. Egy olyan célfüggvény, amely teljes vagy részleges megoldást értékel.
5. Egy kiértékelő függvény, amely jelzi, ha a megoldás elkészült.

A Mohó Egy ötlete

A Greedy One kizárólag érték alapján rendezi a csomagokat:

• Rendezd a csomagokat nem növekvő értékrendbe.
• Járd végig a listát, és tedd a csomagokat a hátizsákba, ha a maradék kapacitás elbírja.

Ez a szabály nem mindig adja az optimális választ. Ellenpélda:

• Paraméterek: n = 3, M = 19.
• Csomagok: {i = 1; W = 14; V = 20}, {i = 2; W = 6; V = 16}, {i = 3; W = 10; V = 8} — nagy érték, de nagy súly is.
• A Kapzsi az 1. csomagot választja, amelynek összértéke 20, míg az optimális választás (2. csomag, 3. csomag) eléri a 24-et.

A Mohó Kettő ötlete

A Greedy Two kizárólag súly alapján rendezi a csomagokat:

• A csomagokat nem csökkenő súlyrendbe rendezd.
• Járd végig a listát, és tedd a csomagokat a hátizsákba, ha a maradék kapacitás elbírja.

Ez a szabály sem optimális. Ellenpélda:

• Paraméterek: n = 3, M = 11.
• Csomagok: {i = 1; W = 5; V = 10}, {i = 2; W = 6; V = 16}, {i = 3; W = 10; V = 28} — könnyűek, de alacsony értékűek.
• Kapzsi Két választás (1. csomag, 2. csomag) összértékkel 26, míg az optimális választás (3. csomag) eléri a 28-at.

A Mohó Három ötlete

A Greedy Three módszer mindkét hibát úgy orvosolja, hogy az értéket és a súlyt egyetlen rangsoroló kulcsba kombinálja. Ez a Tört Hátizsák Probléma standard módszere.

• Számítsa ki az egységnyi költséget V[i] / W[i] minden csomagra.
• A csomagokat nem növekvő egységár szerint rendezd.
• Járd végig a rendezett listát, és add hozzá az összes csomagot, ha a fennmaradó kapacitás elbírja.

Mohó Három rendezi egységköltség szerint V[i] / W[i]

Ötlet: Számítsd ki minden csomag V[i] / W[i] érték-tömeg arányát, rendezd csökkenő sorrendbe, és a legnagyobb elérhető arányt vedd először, amíg a hátizsák meg nem telik.

Az igazért töredékes Egy másik változatban, amikor a következő csomag nem fér bele az egészbe, vegyél egy olyan tört részt, amely pontosan kitölti a fennmaradó kapacitást. Ez a plusz szabály teszi a Mohó Hármast bizonyíthatóan optimálissá a Tört Hátizsákon.

Az algoritmus lépései

A 0/1 elágazásos és kötött változat esetében a rendezett egységköltség-lista egy keresőfát vezérel:

• Lépés 1: A gyökércsomópont egy üres hátizsákot jelöl. TeljesÉrték = 0. FelsőKorlát = M × maximális egységköltség.
• Lépés 2: Ágazd el a gyökeret aszerint, hogy a legnagyobb arányú csomag hány példánya fér bele. Minden gyermek esetében számítsd ki újra a TeljesÉrtéket, a fennmaradó M kapacitást és a FelsőKorlátot.
• Lépés 3: Először a legnagyobb felső határral rendelkező gyermeket bővítsd ki, abban a reményben, hogy gyorsan találsz egy erős megoldást.
• Lépés 4: Nyiss ki minden olyan csomópontot, amelynek UpperBound értéke nem jobb, mint a jelenlegi legjobb teljes megoldás.
• Lépés 5: Amikor minden csomópontot kibővítünk vagy metszünk, a jelenlegi legjobb teljes megoldás az optimális.

Pszeudo kód a tiszta Fractional Knapsack mohó algoritmushoz:

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

Az algoritmus komplexitása:

• Egyszerű rendezés (kijelölés vagy buborékrendezés) használatával: O(n²).
• Gyors rendezés vagy összevonó rendezés használata: O(n log n), amelyet a rendezési lépés dominál.

Java Code a Greedy Three-nek

Definiálja a KnapsackPackage osztály súllyal, értékkel és származtatott költséggel (a rendezéshez használt V/W arány):

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

Ezután hozd létre a Greedy Three-t megvalósító függvényt:

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

A knapsackGreProc() in Java

A kód magyarázata:

1. Csomagolja be minden bemenetet egy KnapsackPackage tehát a rendezési kulcs (V/W arány) előre kiszámított.
2. Rendezés költség szerint csökkenő sorrendben.
3. Ha belefér, vegyen el egy csomagot egészben.
4. Vegyen egy töredéket a következő csomagból, hogy kitöltse a maradék kapacitást.
5. Álljon meg, amint a maradék kapacitás eléri a nullát.

Javítási megjegyzés: Az eredeti Java hurok haladó i csak akkor, ha egy csomag nem illett bele, ami ugyanazon csomag ismételt felvételét eredményezte. A fenti verzió iterációnként egy csomaggal lép előre, és hozzáad egy törtkitöltési lépést, amely megfelel a valódi Tört hátizsák szabálynak.

Java illesztőprogram, amely egy működő példán futtatja az algoritmust:

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 a Greedy Three-nek

Először definiáld a KnapsackPackage osztály. A __lt__ a metódus közvetlenül költség szerint rendezhetővé teszi:

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

Ezután implementáld a Frakcionális Hátizsák rutint:

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)

A knapsackGreProc() in Python

Javítási megjegyzés: Az eredeti Python az osztály egy üres __init__ test nélkül, ami felemeli IndentationErrorA fenti verzió eltávolítja az üres konstruktort, mert nincs rá szükség.

Az első példában az algoritmust futtató illesztőprogram:

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 a Greedy Three-nek

Definiálja a KnapsackPackage osztály:

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

Implementálja a Greedy Three-t egy törtkitöltéses lépéssel:

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

A KnapsackGreProc() függvény C#-ban

Ellenpélda: Mohó hármas 0/1-es hátizsákon

A Mohó Három az optimális a Tört variánshoz, de a 0/1-es Hátizsákon (ahol a tárgyak nem oszthatók fel) legyőzhető. Ellenpélda:

• Paraméterek: n = 3, M = 10.
• Csomagok: {i = 1; W = 7; V = 9; költség = 9/7}, {i = 2; W = 6; V = 6; költség = 1}, {i = 3; W = 4; V = 4; költség = 1}.
• A Greedy Three az 1. csomagot választja 9-es összértékért, míg az optimális 0/1-es választás (2. csomag, 3. csomag) eléri a 10-es értéket.

A tanulság: csak akkor használd a Greedy Three-t, ha törtek megengedettek. A 0/1 változathoz használd Dinamikus programozás helyette.

A tört hátizsák alkalmazásai

• Olyan rakományrakodás, ahol folyékony, por vagy ömlesztett áruk súly szerint bonthatók.
• Portfólió allokáció részleges finanszírozást elfogadó befektetési lehetőségek között.
• Felhőalapú sávszélesség-megosztás, ahol a folyamatok egy link töredékét foglalhatják el.
• CPU ütemezés megosztott időszelet modellben, osztható munkaterhelésekkel.
• AI erőforrás-elosztás, ahol egy betanítási feladat a GPU töredékét használhatja.

GYIK