Murtoreppuongelma: Ahne algoritmi esimerkin kanssa

Mikä on ahne strategia?

Ahneita algoritmeja valitsevat parhaan paikallisen vaihtoehdon jokaisessa vaiheessa toivoen, että ketju paikallisia optimeja tuottaa globaalisti optimaalisen ratkaisun. Kuten dynaaminen ohjelmointi, ne kohdistuvat optimointiongelmiin, mutta eivät koskaan katso taaksepäin harkitakseen uudelleen aiempia päätöksiä.

Ahneet algoritmit ovat yleensä yksinkertaisia ​​kirjoittaa, nopeita (usein lineaarisessa tai neliöllisessä ajassa), helppoja debugata ja muistia vähän kuluttavia. Kompromissina on, että tulos ei ole aina optimaalinen, joten strategia toimii vain ongelmissa, joilla on todistetusti ahneutta kestävä rakenne.

Ahneet strategiat ratkaisevat kombinatorisen optimoinnin rakentamalla ratkaisun A yhden komponentin Ai kerrallaan. Jokaisella askeleella valitaan Ai optimaalisesti nykyisillä rajoituksilla ja kutistetaan ongelma pienemmäksi osaongelmaksi.

Ahneen metodin on oltava oikein, joten kahden ominaisuuden on täytyttävä:

1. Ahneudenhaluinen ominaisuus: Jokaisella askeleella saavutettu paikallinen optimi johtaa globaaliin optimiin. Valinta riippuu menneistä päätöksistä, mutta ei tulevista.
2. Optimaalinen alusrakenne: Koko ongelman optimaalinen ratkaisu sisältää sen osaongelmien optimaaliset ratkaisut.

Ahneella algoritmilla on viisi osaa:

1. Ehdokasjoukko, josta ratkaisut rakennetaan.
2. Valintafunktio, joka valitsee parhaan seuraavan ehdokkaan.
3. Toteutettavuusfunktio, joka tarkistaa, voiko ehdokas laajentaa nykyistä osaratkaisua.
4. Objektifunktio, joka arvostaa täydellistä tai osittaisratkaisua.
5. Arviointifunktio, joka ilmoittaa, kun ratkaisu on valmis.

Ahneen idea

Greedy One lajittelee paketit pelkästään arvon mukaan:

• Lajittele paketit arvojärjestyksessä, joka ei ole nouseva.
• Kävele lajiteltu lista läpi ja lisää jokainen paketti reppuun, jos jäljellä oleva kapasiteetti riittää.

Tämä sääntö ei aina anna optimaalista vastausta. Vastaesimerkki:

• Parametrit: n = 3, M = 19.
• Paketit: {i = 1; W = 14; V = 20}, {i = 2; W = 6; V = 16}, {i = 3; W = 10; V = 8} — korkea arvo, mutta myös suuri paino.
• Ahne valitsee paketin 1, jonka kokonaisarvo on 20, kun taas optimaalinen valinta (paketti 2, paketti 3) saavuttaa arvon 24.

Idea Greedy Twosta

Greedy Two lajittelee paketit pelkästään painon mukaan:

• Lajittele paketit painon mukaan ei-alenevassa järjestyksessä.
• Kävele lajiteltu lista läpi ja lisää jokainen paketti reppuun, jos jäljellä oleva kapasiteetti riittää.

Tämäkään sääntö ei ole optimaalinen. Vastaesimerkki:

• Parametrit: n = 3, M = 11.
• Paketit: {i = 1; W = 5; V = 10}, {i = 2; W = 6; V = 16}, {i = 3; W = 10; V = 28} — kevyet, mutta edulliset.
• Ahne Kaksi valintaa (paketti 1, paketti 2) yhteisarvolla 26, kun taas optimaalinen valinta (paketti 3) saavuttaa 28.

Ahneen Kolmon idea

Greedy Three korjaa molemmat ongelmat yhdistämällä arvon ja painon yhdeksi ranking-avaimeksi. Se on murtolukuisen reppuongelman standardimenetelmä.

• Laske jokaisen paketin yksikkökustannus V[i] / W[i].
• Lajittele paketit yksikköhinnan mukaan ei-nousevaan järjestykseen.
• Kävele lajiteltu lista läpi ja lisää jokainen paketti, jos jäljellä oleva kapasiteetti riittää.

Ahne Kolme lajittelua yksikkökustannuksen mukaan V[i] / W[i]

Idea: Laske jokaisen paketin arvo-painosuhde V[i] / W[i], lajittele arvot laskevaan järjestykseen ja ota suurin mahdollinen suhde ensin, kunnes reppu on täynnä.

Totuuden puolesta murto- variantissa, kun seuraavaan pakettiin ei mahdu kokonaista pakettia, otetaan murto-osa, joka täyttää täsmälleen jäljellä olevan kapasiteetin. Tämä lisäsääntö tekee Greedy Threestä todistettavasti optimaalisen Murtolukuisessa Repussa.

Algoritmin vaiheet

0/1 haarautuvassa ja sidotussa variantissa lajiteltu yksikkökustannuslista ajaa hakupuuta:

• Vaihe 1: Juurisolmu edustaa tyhjää reppua. Kokonaisarvo = 0. Yläraja = M × suurin yksikkökustannus.
• Vaihe 2: Haaraa juuri sen mukaan, kuinka monta kopiota suurimman suhteen paketista siihen mahtuu. Laske jokaiselle lapselle uudelleen Kokonaisarvo, jäljellä oleva kapasiteetti M ja Yläraja.
• Vaihe 3: Laajenna ensin lasta, jolla on suurin yläraja, toivoen löytäväsi nopeasti vahvan ratkaisun.
• Vaihe 4: Karsitaan kaikki solmut, joiden UpperBound ei ole parempi kuin nykyinen paras täydellinen ratkaisu.
• Vaihe 5: Kun jokaista solmua joko laajennetaan tai karsitaan, nykyinen paras täydellinen ratkaisu on optimaalinen.

Pseudokoodi puhtaalle Fractional Knapsackin ahneelle algoritmille:

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

Algoritmin monimutkaisuus:

• Yksinkertaisen lajittelun (valinta tai kupla) käyttäminen: O(n²).
• Pikalajittelun tai yhdistämislajittelun käyttö: O(n log n), lajitteluaskeleen määräämä.

Java Code ahneelle kolmelle

Määrittele KnapsackPackage luokka painolla, arvolla ja johdetuilla kustannuksilla (lajittelussa käytetty V/W-suhde):

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

Luo sitten funktio, joka toteuttaa Greedy Threen:

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

Funktio knapsackGreProc() in Java

Koodin selitys:

1. Kääri jokainen syöte sisään KnapsackPackage joten lajitteluavain (V/W-suhde) on laskettu etukäteen.
2. Lajittele kustannusten mukaan laskevaan järjestykseen.
3. Ota jokainen paketti kokonaisena, jos se sopii.
4. Ota murto-osa seuraavasta pakkauksesta täyttääksesi jäljellä olevan kapasiteetin.
5. Pysäytä heti, kun jäljellä oleva kapasiteetti on nolla.

Korjaa huomautus: Alkuperäisen Java silmukka edistynyt i vain silloin, kun paketti ei mahtunut, mikä aiheutti saman paketin ottamisen toistuvasti. Yllä oleva versio siirtää yhden paketin iteraatiota kohden ja lisää osittaistäyttövaiheen, joka vastaa todellista osittaisreppusääntöä.

Java ajuri, joka suorittaa algoritmin toimivassa esimerkissä:

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 ahneelle kolmelle

Määrittele ensin KnapsackPackage luokassa. __lt__ menetelmä tekee siitä suoraan lajiteltavan hinnan mukaan:

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

Toteuta sitten murtolukuinen reppurutiini:

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)

Funktio knapsackGreProc() in Python

Korjaa huomautus: Alkuperäisen Python luokka määritteli tyhjän __init__ ilman kehoa, joka nostaa IndentationErrorYllä oleva versio poistaa tyhjän konstruktorin, koska sitä ei tarvita.

Ensimmäisessä esimerkissä algoritmia suorittava ajuri:

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 ahneelle kolmelle

Määrittele KnapsackPackage luokka:

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

Toteuta Greedy Three murtolukutäyttöaskelella:

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

Funktio KnapsackGreProc() C#:ssa

Vastaesimerkki: Ahne kolmonen 0/1-repulla

Ahne Kolmonen on optimaalinen Murtolukumuunnelmaan, mutta 0/1 Repussa (jossa esineitä ei voi jakaa) se voidaan voittaa. Vastaesimerkki:

• Parametrit: n = 3, M = 10.
• Paketit: {i = 1; W = 7; V = 9; hinta = 9/7}, {i = 2; W = 6; V = 6; hinta = 1}, {i = 3; W = 4; V = 4; hinta = 1}.
• Ahne Kolme valitsee paketin 1 kokonaisarvolla 9, kun taas optimaalinen 0/1-valinta (paketti 2, paketti 3) saavuttaa 10.

Opetus: käytä Greedy Three -käskyä vain, kun murtoluvut ovat sallittuja. 0/1-muunnelmassa käytä Dynaaminen ohjelmointi sen sijaan.

Murtolukuisen repun sovellukset

• Lastin lastaus, jossa nestemäisiä, jauhemaisia ​​tai irtotavaroita voidaan jakaa painon mukaan.
• Salkun allokaatio sijoitusvaihtoehtojen välillä, jotka hyväksyvät osittaisen rahoituksen.
• Pilvipalvelun kaistanleveyden jakaminen, jossa virrat voivat kuluttaa vain murto-osan linkistä.
• CPU-ajoitus jaetun aikaviipaleen mallissa jaettavilla työkuormilla.
• Tekoälyresurssien allokointi, jossa harjoitustyö voi käyttää vain murto-osan GPU:sta.

UKK