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

Binary Knapsack - Branch & Bound Design

Problem için öncelikle durum uzayı oluşturalım .

Her seviyede o objeyi alıp almama olarak nodumuz ikiye ayrılıyor. Sonunda 2^n farklı kombinasyon oluşuyor. Peki tüm ağacı search etmekten daha iyi ne yapabiliriz?

İki farklı budama yapabiliriz.

1. Branching infeasible nodes

2. Branching with bounding

Bir örnek üzerinde açıklayalım.

4 adet objemiz olsun. Ağırlıkları 2,5, 7, 3 ; kapasite 12 olsun . Öyleyse (1,1,1,0) bir çözüm olabilir mi? Hayır  çünkü 1 . 2. 3. objeyi koyabilmemiz için kapasitemizin en az  2+5+7=14 olması gerekir. Öyleyse bu noddan devam etmeye gerek kalmıyor ve buduyoruz.

Sadece infeasibility ile budamak dışında ne yapabiliriz. Her bir nodda bir üst sınır bulabilirsek , yani o noddan ilerleyerek bulabileceğim çözümün maksimum benefiti o nodun üst sınırı, üst sınırı düşük kalan nodları budayabiliriz. Binary knapsack için nasıl bir üst sınır bulabiliriz: Rational knapsack. Aynı objeler ve aynı kapasiteyle binary knapscakle ulaşabilceğim maksimum benefit her zaman rational knapsackle ulaşabilceğiminkinden küçük veya eşittir.

Bunuda bir örnekle açıklayalım.

benefits: 20  35  21  33

weights:  2    5    7    3

b/w      : 10   7   3    11

capacity: 12

Rational knapsack problemi olsaydı b/w büyüklüğüne göre

33 + 20 + 35 + 21*2/7 = 94 maksimum benefitimiz 94 olurdu.(1. 2. 4. objeyi tamamen alıyoruz , 3.nün 2/7sini)

1. seviyede 1. objeyi alırsak üst sınırımız yine 94 b=20 w=2

                  1. objeyi almazsak kalan objelerle maksimum 33+35+21*4/7=80 benefit elde edebiliyoruz

En gelecek vadedenden devam ediyoruz.

2. seviye 2.objeyi alırsak üst sınır yine 94, weight=7

                           almazsak kalan objelerle üst sınırımız 33+20+21=74 oluyor.

3. seviye 3.objeyi alırsak üst sınır 94 , weight = 14 (infeasible)

                            almazsak üst sınır= 33+20+35=88

4.seviye 4.objeyi alırsak üst sınır 88, weight=10, benefit=88

B(x)=benefit olduğu için öbür nodu açmaya gerek yok zaten bu noddan elde edilebilcek maksimum benefit 88. Açılmamış olan tüm nodlar budanıyor , çünkü bulduğumuz çözümün benefiti hepsinin üst sınırından daha büyük , o sebepten onları açmaya gerek kalmadan çözüme ulaşıyoruz.

Binary Knapsnak Problem - Dynamic Programming

Nedir Sırt Çantası Problemi: Kısıtlı kapasitesi olan sırt çantan var . Boyutları ve değerleri olan parçalanamayan eşyalar var. Çantaya alabileceği kadarını koyduk , değer maksimum kaç olur?

Problemin alt parçasına inelim. W kapasiteli bir çantanın maksimum değeri V.
X eşyası eklendiyse onu çıkardığımız  zaman W- Sx kapasiteli çantada maksimum değeri elde ederiz.
Sx: X eşyasının boyutu
Vx: X eşyasının değeri

Value = max{ Value(W-Sx)+Vx , Value(W) }
Value(0) = 0;

Bir örnek üzerinden gidelim:
1. obje boyutu=4 değeri =10
2. obje boyutu=2 değeri =8
3. obje boyutu=3 değeri =3
Çantanın boyutu=5

 Öncelikle 1 tabloya ihtiyacımız var

 Tablonun boyutu: Çantanın kapasitesi kadar sütun(bizim örneğimizde 5) , obje sayısı kadar satır.
[i,j] hücresi j kapasiteli bir çanta ve ilk i obje varken elde ettiğimiz maksimum kazanç.

Birinci satırı doldurmaya başlıyoruz. 1. objenin boyutu 4 ,değeri 10 . Çantanın kapasitesi 4 olana kadar 1. objeyi ekleyemiyoruz bu yüzden 4e kadar kazancımız hep 0. 4e geldik 1. objeyi ekleyebilirim. 1. objeyi eklediğimizde kazancımız 10 oldu. 5e geldik ekleyeceğimiz başka obje yok yine 1. objeyi ekliyoruz.

2. objede geldik boyutu=2 değeri=8
Kapasite 1 : 2. obje sığmıyor , kazanç 0. Üst satıra bakıyoruz oradaki değer de 0. 0 yazıyoruz.

Kapasite 2:  Obje sığıyor , kazanç=8 , bir üst satıra bakıyoruz kazanç 0 imiş. Eklediğimizde değer artıyor o sebepten ekliyoruz.Hücrenin değeri 8 oluyor.

Kapasite 3: Objenin boyutu 2 , 1 birim yer kaldı , 1 birimlik yerde önceki objelerle neler yapabiliriz? Bir üst satırda 1.sütuna bakıyoruz değeri 0. Toplam kazanç 8+0=8. Bir üst satıra bakıyoruz değeri 0. 8>0 olduğu için objeyi ekliyoruz, kazanç 8 oluyor.

Kapasite 4: Burada iş biraz değişiyor. Objeyi ekleyelim kazanç 8 , 2 birim yer kalıyor . Üst satırdan 2 birim yerin değerine bakıyoruz 0, 8+0 toplam kazanç 8. Üst satırın 4. sütununa bakıyoruz. Peki ne için , önceki objelerle 4 kapasitesinde bir çanta için maksimum ne kadar kazanç elde etmişiz : 10 . 10 > 8 olduğu için 2. objeyi bu sefer eklemek yerine üstteki kazançla devam ediyoruz. Hücrenin değeri 10 oluyor.

Kapasite 5: 2. objeyi koyarsak 3 birim yer kalıyor. Üst satırdan bakıyoruz değeri 0 toplam kazanç 8 oluyor . Üst satırdan 5. sütuna baktık değer 10 daha büyük , 2. objeyi koymuyoruz.

 Buraya kadar genel mantık şu şeklide ilerliyor:

i. obje için
o anki kapasite = K
objenin boyutu = H
objenin değeri=P

K<H
Objeyi ekleyemiyoruz. Value[i][K]=Value[i-1][K],  Value[0][K]=0

K=H
Eklediğimizde elde ettiğimiz kazanç , eski kazançtan daha büyükse objeyi ekliyoruz.
 if (P > Value[i-1][K] )
    Value[i][K]=P
else
   Value[i][K]=Value[i-1][K]

K>H
Bu durumda kalan birimin değerini de eklememiz lazım.Eğer objeyi eklediğimizde elde ettiğimiz değer + kalan birimden gelen değer , önceki değerden büyükse objeyi ekliyoruz.

if (P + Value[i-1][K-H] > Value[i-1][K])
    Value[i][K]=P + Value[i-1][K-H]
else
   Value[i][K]=Value[i-1][K]


Tablonun son hali

Bu 3 objeyle 5 birim kapasiteli bir çantada maksimum bu kazanç elde ediyoruz: Value[2][4] = 11

11 i neleri çantaya ekleyerek elde ettik?
5 birimlik çantada 1 ve 2 objelerle max kazanç (Value[1][4]): 10
5 birimlik çantada 1 2 3 objelerlerle max kazanç (Value[2][4]): 11
3. objeyi eklemişiz ki kazanç değişmiş.

3 objeyi eklemeye nasıl karar veriyorduk:
Boyutu 3 olduğu için 2 birim yer kalıyor , bir üst satırdan 2 birim yerden maksimum ne kadar kazanç elde ettiğimize bakıyoruz : 8 , 8 i nasıl elde ettik aynı sütunun üst satırına bakıyoruz kazanç 0 imiş 2. objeyide hesaba katınca kazanç 8 olmuş ; demekki 2. objeyide eklemişiz. 2. objenin boyutu 2 , başka yerimiz kalmadı.
Demekki 2. ve 3. objeleri eklemişiz.

Two Egg Problem - İki Yumurta Problemi

Önce problemin tanımını yapalım:

n katlı bir binadayız , iki adet yumurtamız var . Yumurtalar x. katın altındaki katlardan atınca kırılmıyor, x ve üzeri katlardan atılınca kırılıyor. Kırılmadığı sürece yumurtayı tekrar tekrar kullanabilirsiniz. Minimum kaç atışta yumurtanın kırılmaya başladığı katı bulursunuz?

Akla gelen ilk çözümler:

• 1. kattan başlarız ilk nerede kırıldıysa x odur.

 En iyi Durum: İlk katta kırıldıysa tek atışla bulduk.
 En kötü Durum: En üst katta kırılıyorsa n -1 atışta bulduk.

•  İlk yumurtayı orta kattan atarız.

kırıldıysa : 2. yumurtayı ilk kattan atmaya başlarız, taki kırılana kadar
kırılmadıysa : n/2 ile n. katlar arasında kırılıyor. Bu katların ortasından atış yapıyoruz( 3* n / 4). Böyle devam ediyoruz.(Binary search mantığı).
En kötü Durum: yumurtanın n/2-1 katta kırılması. (Benim de aklıma gelen çözüm bu olmuştu)

Gelelim ideal çözüme bunu direk bir örnekle açıklayacağım. Diyelim ki binamız 100 katlı iddiamız 14 atışta ben nerede kırıldığını bulurum. Nasıl mı?

14. kattan atalım. İlk atış hakkımı kullandım. Kaldı 13.

Kırıldı: 1 den 13 e kadar tek tek deniyoruz.

Kırılmadı: İlk 14 katta kırılmıyor. 1 atış yaptık , 13 atış hakkımız kaldı . 14 + 13 = 27 .

27. kattan atalım. Kaldı 12.

Kırıldı: 15 ten 26. kata tek tek deniyoruz.

Kırılmadı: İlk 27 katta kırılmıyor. 2 atış yaptık , 12 hakkımız kaldı. 27+12=39.(14+13+12)

39. kattan atalım: Kaldı 11

Kırıldı: 28 den 38. kata tek tek deniyoruz.

Kırılmadı: İlk 39 katta kırılmıyor. 39+11=50.(14+13+12+11)

.
.
.

(14+13+12+11+...+4 = 99)39. kattan atalım: Kaldı 3
Kırıldı : (14+13+12+11+...+5+1 = 96)96. kattan 98. kata tek tek deniyoruz.
Kırılmadı: İlk 99 katta kırılmıyor. 100. kattan atıyoruz. Kırılacaktır.

n katlı bina için q atış garantiler ise

q+(q-1)+(q-2)+.....1 =  q*(q+1)/2 >= n olması gerekir.

Güzel çözüm değil mi ? Tabi bu problemde yumurta sayısı da değiştirilebilir, strateji aynı.