Ułamkowy problem plecakowy: algorytm zachłanny z przykładem

Czym jest zachłanna strategia?

Algorytmy zachłanne Wybierają najlepszą lokalną opcję na każdym etapie, mając nadzieję, że łańcuch lokalnych optimów doprowadzi do globalnie optymalnego rozwiązania. Podobnie jak w programowaniu dynamicznym, koncentrują się na problemach optymalizacyjnych, ale nigdy nie wracają do wcześniejszych decyzji, aby je ponownie rozważyć.

Algorytmy zachłanne są zazwyczaj proste w pisaniu, szybkie (często liniowe lub kwadratowe), łatwe do debugowania i mało pamięciochłonne. Kompromisem jest to, że wynik nie zawsze jest optymalny, dlatego strategia ta sprawdza się tylko w przypadku problemów o sprawdzonej, bezpiecznej dla zachłanności strukturze.

Strategie zachłanne rozwiązują optymalizację kombinatoryczną, budując rozwiązanie A, po jednym komponencie Ai na raz. Na każdym kroku wybierasz Ai optymalnie w ramach bieżących ograniczeń i redukujesz problem do mniejszego podproblemu.

Aby metoda chciwa była poprawna, muszą być spełnione dwie właściwości:

1. Własność wyboru chciwego: Lokalne optimum na każdym etapie prowadzi do globalnego optimum. Wybór zależy od decyzji z przeszłości, ale nie od decyzji z przyszłości.
2. Optymalna podbudowa: optymalne rozwiązanie całego problemu zawiera optymalne rozwiązania jego podproblemów.

Algorytm zachłanny składa się z pięciu elementów:

1. Zbiór kandydatów, na podstawie którego tworzone są rozwiązania.
2. Funkcja selekcji wybierająca najlepszego kolejnego kandydata.
3. Funkcja wykonalności sprawdzająca, czy kandydat może rozszerzyć bieżące częściowe rozwiązanie.
4. Funkcja celu, która ocenia rozwiązanie całkowite lub częściowe.
5. Funkcja oceny sygnalizująca zakończenie rozwiązania.

Idea chciwego

Greedy One sortuje pakiety wyłącznie według wartości:

• Sortuj pakiety w kolejności nierosnącej według wartości.
• Przejrzyj posortowaną listę i dodaj każdą paczkę do plecaka, jeśli jest w nim wystarczająco dużo miejsca.

Ta reguła nie zawsze daje optymalną odpowiedź. Kontrprzykład:

• Parametry: n = 3, M = 19.
• Pakiety: {i = 1; W = 14; V = 20}, {i = 2; W = 6; V = 16}, {i = 3; W = 10; V = 8} — duża wartość, ale także duża waga.
• Łakomy wybiera pakiet 1 o łącznej wartości 20, podczas gdy optymalny wybór (pakiet 2, pakiet 3) sięga 24.

Pomysł Chciwej Dwójki

Greedy Two sortuje paczki wyłącznie według wagi:

• Sortuj paczki w kolejności niemalejącej według wagi.
• Przejrzyj posortowaną listę i dodaj każdą paczkę do plecaka, jeśli jest w nim wystarczająco dużo miejsca.

Ta reguła również nie jest optymalna. Kontrprzykład:

• Parametry: n = 3, M = 11.
• Opakowania: {i = 1; W = 5; V = 10}, {i = 2; W = 6; V = 16}, {i = 3; W = 10; V = 28} — lekkie, ale o małej wartości.
• Greedy Two wybiera (pakiet 1, pakiet 2) o łącznej wartości 26, podczas gdy optymalny wybór (pakiet 3) osiąga wartość 28.

Idea Chciwej Trójki

Greedy Three naprawia obie awarie, łącząc wartość i wagę w jeden klucz rankingowy. Jest to standardowa metoda rozwiązywania problemu plecakowego ułamkowego.

• Oblicz koszt jednostkowy V[i] / W[i] dla każdego pakietu.
• Sortuj pakiety w kolejności nierosnącej według kosztu jednostkowego.
• Przejrzyj posortowaną listę i dodaj każdy pakiet, jeśli jest w stanie go pomieścić.

Chciwy Trzy sortuje według kosztu jednostkowego V[i] / W[i]

Idea: oblicz stosunek wartości do wagi V[i] / W[i] dla każdego pakietu, posortuj w kolejności malejącej i najpierw weź największy dostępny stosunek, aż plecak się zapełni.

Dla prawdy Frakcyjny Wariant: gdy kolejny pakiet nie mieści się w całości, należy wziąć ułamek, który dokładnie wypełnia pozostałą pojemność. Ta dodatkowa zasada sprawia, że ​​Greedy Three jest prawdopodobnie optymalnym rozwiązaniem w przypadku Fractional Knapsack.

Kroki algorytmu

W przypadku wariantu rozgałęzienia i ograniczenia 0/1 posortowana lista kosztów jednostkowych napędza drzewo wyszukiwania:

• Krok 1: Węzeł główny reprezentuje pusty plecak. Wartość całkowita = 0. Górna granica = M × maksymalny koszt jednostkowy.
• Krok 2: Rozgałęzienie pierwiastka, określając liczbę kopii pakietu o największym stosunku, jakie może pomieścić. Dla każdego elementu podrzędnego przelicz wartość całkowitą (TotalValue), pozostałą pojemność (M) i granicę górną (UpperBound).
• Krok 3: Najpierw rozwiń dziecko z największą granicą górną, mając nadzieję na szybkie znalezienie mocnego rozwiązania.
• Krok 4: Usuń każdy węzeł, którego UpperBound nie jest lepszy od najlepszego aktualnego kompletnego rozwiązania.
• Krok 5: Gdy każdy węzeł zostanie rozszerzony lub przycięty, najlepsze obecne kompletne rozwiązanie staje się optymalne.

Pseudokod czystego algorytmu zachłannego Fractional Knapsack:

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

Złożoność algorytmu:

• Używając sortowania prostego (selekcja lub bąbelkowego): O(n²).
• Użycie sortowania szybkiego lub sortowania przez scalanie: O(n log n), zdominowane przez krok sortowania.

Java Code dla Chciwej Trójki

Zdefiniuj KnapsackPackage klasa z wagą, wartością i kosztem pochodnym (stosunek V/W używany do sortowania):

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

Następnie utwórz funkcję implementującą 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 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);
}

Funkcja plecakGreProc() w Java

Wyjaśnienie kodu:

1. Zawiń każdy element wejściowy w KnapsackPackage więc klucz sortowania (stosunek V/W) jest obliczony wcześniej.
2. Sortuj malejąco według kosztów.
3. Jeśli się zmieści, zabierz każde opakowanie w całości.
4. Użyj części następnego opakowania, aby zapełnić pozostałą pojemność.
5. Zatrzymaj się, gdy pozostała pojemność spadnie do zera.

Poprawka: oryginalny Java pętla zaawansowana i tylko wtedy, gdy paczka się nie zmieściła, co powodowało wielokrotne pobieranie tej samej paczki. Powyższa wersja przesuwa o jedną paczkę na iterację i dodaje krok wypełniania częściowego, spełniając prawdziwą regułę ułamkowego plecaka.

Java sterownik, który uruchamia algorytm na przykładzie działania:

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 dla Chciwej Trójki

Najpierw zdefiniuj KnapsackPackage klasa. Plik __lt__ Metoda ta umożliwia bezpośrednie sortowanie według kosztu:

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

Następnie wdróż procedurę Fractional Knapsack:

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)

Funkcja plecakGreProc() w Python

Poprawka: oryginalny Python klasa zdefiniowała pustą __init__ bez ciała, które podnosi IndentationErrorPowyższa wersja usuwa pusty konstruktor, ponieważ nie jest on potrzebny.

Sterownik, który uruchamia algorytm w pierwszym przykładzie:

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 dla Chciwej Trójki

Zdefiniuj KnapsackPackage klasa:

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

Implementacja metody Greedy Three z krokiem wypełniania ułamkowego:

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

Funkcja KnapsackGreProc() w C#

Kontrprzykład: Chciwa Trójka na 0/1 Plecak

Chciwa Trójka jest optymalna dla wariantu Frakcyjnego, ale w Plecaku 0/1 (gdzie przedmioty nie mogą być rozdzielane) może być pokonana. Kontrprzykład:

• Parametry: n = 3, M = 10.
• Pakiety: {i = 1; W = 7; V = 9; koszt = 9/7}, {i = 2; W = 6; V = 6; koszt = 1}, {i = 3; W = 4; V = 4; koszt = 1}.
• Greedy Three wybiera pakiet 1 za łączną wartość 9, podczas gdy optymalny wybór 0/1 (pakiet 2, pakiet 3) osiąga wartość 10.

Lekcja: używaj Greedy Three tylko wtedy, gdy dozwolone są ułamki. W wariancie 0/1 użyj Programowanie dynamiczne zamiast.

Zastosowania plecaka frakcyjnego

• Załadunek towarów, w przypadku których możliwe jest podzielenie ich według wagi w stanie płynnym, sproszkowanym lub masowym.
• Alokacja portfela w ramach opcji inwestycyjnych akceptujących częściowe finansowanie.
• Współdzielenie pasma chmury, w którym przepływy mogą zużywać ułamek łącza.
• Harmonogramowanie procesora w modelu współdzielonego przedziału czasowego z podzielnymi obciążeniami.
• Alokacja zasobów sztucznej inteligencji, w której zadanie szkoleniowe może wykorzystać ułamek mocy obliczeniowej procesora GPU.

FAQ