Binary KnapSack - BackTracking

ağırlık	değeri	değer/ağırlık
5	10	2
8	12	1.5
3	3	1

Kapasite : 10

Kapasitesi 10 birim olan çantaya parçalanamayan 3 tane obje yerleştireceksin , hangilerini seçesin ki kazancın maksimum olsun ?

Ağacı oluşturalım:

1 _ _ : 1. objeyi alalım

1 1 _ : 1. ve 2. objeyi alalım

1 0 _ : 1. objeyi alalım , 2. objeyi almayalım

Ağacın yaprakları tüm kombinasyonları gösteriyor. Bunların bazıları imkansız : 

1 1 1 : 3 objeyi de alalım

3 objenin toplam ağırlığı 5 + 8 + 3 = 16 kapasiteyi aşıyor!

Peki 1 1 1 in olanaksız olduğunu daha önceden göremiyor muyuz?

1 1 1 in türediği noda bakalım

1 1 _ : 1.ve 2. objeyi alalım.

2 objenin toplam ağırlığı 13 kapasiteyi aşıyor!

O halde 1 1 _ nodundan daha devam etmeye gerek var mıydı? Hayır. Bu eleme yöntemine olanaksızlık ile budama yöntemi deniyor.

Budama hakkında genel bir bilgi verdikten sonra backtracking le ağaçta nasıl gezeceğimizi görelim. DFS(Depth first search) diye adlandırdığımız derinlik öncelikli arama yöntemi ile gezeceğiz. Yani her noda geldiğimizde önce sol çocuk , sonra sağ çocuk. Yaprağa gelindiğinde ya da gidecek daha fazla yer kalmadığında ebeveyn noda dönülür.

Son haliyle gezme sırası numaralanmıştır:

Başka bir budama yöntemi ise bir noddan devam ettiğinde elde edebileceğin maksimum kazanç şimdiye kadar ulaştığın kazançtan daha yüksek değil ise nodu açmanın bir anlamının olmaması.

Diyelimki 5 numaranın bana getirisinin 15 olduğunu saptadım. (Sayısal değerleri atıyorum) , back trackle 2. noda geri döndün , sağ taraftan devam ediyorsun , 6. noda geldin elde edebileceğin maksimum kazancı hesapladın 14 çıktı , o  zaman o nodu daha fazla açmaya gerek yok , zaten elimde kazancımın 15 olduğu bir çözüm var , 15ten daha yüksek birşey bulursam eğer yeni çözümüm o olur.

Öncelikle üst sınır hesaplamalarında Rational Knapsack kullanabiliriz . (Rational Knapsackten elde edeceğim kazanç her zaman binary knapsackten büyük ya da eşit olacaktır)

Bu ağaç üzerinde inceleyelim:

1 numaralı nodda elde edebileceğimiz maksimum kazanç ne olur ?

Değer/ağırlık değeri en yüksek olan obje 1. obje

ağırlık 5 , değer 10 , 5 birimin hepsini koydum kazancım  10

Geriye 5 birim yerim kaldı

2. olarak değer/ağırlık oranı en yüksek olan 2. obje

ağırlık 8 , değer 12 , bunun 5 birimini alabiliyorum , kazancım 7,5

toplam kazancım : 10 + 7,5 = 17,5

Yani 3 objeyle ulaşabileceğimiz maksimum kazanç 17,5 . 1. nodun üst sınırı 17,5 .

2. node : 1. objeyi alalım , zaten 17,5 kazancı 1. objenin tamamını alarak hesaplamıştık , o sebepten bu nod içinde üst sınır 17,5.

3. node : 1. ve 2. objeyi alalım.

Ağırlık : 5 + 8 = 13 .

Kapasiteyi aştığı için bu nodu buduyoruz.(Aşağıdaki şekilde görülüyor.)

Tekrar 2. noda çıktık , ordan sağ çocuğa iniyoruz:

6. nod : 1i alalım , 2yi almayalım.

17,5 kazancını 2. objenin bir kısmını koyarak elde ettik , burda 2. objeyi almıyoruz , o sebepten 3. objeye bakalım : 1. obje 5 birimi doldurdu , 2. obje 3 birim alanı oldurdu:

Toplam kazanç : 10 + 3 = 13

7. nod : İlk olasılığa ulaştık : 1. ve 3. objeleri al , toplam kazanç 13

6. noda çıkıyoruz üst sınır 13 tü , onuda 7. nodla elde ettik , o sebepten 8. noda bakmaya gerek yok , eliyoruz.

Şu ana kadar ağaç şu durumda :

Backtrackle 1. noda çıktık , şimdi 8. noda bakıyoruz.

9. nod: 1. objeyi alma. Kalan objelerden elde edeceğim kazanç:

2. objenin tamamını alırım , 2 birimde 3. objeden alırım

Toplam kazanç 12 + 2 = 14

Şu an elimizde olan çözümün(1 0 1) kazancı 13 , daha yüksek bir kazanç vadediyor, devam edelim.

10. nod : 1. yi almayalım , 2.yi alalım , bir üst nodda hesaplamayı 2. tamamen alarak yapmıştık , maksimum kazanç yine 14

11. nod : 2. ve 3.ü alalım.

Ağırlık : 11 Kapasiteyi aştı buduyoruz.

12. nod : Sadece 2.yi alalım

Ağırlık :8 , Kazanç : 12

Elimizdeki çözümden daha iyi değil.

BackTrackle 9. noda geldik.

13. nod : 1. ve 2.yi alma

Geriye 3. kaldı , maksimum kazancımız 3 , elimizde kazancı 13 olan çözüm var , bu noddan daha fazla devam etmiyoruz.

Daha fazla gezecek node kalmadığı için çözüme ulaştık : (1 , 0 , 1) , Kazanç : 13