Problém frakčního batohu: Chamtivý algoritmus s příkladem

Co je to Greedy Strategy?

Chamtivé algoritmy jsou jako algoritmy dynamického programování, které se často používají k řešení optimálních problémů (hledání nejlepších řešení problému podle konkrétního kritéria).

Chamtivé algoritmy implementují optimální místní výběry v naději, že tyto výběry povedou k optimálnímu globálnímu řešení problému, který má být vyřešen. Chamtivé algoritmy často nejsou příliš těžké na nastavení, jsou rychlé (časová složitost je často lineární funkce nebo do značné míry funkce druhého řádu). Kromě toho tyto programy není těžké ladit a využívají méně paměti. Ale výsledky nejsou vždy optimálním řešením.

K vyřešení problému kombinatorické optimalizace se často používají chamtivé strategie vytvořením možnosti A. Možnost A je konstruována výběrem každé složky Ai z A, dokud není dokončena (dostatek n složek). Pro každou Ai zvolíte Ai optimálně. Tímto způsobem je možné, že v posledním kroku nemáte na výběr nic jiného, než přijmout poslední zbývající hodnotu.

Existují dvě kritické složky chamtivých rozhodnutí:

Způsob zištného výběru. Můžete si vybrat, které řešení je v současnosti nejlepší, a poté vyřešit dílčí problém vyplývající z posledního výběru. Výběr zištných algoritmů může záviset na předchozích výběrech. Ale nemůže to záviset na nějakém budoucím výběru nebo v závislosti na řešení dílčích problémů. Algoritmus se vyvíjí způsobem, který provádí výběry ve smyčce a zároveň zmenšuje daný problém na menší dílčí problémy.
Optimální spodní konstrukce. Optimální podstrukturu pro problém provedete, pokud optimální řešení tohoto problému obsahuje optimální řešení jeho podproblémů.

Chamtivý algoritmus má pět složek:

Sada kandidátů, ze kterých lze vytvářet řešení.
Funkce výběru pro výběr nejlepšího kandidáta pro přidání do řešení.
Pro rozhodnutí, zda lze kandidáta použít k sestavení řešení, se používá proveditelná funkce.
Objektivní funkce, fixující hodnotu řešení nebo neúplného řešení.
Vyhodnocovací funkce, která ukazuje, kdy najdete kompletní řešení.

Nápad Greedy One

S prvním nápadem máte následující kroky Greedy One:

Seřadit v nerostoucím pořadí hodnot.
Následně zvažte objednané balíky, uvažovaný balík vložte do batohu, pokud zbývající kapacita batohu postačí k jeho uložení (to znamená, že celková hmotnost balíčků, které byly do batohu vloženy, a hmotnost uvažovaných balíčků nepřesahují kapacita batohu).

Tento chamtivý algoritmus však ne vždy poskytuje optimální řešení. Zde máte protipříklad:

Parametry problému jsou: n = 3; M = 19.
Balíčky: {i = 1; W[i] = 14; V[i] = 20}; {i = 2; W[i] = 6; V[i] = 16}; {i = 3; W[i] = 10; V[i] = 8} -> Skvělá hodnota, ale také velká hmotnost.
Algoritmus vybere balíček 1 s celkovou hodnotou 20, přičemž je vybráno optimální řešení problému (balíček 2, balíček 3) s celkovou hodnotou 24.

Myšlenka chamtivé dvojky

S druhým nápadem máte následující kroky Greedy Two:

Seřaďte v neklesajícím pořadí hmotností.
Následně zvažte objednané balíky, uvažovaný balík vložte do batohu, pokud zbývající kapacita batohu postačí k jeho uložení (to znamená, že celková hmotnost balíčků, které byly do batohu vloženy, a hmotnost uvažovaných balíčků nepřesahují kapacita batohu).

Tento chamtivý algoritmus však ne vždy poskytuje optimální řešení. Zde máte protipříklad:

Parametry problému jsou: n = 3; M = 11.
Balíčky: {i = 1; W[i] = 5; V[i] = 10}; {i = 2; W[i] = 6; V[i] = 16}; {i = 3; W[i] = 10; V[i] = 28} -> Nízká hmotnost, ale hodnota je také velmi nízká.
Algoritmus vybere (balíček 1, balíček 2) s celkovou hodnotou 26, přičemž optimální řešení problému je (balíček 3) s celkovou hodnotou 28.

Myšlenka chamtivé trojky

S třetím nápadem máte následující kroky Greedy Three. Ve skutečnosti se jedná o nejpoužívanější algoritmus.

Seřaďte balíčky v pořadí nezvyšování hodnoty jednotkových nákladů . Ty máš:

Následně zvažte objednané balíky, uvažovaný balík vložte do batohu, pokud zbývající kapacita batohu postačí k jeho uložení (to znamená, že celková hmotnost balíčků, které byly do batohu vloženy, a hmotnost uvažovaných balíčků nepřesahují kapacita batohu).

Nápad: Chamtivou myšlenkou tohoto problému je vypočítat poměr každého . Poté tyto poměry seřaďte sestupně. Vyberete si tu nejvyšší balíček a kapacita batohu může obsahovat tento balíček (zbývají > w_i). Pokaždé, když se do batohu vloží balíček, sníží se také kapacita batohu.

Způsob výběru balíčků:

Zvažte rozsah jednotkových nákladů. Balíčky vybíráte podle klesajících jednotkových nákladů.

Předpokládejme, že jste našli částečné řešení: (x₁,…, X_i).
Hodnota batohu se získá:

Odpovídající hmotnosti balíků, které byly vloženy do batohu:

Zbývající hmotnostní limit batohu je tedy:

Kroky algoritmu

Vidíte, že je problém najít max. Seznam balíčků je řazen sestupně podle jednotkových nákladů, aby bylo možné zvážit větvení.

Krok 1: Kořen uzlu představuje počáteční stav batohu, kde jste nevybrali žádný balíček.
Celková hodnota = 0.
Horní hranice kořenového uzlu Horní hranice = M * Maximální jednotkové náklady.
Krok 2: Kořen uzlu bude mít podřízené uzly odpovídající možnosti vybrat balíček s největší jednotkovou cenou. Pro každý uzel přepočítáte parametry:
TotalValue = TotalValue (staré) + počet vybraných balíčků * hodnota každého balíčku.
M = M (staré) – počet vybraných balíků * hmotnost každého balíku.
Horní hranice = Celková hodnota + M (nové) * Jednotková cena zabaleného zboží, která se má vzít v úvahu jako další.
Krok 3: V podřízených uzlech upřednostníte větvení pro uzel s větší horní hranicí. Potomci tohoto uzlu odpovídají schopnosti vybrat další balíček s velkou jednotkovou cenou. Pro každý uzel musíte přepočítat parametry TotalValue, M, UpperBound podle vzorce uvedeného v kroku 2.
Krok 4: Opakujte krok 3 s poznámkou: pro uzly, jejichž horní mez je nižší nebo se rovná dočasné maximální ceně nalezené možnosti, již pro tento uzel nemusíte větvit.
Krok 5: Pokud jsou všechny uzly rozvětvené nebo odříznuté, je nejdražší varianta, kterou je třeba hledat.

Pseudokód pro algoritmus:

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

Složitost algoritmu:

Při použití jednoduchého třídícího algoritmu (výběr, bublina…) je složitost celého problému O(n2).
Pokud používáte rychlé třídění nebo slučovací třídění, pak je složitost celého problému O(nlogn).

Java kód pro Greedy Three

Nejprve definujete třídu KnapsackPackage. Tato třída má vlastnosti: hmotnost, hodnotu a odpovídající cenu každého balíčku. Cena vlastnosti této třídy se používá pro úlohu řazení v hlavním algoritmu. Hodnota každého nákladu je poměr každého balení.

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

}

Poté vytvoříte funkci pro provedení algoritmu 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);
}

Vysvětlení kódu:

Inicializujte hmotnost a hodnotu každého batohu.
Seřaďte balíčky batohů podle ceny sestupně.
Pokud zvolíte balíček i.
Pokud zvolíte počet balení, stačí i.
Zastavte se při procházení všech balíčků.

V tomto tutoriálu máte dva příklady. Zde je kód java pro spuštění výše uvedeného programu se dvěma příklady:

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

Máte výstup:

První příklad:

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

Druhý příklad:

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

Analyzujte první příklad:

Parametry problému jsou: n = 4; M = 37.
Balíčky: {i = 1; W[i] = 15; V[i] = 30; Cena = 2.0}; {i = 2; W[i] = 10; V[i] = 25; Cena = 2.5}; {i = 3; W[i] = 2; V[i] = 4; Cena = 1.0}; {i = 4; W[i] = 4; V[i] = 6; Cena = 1.5}.
Balíčky třídíte v pořadí bez zvýšení hodnoty jednotkových nákladů. Máte: {i = 2} -> {i = 1} -> {i = 4} -> {i = 3}.

Kroky pro použití algoritmu pro první příklad:

Definujte x1, x2, x3, x4 je číslo každého vybraného balíčku, odpovídající balíčku {i = 2} -> {i = 1} -> {i = 4} -> {i = 3}.
Kořen uzlu N představuje stav, kdy jste nevybrali žádný balíček. Pak:
- Celková hodnota = 0.
- M = 37 (jak je navrženo).
- Horní hranice = 37 * 2.5 = 92.5, z toho 37 je M a 2.5 je jednotková cena balíčku {i = 2}.
S balíčkem {i = 2} máte 4 možnosti: vyberte 3 balíčky {i = 2} (x1 = 3); vyberte 2 balíček {i = 2} (x1 = 2); vyberte 1 balíček {i = 2} (x1 = 1) a nevyberte balíček {i = 2} (x1 = 0). V souladu s těmito 4 možnostmi rozvětvíte kořenový uzel N na 4 potomky N[1], N[2], N[3] a N[4].
Pro podřízený uzel N1 máte:
- TotalValue = 0 + 3 * 25 = 75, kde 3 je počet vybraných balíků {i = 2} a 25 je hodnota každého balíku {i = 2}.
- M = 37 – 3 * 10 = 7, kde 37 je počáteční množství batohu, 3 je počet balení {i = 2}, 10 je hmotnost každého balení {i = 2}.
- Horní hranice = 75 + 7 * 2 = 89, kde 75 je celková hodnota, 7 je zbývající hmotnost batohu a 2 je jednotková cena balíčku {i = 1}.
Podobně můžete vypočítat parametry pro uzly N[2], N[3] a N[4], ve kterých je horní hranice 84, 79 a 74.
Mezi uzly N[1], N[2], N[3] a N[4] má uzel N[1] největší UpperBound, takže nejprve rozvětvíte uzel N[1] v naději, že tam bude z tohoto směru dobrý plán.
Z uzlu N[1] máte pouze jeden podřízený uzel N[1-1] odpovídající x2 = 0 (vzhledem k zbývající hmotnosti batohu je 7, přičemž hmotnost každého balíčku {i = 1} je 15) . Po určení parametrů pro tlačítko N[1-1] máte horní hranici N[1-1] 85.5.
Pokračujete větvením uzlu N[1-1]. Uzel N[1-1] má 2 potomky N[1-1-1] a N[1-1-2] odpovídající x3 = 1 a x3 = 0. Po určení parametrů pro tyto dva uzly vidíte, že Horní hranice N[1-1-1] je 84 a N[1-1-2] je 82, takže pokračujete ve větvení uzlu N[1-1-1].
Uzel N[1-1-1] má dva potomky, N[1-1-1-1] a N[1-1-1-2], což odpovídá x4 = 1 a x4 = 0. Jedná se o dva listové uzly (představuje možnost), protože pro každý uzel byl vybrán počet balíčků. Ve kterém uzel N[1-1-1-1] představuje možnost x1 = 3, x2 = 0, x3 = 1 a x4 = 1 pro 83, zatímco uzel N[1-1-1-2] představuje možnost x1 = 3, x2 = 0, x3 = 1 a x4 = 01 na 81. Dočasná maximální hodnota je zde tedy 83.
Když se vrátíte zpět k uzlu N[1-1-2], uvidíte, že horní hranice N[1-1-2] je 82 < 83, takže uzel N[1-1-2] oříznete.
Když se vrátíte zpět k uzlu N2, uvidíte, že horní hranice N2 je 84 > 83, takže pokračujete ve větvení uzlu N2. Uzel N2 má dva potomky N[2-1] a N[2-2] odpovídající x2 = 1 a x2 = 0. Po výpočtu parametrů pro N[2-1] a N[2-2] uvidíte horní hranice N[2-1] je 83 a horní hranice N[2-2] je 75.25. Žádná z těchto hodnot není větší než 83, takže jsou oříznuty oba uzly.
Nakonec jsou také oříznuty uzly N3 a N4.
Takže všechny uzly na stromě jsou rozvětvené nebo oříznuté, takže nejlepší dočasné řešení je to, které je třeba hledat. Podle toho je třeba vybrat 3 balíčky {i = 2}, 1 balíček {i = 4} a jeden balíček {i = 3} v celkové hodnotě 83, celková hmotnost je 36.

Se stejnou analýzou druhého příkladu máte výsledek: vyberte balíček 4 (3krát) a balíček 5 (3krát).

Python3 kód pro Greedy Three

Nejprve definujete třídu 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

Poté vytvoříte funkci pro provedení algoritmu 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)

Vysvětlení kódu:

Inicializujte hmotnost a hodnotu každého batohu.
Seřaďte balíčky batohů podle ceny sestupně.
Pokud zvolíte balíček i.
Pokud zvolíte počet balení, stačí i.
Zastavte se při procházení všech balíčků.

Zde je Python3 kód pro spuštění výše uvedeného programu s prvním příkladem:

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)

Máte výstup:

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# kód pro Greedy Three

Nejprve definujete třídu 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; }
        }
    }
}

Poté vytvoříte funkci pro provedení algoritmu 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);
        }        
    }
}

Vysvětlení kódu:

Inicializujte hmotnost a hodnotu každého batohu.
Seřaďte balíčky batohů podle ceny sestupně.
Pokud zvolíte balíček i.
Pokud zvolíte počet balení, stačí i.
Zastavte se při procházení všech balíčků.

Zde je kód C# pro spuštění výše uvedeného programu s prvním příkladem:

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

Máte výstup:

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

Protipříklad Greedy Three

Algoritmus Greedy Three se vyřeší rychle a v některých případech může být také optimální. V některých speciálních případech však nedává optimální řešení. Zde máte protipříklad:

Parametry problému jsou: n = 3; M = 10.
Balíčky: {i = 1; W[i] = 7; V[i] = 9; Cena = 9/7}; {i = 2; W[i] = 6; V[i] = 6; Cena = 1}; {i = 3; W[i] = 4; V[i] = 4; Cena = 1}.
Algoritmus vybere (balíček 1) s celkovou hodnotou 9, přičemž optimální řešení problému je (balíček 2, balíček 3) s celkovou hodnotou 10.

Zde je kód java pro spuštění výše uvedeného programu s příkladem počítadla:

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

Zde je výsledek:

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

To je vše k problému frakčního batohu.

Co je to Greedy Strategy?

Nápad Greedy One

Myšlenka chamtivé dvojky

SOUVISEJÍCÍ ČLÁNKY

Myšlenka chamtivé trojky

Kroky algoritmu

Java kód pro Greedy Three

Python3 kód pro Greedy Three

C# kód pro Greedy Three

Protipříklad Greedy Three

SOUVISEJÍCÍ ČLÁNKY

Přihlaste se k odběru newsletteru