Kesirli Sırt Çantası Problemi: Örnekli Açgözlü Algoritma

Açgözlü Strateji Nedir?

açgözlü algoritmalar Her adımda en iyi yerel seçeneği belirleyerek, bir dizi yerel optimumun küresel olarak en iyi çözümü üretmesini umarlar. Dinamik Programlama gibi, optimizasyon problemlerini hedeflerler, ancak daha önceki kararları yeniden değerlendirmek için asla geriye bakmazlar.

Açgözlü algoritmalar genellikle yazması basit, hızlı (çoğunlukla doğrusal veya karesel zamanlı), hata ayıklaması kolay ve bellek kullanımında hafiftir. Dezavantajı ise sonucun her zaman optimal olmamasıdır; bu nedenle strateji yalnızca kanıtlanmış açgözlü güvenli bir yapıya sahip problemler için işe yarar.

Açgözlü stratejiler, bir çözüm A'yı her seferinde bir bileşen Ai oluşturarak kombinatoryal optimizasyonu çözer. Her adımda, mevcut kısıtlamalar altında en uygun Ai'yi seçer ve problemi daha küçük bir alt probleme indirgersiniz.

Açgözlü bir yöntemin doğru olması için iki özelliğin sağlanması gerekir:

1. Açgözlü seçim özelliği: Her adımda yerel bir optimum, küresel bir optimuma yol açar. Seçim geçmiş kararlara bağlıdır, ancak gelecekteki kararlara bağlı değildir.
2. Optimal alt yapı: Bütün problemin en uygun çözümü, alt problemlerinin en uygun çözümlerini de içerir.

Açgözlü bir algoritmanın beş bileşeni vardır:

1. Çözümlerin oluşturulduğu aday kümesi.
2. Bir sonraki en iyi adayı seçen bir seçim fonksiyonu.
3. Bir adayın mevcut kısmi çözümü genişletip genişletemeyeceğini kontrol eden bir fizibilite fonksiyonu.
4. Tam veya kısmi çözümü değerlendiren bir amaç fonksiyonu.
5. Çözümün tamamlandığını bildiren bir değerlendirme fonksiyonu.

Açgözlü Bir Fikri

Greedy One paketleri yalnızca değerine göre sıralar:

• Paketleri değerlerine göre azalan sırada sıralayın.
• Sıralanmış listede gezinin ve kalan kapasite yetiyorsa her paketi sırt çantasına ekleyin.

Bu kural her zaman en iyi sonucu vermez. Karşı örnek:

• Parametreler: n = 3, M = 19.
• Paketler: {i = 1; W = 14; V = 20}, {i = 2; W = 6; V = 16}, {i = 3; W = 10; V = 8} — yüksek değere sahip ancak aynı zamanda yüksek ağırlığa sahip.
• Açgözlü oyuncu toplam değeri 20 olan 1 numaralı paketi seçerken, en uygun seçim (2 numaralı paket, 3 numaralı paket) 24'e ulaşır.

Açgözlü İki Fikri

Greedy Two paketleri yalnızca ağırlığa göre sıralar:

• Paketleri ağırlıklarına göre artmayan sırada sıralayın.
• Sıralanmış listede gezinin ve kalan kapasite yetiyorsa her paketi sırt çantasına ekleyin.

Bu kural da en uygun kural olmaktan uzaktır. Karşı örnek:

• Parametreler: n = 3, M = 11.
• Paketler: {i = 1; W = 5; V = 10}, {i = 2; W = 6; V = 16}, {i = 3; W = 10; V = 28} — hafif ancak düşük değerli.
• Açgözlü algoritma, toplam değeri 26 olan iki paket (paket 1, paket 2) seçerken, en uygun seçim (paket 3) 28'e ulaşır.

Açgözlü Üçlü Fikri

Açgözlü Üç algoritması, değer ve ağırlığı tek bir sıralama anahtarında birleştirerek her iki hatayı da giderir. Kesirli Sırt Çantası Problemi için standart yöntemdir.

• Her paket için birim maliyeti V[i] / W[i] hesaplayın.
• Paketleri birim maliyetine göre azalan sırada sıralayın.
• Sıralanmış listede gezinin ve kalan kapasite yetiyorsa her paketi ekleyin.

Açgözlü Üçlü, birim maliyetine göre sıralar V[i] / W[i]

Fikir: Her paket için değer-ağırlık oranı V[i] / W[i]'yi hesaplayın, azalan sırada sıralayın ve çanta dolana kadar en büyük oranı önce alın.

Gerçek için kesirli Bir sonraki paket tam olarak sığmadığında, kalan kapasiteyi tam olarak dolduracak bir kesir alın. Bu ek kural, Açgözlü Üçlü'yü Kesirli Sırt Çantası oyununda kanıtlanabilir şekilde en iyi seçenek haline getiriyor.

Algoritmanın Adımları

0/1 dallanma ve sınırlandırma varyantı için, sıralanmış birim maliyet listesi bir arama ağacını yönlendirir:

• 1 Adım: Kök düğüm boş bir sırt çantasını temsil eder. Toplam Değer = 0. Üst Sınır = M × maksimum birim maliyet.
• 2 Adım: Kökü, en büyük oranlı paketin kaç kopyasının sığabileceğine göre dallandırın. Her alt dal için, ToplamDeğer, kalan kapasite M ve ÜstSınırı yeniden hesaplayın.
• 3 Adım: En büyük Üst Sınır değerine sahip alt grubu önce genişleterek, hızlı bir şekilde güçlü bir çözüm bulmayı umuyoruz.
• 4 Adım: Üst sınırı mevcut en iyi tam çözümden daha iyi olmayan tüm düğümleri budayın.
• 5 Adım: Her düğüm genişletildiğinde veya budandığında, mevcut en iyi tam çözüm en uygun çözümdür.

Saf Kesirli Sırt Çantası açgözlü algoritması için sözde kod:

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

Algoritmanın karmaşıklığı:

• Basit bir sıralama yöntemi kullanarak (seçim veya kabarcık sıralama): O(n²).
• Hızlı sıralama veya birleştirme sıralaması kullanıldığında: O(n log n), sıralama adımı baskındır.

Java Code Açgözlü Üçlü için

Tanımlamak KnapsackPackage Ağırlık, değer ve türetilmiş maliyete sahip sınıf (sıralama için kullanılan V/W oranı):

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

Ardından Greedy Three'ü uygulayan fonksiyonu oluşturun:

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

Sırt çantasıGreProc() işlevi Java

Kodun açıklaması:

1. Her girdiyi şu şekilde sarın: KnapsackPackage Bu nedenle sıralama anahtarı (V/W oranı) önceden hesaplanır.
2. Maliyet sırasına göre azalan şekilde sıralayın.
3. Her paket sığıyorsa, tamamını bütün olarak alın.
4. Kalan kapasiteyi doldurmak için bir sonraki paketin bir kısmını alın.
5. Kalan kapasite sıfıra ulaştığı anda durdurun.

Düzeltme notu: Orijinal Java gelişmiş döngü i Bu durum yalnızca bir paket sığmadığında meydana geliyordu ve bu da aynı paketin tekrar tekrar alınmasına neden oluyordu. Yukarıdaki sürüm, her yinelemede bir paketi ilerletiyor ve gerçek Kesirli Sırt Çantası kuralına uyan bir kesirli doldurma adımı ekliyor.

Java Algoritmayı örnek bir uygulama üzerinde çalıştıran sürücü:

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çgözlü Üçlü için

Öncelikle şunu tanımlayın: KnapsackPackage sınıf. __lt__ Bu yöntem, maliyete göre doğrudan sıralanabilir olmasını sağlar:

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

Ardından Kesirli Sırt Çantası algoritmasını uygulayın:

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)

Sırt çantasıGreProc() işlevi Python

Düzeltme notu: Orijinal Python sınıf boş olarak tanımlandı __init__ bedensiz, yükselten IndentationErrorYukarıdaki sürüm, boş kurucu fonksiyona ihtiyaç duyulmadığı için onu kaldırır.

İlk örnek üzerinde algoritmayı çalıştıran sürücü:

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çgözlü Üçlü için

Tanımlamak KnapsackPackage sınıf:

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

Kesirli doldurma adımıyla Açgözlü Üç algoritmasını uygulayın:

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

C#'ta KnapsackGreProc() işlevi

Karşı Örnek: 0/1 Sırt Çantası Üzerindeki Açgözlü Üçlü

Açgözlü Üçlü, Kesirli varyant için en uygun stratejidir, ancak 0/1 Sırt Çantası'nda (eşyaların bölünemediği yerde) yenilebilir. Karşı örnek:

• Parametreler: n = 3, M = 10.
• Paketler: {i = 1; W = 7; V = 9; maliyet = 9/7}, {i = 2; W = 6; V = 6; maliyet = 1}, {i = 3; W = 4; V = 4; maliyet = 1}.
• Açgözlü Üçlü algoritması, toplam değeri 9 olan 1. paketi seçerken, en uygun 0/1 seçeneği (2. paket, 3. paket) 10'a ulaşır.

Öğrenilen ders: Açgözlü Üç algoritmasını yalnızca kesirli sayılara izin verildiğinde kullanın. 0/1 varyantı için şunu kullanın: Dinamik program yerine.

Kesirli Sırt Çantası Probleminin Uygulamaları

• Sıvı, toz veya dökme malların ağırlıklarına göre bölünebildiği kargo yükleme işlemi.
• Kısmi finansmanı kabul eden yatırım seçenekleri arasında portföy dağılımı.
• Bulut tabanlı bant genişliği paylaşımı sayesinde, akışlar bağlantının yalnızca küçük bir bölümünü tüketebilir.
• Bölünebilir iş yüklerine sahip paylaşımlı zaman dilimi modeli altında CPU zamanlaması.
• Yapay zeka kaynaklarının tahsisi, bir eğitim işleminin GPU'nun yalnızca küçük bir bölümünü kullanabilmesini sağlar.

SSS