Kesirli Sırt Çantası Problemi: Örnekli Açgözlü Algoritma
Sarah Chen
Açgözlü Strateji Nedir?
Açgözlü algoritmalar, sıklıkla optimal problemleri çözmek (belirli bir kritere göre problemin en iyi çözümlerini bulmak) için kullanılan dinamik programlama algoritmaları gibidir.
Açgözlü algoritmalar, bu seçimlerin çözülecek problem için en uygun küresel çözüme yol açacağı umuduyla en uygun yerel seçimleri uygular. Açgözlü algoritmaların kurulumu genellikle çok zor değildir ve hızlıdır (zaman karmaşıklığı genellikle doğrusal bir fonksiyondur veya büyük ölçüde ikinci dereceden bir fonksiyondur). Ayrıca bu programların hata ayıklaması ve daha az bellek kullanması zor değildir. Ancak sonuçlar her zaman optimal çözüm değildir.
Açgözlü stratejiler sıklıkla kombinatoryal optimizasyon problemini bir A seçeneği oluşturarak çözmek için kullanılır. Seçenek A, A'nın her bileşeni Ai'nin tamamlanana kadar (yeterli n bileşen) seçilmesiyle oluşturulur. Her Ai için Ai'yi en uygun şekilde seçersiniz. Bu sayede son adımda kalan son değeri kabul etmekten başka seçeceğiniz bir şey kalmaması mümkündür.
Açgözlü kararların iki kritik bileşeni vardır:
- Açgözlü seçimin yolu. Şu anda hangi çözümün en iyi olduğunu seçebilir ve ardından son seçimin yapılmasından kaynaklanan alt problemi çözebilirsiniz. Açgözlü algoritmaların seçimi önceki seçimlere bağlı olabilir. Ancak gelecekteki herhangi bir seçime veya alt problemlerin çözümüne bağlı olamaz. Algoritma, bir döngü içerisinde seçimler yaparak aynı zamanda verilen problemi daha küçük alt problemlere küçültecek şekilde gelişir.
- Optimum altyapı. Bir problemin optimal çözümü, alt problemlerine de optimal çözümler içeriyorsa, o problem için optimal altyapıyı gerçekleştirmiş olursunuz.
Açgözlü bir algoritmanın beş bileşeni vardır:
- Çözümlerin oluşturulacağı adaylardan oluşan bir küme.
- Çözüme eklenecek en iyi adayı seçmek için bir seçim işlevi.
- Uygun bir fonksiyon, bir adayın bir çözüm oluşturmak için kullanılıp kullanılamayacağına karar vermek için kullanılır.
- Bir çözümün veya tamamlanmamış bir çözümün değerini sabitleyen bir amaç fonksiyonu.
- Tam bir çözüm bulduğunuzu gösteren bir değerlendirme işlevi.
Açgözlü Bir Fikri
İlk fikirle Greedy One'ın aşağıdaki adımlarına sahipsiniz:
- Artmayan değerler sırasına göre sıralayın.
- Sırasıyla, sipariş edilen paketleri göz önünde bulundurun, eğer sırt çantasının kalan kapasitesi onu almaya yeterliyse, söz konusu paketi sırt çantasına koyun (bu, sırt çantasına konulan paketlerin toplam ağırlığının ve söz konusu paketlerin ağırlığının aşmadığı anlamına gelir) sırt çantası kapasitesi).
Ancak bu açgözlü algoritma her zaman en uygun çözümü vermez. Burada bir karşı örneğiniz var:
- Problemin parametreleri: n = 3; M = 19.
- Paketler: {i = 1; W[i] = 14; V[i] = 20}; {i = 2; W[i] = 6; V[i] = 16}; {i = 3; W[i] = 10; V[i] = 8} -> Büyük değer ama aynı zamanda büyük ağırlık.
- Algoritma toplam değeri 1 olan paket 20'i seçecek, problemin optimal çözümü ise toplam değeri 2 olan paket 3, paket 24'ü seçecektir.
Açgözlü İki Fikri
İkinci fikirle, Açgözlü İki'nin aşağıdaki adımlarına sahipsiniz:
- Ağırlıkların azalmayacak şekilde sıralanması.
- Sırasıyla, sipariş edilen paketleri göz önünde bulundurun, eğer sırt çantasının kalan kapasitesi onu almaya yeterliyse, söz konusu paketi sırt çantasına koyun (bu, sırt çantasına konulan paketlerin toplam ağırlığının ve söz konusu paketlerin ağırlığının aşmadığı anlamına gelir) sırt çantası kapasitesi).
Ancak bu açgözlü algoritma her zaman en uygun çözümü vermez. Burada bir karşı örneğiniz var:
- Problemin parametreleri: n = 3; M = 11.
- Paketler: {i = 1; W[i] = 5; V[i] = 10}; {i = 2; W[i] = 6; V[i] = 16}; {i = 3; W[i] = 10; V[i] = 28} -> Hafif ama değeri de çok hafif.
- Algoritma toplam değeri 1 olan (paket 2, paket 26) seçeneğini seçecek, problemin optimal çözümü ise toplam değeri 3 olan (paket 28) olacaktır.
Açgözlü Üçlü Fikri
Üçüncü fikirle Açgözlü Üç'ün aşağıdaki adımlarına sahip olursunuz. Aslında bu en yaygın kullanılan algoritmadır.
- Paketleri birim maliyet değerinin artmamasına göre sıralayın
. Var:
- Sırasıyla, sipariş edilen paketleri göz önünde bulundurun, eğer sırt çantasının kalan kapasitesi onu almaya yeterliyse, söz konusu paketi sırt çantasına koyun (bu, sırt çantasına konulan paketlerin toplam ağırlığının ve söz konusu paketlerin ağırlığının aşmadığı anlamına gelir) sırt çantası kapasitesi).
Fikir: Bu problemin açgözlü fikri, 
her birinin oranı 
. Daha sonra bu oranları azalan düzende sıralayın. En yüksek olanı seçeceksin paket ve sırt çantasının kapasitesi bu paketi içerebilir (kalan > wi). Sırt çantasına her paket konulduğunda sırt çantasının kapasitesi de azalacaktır.
Paketleri seçmenin yolu:
- Birim maliyet dizisini göz önünde bulundurun. Azalan birim maliyetlere göre paketleri seçersiniz.
- Kısmi bir çözüm bulduğunuzu varsayalım: (x1,…, Xi).
- Sırt çantasının değeri elde edilir:
- Sırt çantasına konulan paketlerin ağırlığına karşılık gelen:
- Bu nedenle sırt çantasının kalan ağırlık limiti:
Algoritmanın Adımları
Bunun max'ı bulma sorunu olduğunu görüyorsunuz. Paketlerin listesi, dallanmayı dikkate almak için birim maliyetlere göre azalan şekilde sıralanır.
- 1. Adım: Düğüm kökü, herhangi bir paket seçmediğiniz sırt çantasının başlangıç durumunu temsil eder.
- Toplam Değer = 0.
- Kök düğümün üst sınırı UpperBound = M * Maksimum birim maliyet.
- 2. Adım: Düğüm kökü, en büyük birim maliyete sahip paketi seçebilme yeteneğine karşılık gelen alt düğümlere sahip olacaktır. Her düğüm için parametreleri yeniden hesaplarsınız:
- ToplamDeğer = ToplamDeğer (eski) + seçilen paket sayısı * her paketin değeri.
- M = M (eski) – seçilen paket sayısı * her paketin ağırlığı.
- UpperBound = Toplam Değer + M (yeni) * Daha sonra dikkate alınacak paketlenen birim maliyeti.
- 3. Adım: Alt düğümlerde, üst sınırı daha büyük olan düğüm için dallanmaya öncelik vereceksiniz. Bu düğümün çocukları, büyük birim maliyete sahip bir sonraki paketi seçme yeteneğine karşılık gelir. Her düğüm için TotalValue, M, UpperBound parametrelerini 2. adımda belirtilen formüle göre yeniden hesaplamanız gerekir.
- 4. Adım: 3. Adımı şu notla tekrarlayın: Üst sınırı bulunan düğümler, bulunan bir seçeneğin geçici maksimum maliyetine eşit veya daha düşük değerlere sahipse, artık o düğüm için dallanma yapmanıza gerek yoktur.
- 5. Adım: Tüm düğümler dallanmış veya kesilmişse, en pahalı seçenek aranacak olandır.
Algoritma için sözde kod:
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
Algoritmanın karmaşıklığı:
- Basit bir sıralama algoritması (seçim, kabarcık…) kullanılıyorsa tüm problemin karmaşıklığı O(n2) olur.
- Hızlı sıralama veya birleştirme sıralaması kullanılıyorsa tüm sorunun karmaşıklığı O(nlogn) olur.
Java Açgözlü Üç'ün kodu
- Öncelikle KnapsackPackage sınıfını tanımlıyorsunuz. Bu sınıfın özellikleri şunlardır: her paketin ağırlığı, değeri ve karşılık gelen maliyeti. Bu sınıfın özellik maliyeti ana algoritmadaki sıralama görevi için kullanılır. Her maliyetin değeri
Her paketin 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 = new Double(value / weight);
}
public double getWeight() {
return weight;
}
public double getValue() {
return value;
}
public Double getCost() {
return cost;
}
}
- Daha sonra Açgözlü Üç algoritmasını gerçekleştirmek için bir fonksiyon yaratırsınız.
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);
}
Kodun açıklaması:
- Her sırt çantası paketi için ağırlığı ve değeri başlatın.
- Sırt çantası paketlerini maliyete göre azalan sırada sıralayın.
- Eğer paket i seçilirse.
- i paket sayısını seçmeniz yeterli olacaktır.
- Tüm paketlere göz atarken durun.
Bu eğitimde iki örneğiniz var. Yukarıdaki programı iki örnekle çalıştırmak için Java kodu:
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);
}
Çıktıya sahipsiniz:
- İlk Örnek:
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
- İkinci Örnek:
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
İlk örneği analiz edin:
- Problemin parametreleri: n = 4; M = 37.
- Paketler: {i = 1; W[i] = 15; V[i] = 30; Maliyet = 2.0}; {i = 2; W[i] = 10; V[i] = 25; Maliyet = 2.5}; {i = 3; W[i] = 2; V[i] = 4; Maliyet = 1.0}; {i = 4; W[i] = 4; V[i] = 6; Maliyet = 1.5}.
- Paketleri birim maliyetlerin değerinde artış olmayacak şekilde sıralarsınız. Elinizde: {i = 2} -> {i = 1} -> {i = 4} -> {i = 3}.
İlk örnek için algoritmayı uygulama adımları:
- Tanım x1, x2, x3, x4, {i = 2} paketine karşılık gelen seçilen her paketin numarasıdır -> {i = 1} -> {i = 4} -> {i = 3}.
- Düğüm kökü N, herhangi bir paket seçmediğiniz durumu temsil eder. Daha sonra:
- Toplam Değer = 0.
- M = 37 (önerildiği gibi).
- Üst Sınır = 37 * 2.5 = 92.5, bunun 37'si M ve 2.5'i {i = 2} paketinin birim maliyetidir.
- {i = 2} paketi ile 4 seçeneğiniz vardır: 3 paket seçin {i = 2} (x1 = 3); 2 paket seçin {i = 2} (x1 = 2); 1 paket {i = 2} (x1 = 1) seçin ve {i = 2} (x1 = 0) paketini seçmeyin. Bu 4 olasılığa uygun olarak, N kök düğümünü 4 çocuğa N[1], N[2], N[3] ve N[4] olarak dallandırırsınız.
- N1 alt düğümü için şunlara sahipsiniz:
- Toplam Değer = 0 + 3 * 25 = 75; burada 3, seçilen {i = 2} paketinin sayısı ve 25, her bir {i = 2} paketinin değeridir.
- M = 37 – 3 * 10 = 7, burada 37 sırt çantasının başlangıç miktarı, 3 paket sayısı {i = 2}, 10 her paketin ağırlığıdır {i = 2}.
- Üst Sınır = 75 + 7 * 2 = 89, burada 75 Toplam Değer, 7 sırt çantasının kalan ağırlığı ve 2 paketin birim maliyetidir {i = 1}.
- Benzer şekilde, Üst Sınırın sırasıyla 2, 3 ve 4 olduğu N[84], N[79] ve N[74] düğümleri için parametreleri hesaplayabilirsiniz.
- N[1], N[2], N[3] ve N[4] düğümleri arasında, N[1] düğümü en büyük Üst Sınıra sahiptir, dolayısıyla bir tane olması umuduyla ilk önce N[1] düğümünü dallandıracaksınız. bu yönden iyi bir plan.
- N[1] düğümünden, x1 = 1'a karşılık gelen yalnızca bir N[2-0] alt düğümünüz olur (sırt çantasının kalan ağırlığı 7 iken, her paketin ağırlığı {i = 1} 15'tir) . N[1-1] düğmesinin parametrelerini belirledikten sonra N[1-1]'in Üst Sınırı 85.5 olur.
- N[1-1] düğümünü dallandırmaya devam edersiniz. N[1-1] düğümünün x2 = 1 ve x1 = 1'a karşılık gelen 1 çocuğu N[1-2-3] ve N[1-3-0] vardır. Bu iki düğüm için parametreleri belirledikten sonra, şunu görürsünüz: N[1-1-1]'in üst sınırı 84'tür ve N[1-1-2]'nin üst sınırı 82'dir, dolayısıyla N[1-1-1] düğümünü dallanmaya devam edersiniz.
- N[1-1-1] düğümünün iki çocuğu vardır, N[1-1-1-1] ve N[1-1-1-2], x4 = 1 ve x4 = 0'a karşılık gelir. Bunlar iki yaprak düğümdür. (seçeneği temsil eder) çünkü her düğüm için paket sayısı seçilmiştir. Burada N[1-1-1-1] düğümü x1 = 3 seçeneğini, x2 = 0, x3 = 1 ve x4 = 1'i 83 için temsil ederken, N[1-1-1-2] düğümü x1 seçeneğini temsil eder = 3, x2 = 0, x3 = 1 ve x4 = 01, 81'de. Yani buradaki geçici maksimum değer 83'tür.
- N[1-1-2] düğümüne geri döndüğümüzde, N[1-1-2]'nin Üst Sınırının 82 < 83 olduğunu görüyorsunuz, dolayısıyla N[1-1-2] düğümünü kırpıyorsunuz.
- N2 düğümüne geri dönersek, N2'nin Üst Sınırının 84 > 83 olduğunu görürsünüz, böylece N2 düğümünü dallara ayırmaya devam edersiniz. N2 düğümünün x2 = 1 ve x2 = 2'a karşılık gelen iki çocuğu N[2-1] ve N[2-0] vardır. N[2-1] ve N[2-2] için parametreleri hesapladıktan sonra şunu görürsünüz: N[2-1]'in Üst Sınırı 83 ve N[2-2]'nin Üst Sınırı 75.25'tir. Bu değerlerin hiçbiri 83'ten büyük olmadığından her iki düğüm de kırpılır.
- Son olarak N3 ve N4 düğümleri de kırpılır.
- Yani ağaçtaki tüm düğümler dallanmış veya kesilmiş olduğundan, en iyi geçici çözüm aranacak çözümdür. Buna göre toplam değeri 3 olan 2 paket {i = 1}, 4 paket {i = 3} ve bir paket {i = 83} seçmeniz gerekiyor, toplam ağırlık 36.
İkinci örneğin aynı analiziyle şu sonucu elde edersiniz: Paket 4'ü (3 kez) ve paket 5'i (3 kez) seçin.
PythonAçgözlü Üç'ün 3 kodu
- Öncelikle KnapsackPackage sınıfını tanımlıyorsunuz.
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
- Daha sonra Açgözlü Üç algoritmasını gerçekleştirmek için bir fonksiyon yaratırsınız.
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)
Kodun açıklaması:
- Her sırt çantası paketi için ağırlığı ve değeri başlatın.
- Sırt çantası paketlerini maliyete göre azalan sırada sıralayın.
- Eğer paket i seçilirse.
- i paket sayısını seçmeniz yeterli olacaktır.
- Tüm paketlere göz atarken durun.
İşte PythonYukarıdaki programı ilk örnekle çalıştırmak için 3 kod:
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)
Çıktıya sahipsiniz:
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
Açgözlü Üç için C# kodu
- Öncelikle KnapsackPackage sınıfını tanımlıyorsunuz.
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; }
}
}
}
- Daha sonra Açgözlü Üç algoritmasını gerçekleştirmek için bir fonksiyon yaratırsınız.
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);
}
}
}
Kodun açıklaması:
- Her sırt çantası paketi için ağırlığı ve değeri başlatın.
- Sırt çantası paketlerini maliyete göre azalan sırada sıralayın.
- Eğer paket i seçilirse.
- i paket sayısını seçmeniz yeterli olacaktır.
- Tüm paketlere göz atarken durun.
Yukarıdaki programı ilk örnekle çalıştırmak için C# kodu:
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);
}
Çıktıya sahipsiniz:
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
Açgözlü Üç'ün karşı örneği
Açgözlü Üç'ün algoritması hızlı bir şekilde çözümlenir ve bazı durumlarda optimal de olabilir. Ancak bazı özel durumlarda optimal çözümü vermemektedir. Burada bir karşı örneğiniz var:
- Problemin parametreleri: n = 3; M = 10.
- Paketler: {i = 1; W[i] = 7; V[i] = 9; Maliyet = 9/7}; {i = 2; W[i] = 6; V[i] = 6; Maliyet = 1}; {i = 3; W[i] = 4; V[i] = 4; Maliyet = 1}.
- Algoritma toplam değeri 1 olan (paket 9)'i seçecek, problemin optimal çözümü ise toplam değeri 2 olan (paket 3, paket 10) olacaktır.
Yukarıdaki programı karşı örnekle çalıştırmak için Java kodu:
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);
}
İşte sonuç:
Pack 0 - Weight 7.0 - Value 9.0 Max Value: 9.0
Kesirli Sırt Çantası problemi bu kadar.
