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.
Hiç yorum yok :
Yorum Gönder