Murtoreppuongelma: Ahne algoritmi esimerkin kanssa

Mikä on ahne strategia?

Ahneet algoritmit ovat kuin dynaamisia ohjelmointialgoritmeja, joita käytetään usein ratkaisemaan optimaalisia ongelmia (löytää parhaat ratkaisut ongelmaan tietyn kriteerin mukaan).

Ahneet algoritmit toteuttavat optimaaliset paikalliset valinnat siinä toivossa, että valinnat johtavat optimaaliseen globaaliin ratkaisuun ratkaistavaan ongelmaan. Ahneita algoritmeja ei useinkaan ole liian vaikeita määrittää, ne ovat nopeita (aikamonimutkaisuus on usein lineaarinen funktio tai pitkälti toisen asteen funktio). Lisäksi näitä ohjelmia ei ole vaikea korjata, ja ne käyttävät vähemmän muistia. Mutta tulokset eivät aina ole optimaalinen ratkaisu.

Ahneita strategioita käytetään usein ratkaisemaan kombinatorinen optimointiongelma rakentamalla vaihtoehto A. Vaihtoehto A rakennetaan valitsemalla A:n jokainen komponentti Ai, kunnes se on valmis (riittävästi n komponenttia). Jokaiselle Ai:lle valitset Ai optimaalisesti. Tällä tavalla on mahdollista, että viimeisessä vaiheessa sinulla ei ole muuta valittavaa kuin hyväksyä viimeinen jäljellä oleva arvo.

Ahneissa päätöksissä on kaksi kriittistä osatekijää:

Ahne valinta. Voit valita, mikä ratkaisu on tällä hetkellä paras ja ratkaista sitten viimeisimmästä valinnasta syntyneen aliongelman. Ahneiden algoritmien valinta voi riippua aikaisemmista valinnoista. Mutta se ei voi riippua tulevasta valinnasta tai osaongelmien ratkaisuista. Algoritmi kehittyy tavalla, joka tekee valinnat silmukassa, samalla kutistaen annetun ongelman pienempiin osaongelmiin.
Optimaalinen alusrakenne. Teet optimaalisen alirakenteen ongelmalle, jos tämän ongelman optimaalinen ratkaisu sisältää optimaaliset ratkaisut sen aliongelmiin.

Ahneella algoritmilla on viisi osaa:

Joukko ehdokkaita, joista luoda ratkaisuja.
Valintatoiminto, jolla valitaan paras ehdokas ratkaisuun lisättäväksi.
Toteutettavan funktion avulla päätetään, voidaanko ehdokasta käyttää ratkaisun rakentamiseen.
Tavoitefunktio, joka määrittää ratkaisun tai epätäydellisen ratkaisun arvon.
Arviointitoiminto, joka osoittaa, kun löydät täydellisen ratkaisun.

Ahneen idea

Ensimmäisellä idealla sinulla on seuraavat Greedy Onen vaiheet:

Lajittele arvojen ei-nousevaan järjestykseen.
Harkitse puolestaan tilatut pakkaukset, laita harkittava paketti reppuun, jos reppun jäljellä oleva tilavuus riittää sen säilyttämiseen (mikä tarkoittaa, että reppuun laitettujen pakettien kokonaispaino ja harkitsevien pakettien paino eivät ylitä repun kapasiteetti).

Tämä ahne algoritmi ei kuitenkaan aina anna optimaalista ratkaisua. Tässä on vastaesimerkki:

Tehtävän parametrit ovat: n = 3; M = 19.
Paketit: {i = 1; W[i] = 14; V[i] = 20}; {i = 2; W[i] = 6; V[i] = 16}; {i = 3; W[i] = 10; V[i] = 8} -> Suuri arvo, mutta myös suuri paino.
Algoritmi valitsee paketin 1, jonka kokonaisarvo on 20, kun taas valitaan tehtävän optimaalinen ratkaisu (paketti 2, paketti 3), jonka kokonaisarvo on 24.

Idea Greedy Twosta

Toisella idealla sinulla on seuraavat Greedy Twon vaiheet:

Lajittele painojen mukaan ei-laskevaan järjestykseen.
Harkitse puolestaan tilatut pakkaukset, laita harkittava paketti reppuun, jos reppun jäljellä oleva tilavuus riittää sen säilyttämiseen (mikä tarkoittaa, että reppuun laitettujen pakettien kokonaispaino ja harkitsevien pakettien paino eivät ylitä repun kapasiteetti).

Tämä ahne algoritmi ei kuitenkaan aina anna optimaalista ratkaisua. Tässä on vastaesimerkki:

Tehtävän parametrit ovat: n = 3; M = 11.
Paketit: {i = 1; W[i] = 5; V[i] = 10}; {i = 2; W[i] = 6; V[i] = 16}; {i = 3; W[i] = 10; V[i] = 28} -> Kevyt, mutta arvo on myös erittäin kevyt.
Algoritmi valitsee (paketti 1, paketti 2) kokonaisarvolla 26, kun taas ongelman optimaalinen ratkaisu on (paketti 3) kokonaisarvolla 28.

Ahneen Kolmon idea

Kolmannella idealla sinulla on seuraavat Greedy Threen vaiheet. Itse asiassa tämä on yleisimmin käytetty algoritmi.

Lajittele pakkaukset yksikköhinnan arvon nousemattomaan järjestykseen . Sinulla on:

Harkitse puolestaan tilatut pakkaukset, laita harkittava paketti reppuun, jos reppun jäljellä oleva tilavuus riittää sen säilyttämiseen (mikä tarkoittaa, että reppuun laitettujen pakettien kokonaispaino ja harkitsevien pakettien paino eivät ylitä repun kapasiteetti).

Ajatus: Tämän ongelman ahne idea on laskea kunkin suhde . Lajittele sitten nämä suhteet laskevassa järjestyksessä. Valitset korkeimman paketti ja repun kapasiteetti voi sisältää kyseisen paketin (jäljelle > w_i). Joka kerta kun paketti laitetaan reppuun, se vähentää myös repun kapasiteettia.

Tapa valita paketit:

Harkitse yksikkökustannusten joukkoa. Valitset paketit alenevien yksikkökustannusten mukaan.

Oletetaan, että löysit osittaisen ratkaisun: (x₁,…, X_i).
Reppun arvo saadaan:

Reppuun asetettujen pakkausten painon mukaan:

Siksi reppun jäljellä oleva painoraja on:

Algoritmin vaiheet

Tämä on ongelma löytää max. Pakettiluettelo on lajiteltu yksikkökustannusten laskevaan järjestykseen haarautumisen huomioon ottamiseksi.

Vaihe 1: Solmun juuri edustaa repun alkutilaa, jossa et ole valinnut yhtään pakettia.
TotalValue = 0.
Juurisolmun yläraja UpperBound = M * Suurin yksikköhinta.
Vaihe 2: Solmun juurella on lapsisolmuja, jotka vastaavat kykyä valita paketti, jolla on suurin yksikköhinta. Laske kunkin solmun parametrit uudelleen:
TotalValue = TotalValue (vanha) + valittujen pakettien määrä * kunkin paketin arvo.
M = M (vanha) – valittujen pakettien lukumäärä * kunkin paketin paino.
UpperBound = TotalValue + M (uusi) * Pakatun yksikköhinta, joka otetaan huomioon seuraavaksi.
Vaihe 3: Lapsisolmuissa haaroitus asetetaan etusijalle solmulle, jolla on suurempi yläraja. Tämän solmun lapset vastaavat kykyä valita seuraava paketti, jolla on suuret yksikkökustannukset. Jokaisen solmun parametrit TotalValue, M, UpperBound on laskettava uudelleen vaiheessa 2 mainitun kaavan mukaisesti.
Vaihe 4: Toista vaihe 3 huomautuksen kanssa: jos solmujen yläraja on pienempi tai yhtä suuri kuin löydetyn vaihtoehdon tilapäinen enimmäishinta, sinun ei tarvitse enää haarautua kyseiselle solmulle.
Vaihe 5: Jos kaikki solmut ovat haarautuneita tai poikki, kallein vaihtoehto on etsiä.

Algoritmin pseudokoodi:

Fractional Knapsack (Array W, Array V, int M)
1. for i <- 1 to size (V)
2. 	calculate cost[i] <- V[i] / W[i]
3. Sort-Descending (cost)
4. i ← 1
5. while (i <= size(V))
6. 	if  W[i] <= M 
7.		M ← M – W[i]
8.		total ← total + V[i];
9. 	if  W[i] > M
10. 		i ← i+1

Algoritmin monimutkaisuus:

Jos käytetään yksinkertaista lajittelualgoritmia (valinta, kupla…), niin koko ongelman monimutkaisuus on O(n2).
Jos käytät pika- tai yhdistämislajittelua, koko ongelman monimutkaisuus on O(nlogn).

Java koodi Greedy Threelle

Ensin määrität luokan KnapsackPackage. Tällä luokalla on seuraavat ominaisuudet: kunkin paketin paino, arvo ja vastaava hinta. Tämän luokan omaisuuskustannuksia käytetään pääalgoritmin lajittelutehtävässä. Kunkin kulun arvo on kunkin paketin 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 = new Double(value / weight);
	}

	public double getWeight() {
		return weight;
	}

	public double getValue() {
		return value;
	}

	public Double getCost() {
		return cost;
	}

}

Luo sitten funktio suorittaaksesi algoritmin 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 kPackA, KnapsackPackage kPackB) {
			return kPackB.getCost().compareTo(kPackA.getCost());
		}
	});
	
	int remain = M;	
double result = 0d;
	
	int i = 0;
	boolean stopProc = false;
	while (!stopProc) {
		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());
		}
		
		if (packs[i].getWeight() > remain) {
			i ++;
		}
		
		if (i == n) {
			stopProc = true;
		}
	}
	
	System.out.println("Max Value:\t" + result);
}

Koodin selitys:

Alusta jokaisen reppupakkauksen paino ja arvo.
Lajittele reppupaketit hinnan mukaan laskevassa järjestyksessä.
Jos valitset paketin i.
Jos valitset paketin määrän i riittää.
Pysäytä, kun selaat kaikkia paketteja.

Tässä opetusohjelmassa on kaksi esimerkkiä. Tässä on java-koodi yllä olevan ohjelman suorittamiseksi kahdella esimerkillä:

public void run() {
	/*
	 * Pack and Weight - Value
	 */
//int W[] = new int[]{15, 10, 2, 4};
	int W[] = new int[]{12, 2, 1, 1, 4};
	
//int V[] = new int[]{30, 25, 2, 6};
	int V[] = new int[]{4, 2, 1, 2, 10};
	
	/*
	 * Max Weight
	 */
//int M = 37;
	int M = 15;
	int n = V.length;
	
	/*
	 * Run the algorithm
	 */
	knapsackGreProc(W, V, M, n);
}

Sinulla on tulos:

Ensimmäinen esimerkki:

Pack 0 - Weight 10.0 - Value 25.0
Pack 0 - Weight 10.0 - Value 25.0
Pack 0 - Weight 10.0 - Value 25.0
Pack 2 - Weight 4.0 - Value 6.0
Pack 3 - Weight 2.0 - Value 2.0
Max Value:	83.0

Toinen esimerkki:

Pack 0 - Weight 4.0 - Value 10.0
Pack 0 - Weight 4.0 - Value 10.0
Pack 0 - Weight 4.0 - Value 10.0
Pack 1 - Weight 1.0 - Value 2.0
Pack 1 - Weight 1.0 - Value 2.0
Pack 1 - Weight 1.0 - Value 2.0
Max Value:	36.0

Analysoi ensimmäistä esimerkkiä:

Tehtävän parametrit ovat: n = 4; M = 37.
Paketit: {i = 1; W[i] = 15; V[i] = 30; Hinta = 2.0}; {i = 2; W[i] = 10; V[i] = 25; Hinta = 2.5}; {i = 3; W[i] = 2; V[i] = 4; Hinta = 1.0}; {i = 4; W[i] = 4; V[i] = 6; Hinta = 1.5}.
Lajittelet pakkaukset yksikkökustannusten arvon nousun järjestykseen. Sinulla on: {i = 2} -> {i = 1} -> {i = 4} -> {i = 3}.

Ensimmäisen esimerkin algoritmin soveltamisen vaiheet:

Määritä x1, x2, x3, x4 on kunkin valitun paketin numero, joka vastaa pakettia {i = 2} -> {i = 1} -> {i = 4} -> {i = 3}.
Solmun juuri N edustaa tilaa, jossa et ole valinnut yhtään pakettia. Sitten:
- TotalValue = 0.
- M = 37 (ehdotuksen mukaisesti).
- Yläraja = 37 * 2.5 = 92.5, josta 37 on M ja 2.5 on paketin yksikköhinta {i = 2}.
Paketilla {i = 2} sinulla on 4 vaihtoehtoa: valitse 3 pakettia {i = 2} (x1 = 3); valitse 2 pakettia {i = 2} (x1 = 2); valitse 1 paketti {i = 2} (x1 = 1) äläkä valitse pakettia {i = 2} (x1 = 0). Näiden 4 mahdollisuuden mukaisesti haaroit juurisolmun N neljään aliryhmään N[4], N[1], N[2] ja N[3].
Lapsisolmulle N1 sinulla on:
- TotalValue = 0 + 3 * 25 = 75, jossa 3 on valitun paketin {i = 2} lukumäärä ja 25 on kunkin paketin {i = 2} arvo.
- M = 37 – 3 * 10 = 7, jossa 37 on repun alkumäärä, 3 on paketin lukumäärä {i = 2}, 10 on kunkin paketin paino {i = 2}.
- UpperBound = 75 + 7 * 2 = 89, jossa 75 on TotalValue, 7 on repun jäljellä oleva paino ja 2 on paketin yksikköhinta {i = 1}.
Vastaavasti voit laskea parametrit solmuille N[2], N[3] ja N[4], joissa yläraja on vastaavasti 84, 79 ja 74.
Solmujen N[1], N[2], N[3] ja N[4] joukosta solmulla N[1] on suurin yläraja, joten haaraat solmun N[1] ensin siinä toivossa, että siellä on hyvä suunnitelma tästä suunnasta.
Solmusta N[1] sinulla on vain yksi lapsisolmu N[1-1], joka vastaa x2 = 0 (reppun jäljellä olevan painon vuoksi on 7, kun taas kunkin paketin paino {i = 1} on 15) . Kun olet määrittänyt N[1-1]-painikkeen parametrit, N[1-1]:n yläraja on 85.5.
Jatka haaroittelua solmun N[1-1]. Solmulla N[1-1] on 2 lasta N[1-1-1] ja N[1-1-2], jotka vastaavat arvoja x3 = 1 ja x3 = 0. Kun olet määrittänyt parametrit näille kahdelle solmulle, näet, että N[1-1-1]:n yläraja on 84 ja N[1-1-2]:n yläraja on 82, joten jatkat solmun N[1-1-1] haarautumista.
Solmulla N[1-1-1] on kaksi lasta, N[1-1-1-1] ja N[1-1-1-2], jotka vastaavat x4 = 1 ja x4 = 0. Nämä ovat kaksi lehtisolmua (edustaa vaihtoehtoa), koska jokaiselle solmulle on valittu pakettien määrä. Missä solmussa N[1-1-1-1] edustaa vaihtoehtoa x1 = 3, x2 = 0, x3 = 1 ja x4 = 1 83:lle, kun taas solmu N[1-1-1-2] edustaa vaihtoehtoa x1 = 3, x2 = 0, x3 = 1 ja x4 = 01 81:ssä. Väliaikainen maksimiarvo on siis 83.
Kääntyessäsi takaisin solmuun N[1-1-2], näet, että N[1-1-2]:n yläraja on 82 < 83, joten trimmaat solmun N[1-1-2].
Kääntyessäsi takaisin solmuun N2, näet, että N2:n yläraja on 84 > 83, joten jatkat solmun N2 haarautumista. Solmulla N2 on kaksi lapsia N[2-1] ja N[2-2], jotka vastaavat x2 = 1 ja x2 = 0. Kun olet laskenut parametrit N[2-1] ja N[2-2], näet N[2-1]:n yläraja on 83 ja N[2-2]:n yläraja on 75.25. Kumpikaan näistä arvoista ei ole suurempi kuin 83, joten molemmat solmut leikataan.
Lopuksi myös solmut N3 ja N4 leikataan.
Joten kaikki puun solmut ovat haarautuneita tai leikattuja, joten paras väliaikainen ratkaisu on etsiä. Vastaavasti sinun on valittava 3 pakettia {i = 2}, 1 paketti {i = 4} ja yksi paketti {i = 3}, joiden kokonaisarvo on 83, kokonaispaino on 36.

Toisen esimerkin samalla analyysillä saat tuloksen: valitse paketti 4 (3 kertaa) ja paketti 5 (3 kertaa).

Python3 koodi Greedy Threelle

Ensin määrität luokan KnapsackPackage.

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

Luo sitten funktio suorittaaksesi algoritmin Greedy Three.

class FractionalKnapsack(object):
    def __init__(self):
        
    def knapsackGreProc(self, W, V, M, n):
        packs = []
        for i in range(n): 
            packs.append(KnapsackPackage(W[i], V[i]))
            
        packs.sort(reverse = True)
        
        remain = M
        result = 0
        
        i = 0
        stopProc = False
        
        while (stopProc != True):
            if (packs[i].weight <= remain):
                remain -= packs[i].weight;
                result += packs[i].value;
                
                print("Pack ", i, " - Weight ", packs[i].weight, " - Value ", packs[i].value)
            
            if (packs[i].weight > remain):
                i += 1
                
            if (i == n):
                stopProc = True            
        
        print("Max Value:\t", result)

Koodin selitys:

Alusta jokaisen reppupakkauksen paino ja arvo.
Lajittele reppupaketit hinnan mukaan laskevassa järjestyksessä.
Jos valitset paketin i.
Jos valitset paketin määrän i riittää.
Pysäytä, kun selaat kaikkia paketteja.

Tässä on Python3 koodia yllä olevan ohjelman suorittamiseksi ensimmäisen esimerkin kanssa:

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)

Sinulla on tulos:

Pack  0  - Weight  10  - Value  25
Pack  0  - Weight  10  - Value  25
Pack  0  - Weight  10  - Value  25
Pack  2  - Weight  4  - Value  6
Pack  3  - Weight  2  - Value  2
Max Value:	 83

C#-koodi Greedy Threeille

Ensin määrität luokan 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 = (double) value / weight;
        }

        public double Weight
        {
            get { return weight; }
        }

        public double Value
        {
            get { return value; }
        }

        public double Cost
        {
            get { return cost; }
        }
    }
}

Luo sitten funktio suorittaaksesi algoritmin Greedy Three.

using System;
namespace KnapsackProblem
{
    public class FractionalKnapsack
    {
        public FractionalKnapsack()
        {
        }

        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, new Comparison<KnapsackPackage>(
                 (kPackA, kPackB) => kPackB.Cost.CompareTo(kPackA.Cost)));

            double remain = M;
            double result = 0d;

            int i = 0;
            bool stopProc = false;

            while (!stopProc)
            {
                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);
                }

                if (packs[i].Weight > remain)
                {
                    i++;
                }

                if (i == n)
                {
                    stopProc = true;
                }
            }

            Console.WriteLine("Max Value:\t" + result);
        }        
    }
}

Koodin selitys:

Alusta jokaisen reppupakkauksen paino ja arvo.
Lajittele reppupaketit hinnan mukaan laskevassa järjestyksessä.
Jos valitset paketin i.
Jos valitset paketin määrän i riittää.
Pysäytä, kun selaat kaikkia paketteja.

Tässä on C#-koodi yllä olevan ohjelman suorittamiseksi ensimmäisellä esimerkillä:

public void run()
{
    /*
     * Pack and Weight - Value
     */
    int[] W = new int[]{15, 10, 2, 4};
    //int[] W = new int[] { 12, 2, 1, 1, 4 };

    int[] V = new int[]{30, 25, 2, 6};
    //int[] V = new int[] { 4, 2, 1, 2, 10 };

    /*
     * Max Weight
     */
    int M = 37;
    //int M = 15;
    int n = V.Length;

    /*
     * Run the algorithm
     */
    KnapsackGreProc(W, V, M, n);
}

Sinulla on tulos:

Pack 0 - Weight 10 - Value 25
Pack 0 - Weight 10 - Value 25
Pack 0 - Weight 10 - Value 25
Pack 2 - Weight 4 - Value 6
Pack 3 - Weight 2 - Value 2
Max Value:	83

Vastaesimerkki Greedy Threesta

Greedy Threen algoritmi ratkaisee nopeasti ja voi myös olla optimaalinen joissakin tapauksissa. Joissakin erikoistapauksissa se ei kuitenkaan anna optimaalista ratkaisua. Tässä on vastaesimerkki:

Tehtävän parametrit ovat: n = 3; M = 10.
Paketit: {i = 1; W[i] = 7; V[i] = 9; Hinta = 9/7}; {i = 2; W[i] = 6; V[i] = 6; Hinta = 1}; {i = 3; W[i] = 4; V[i] = 4; Hinta = 1}.
Algoritmi valitsee (paketti 1) kokonaisarvolla 9, kun taas ongelman optimaalinen ratkaisu on (paketti 2, paketti 3) kokonaisarvolla 10.

Tässä on java-koodi yllä olevan ohjelman suorittamiseksi vastaesimerkillä:

public void run() {
	/*
	 * Pack and Weight - Value
	 */
	int W[] = new int[]{7, 6, 4};
	
	int V[] = new int[]{9, 6, 4};
	
	/*
	 * Max Weight
	 */
	int M = 10;
	int n = V.length;
	
	/*
	 * Run the algorithm
	 */
	knapsackGreProc(W, V, M, n);
}

Tässä on tulos:

Pack 0 - Weight 7.0 - Value 9.0
Max Value:	9.0

Siinä kaikki Fractional Knapsack -ongelmaan.

Saatat tykätä:

Mikä on ahne strategia?

Ahneen idea

Idea Greedy Twosta

AIHEESEEN LIITTYVÄT ARTIKKELIT

Ahneen Kolmon idea

Algoritmin vaiheet

Java koodi Greedy Threelle

Python3 koodi Greedy Threelle

C#-koodi Greedy Threeille

Vastaesimerkki Greedy Threesta

AIHEESEEN LIITTYVÄT ARTIKKELIT