Torbalama Problemi

Değiştirilebilir bir sıra izleyen kararların sonucu olarak en uygun çözümün aranmasını gerektiren problemlere "dinamik programlam" problemleri denir. Bu tür problemlerde (doğrusal programlama, yani LP problemlerinden farklı olarak) gerçekleştirilebilecek bütün aktiviteler ve onların performansa katkıları önceden bilinmez. Problemin aşama aşama çözülmesi gerekir, ve her aşamada seçilebilecek aktiviteler ve onların performansa katkıları farklıdır. Dolayısıyla, önceki bir aşamada yapılan bir seçim, sonraki aşamalarda yapılabilecek seçimleri ve elde edilecek katkıları değiştirecektir.

Ders kaynaklarında bu tür problemlerin birçok örnekleri vardır. Biz burada bir problem çözüm kitabında bulduğumuz bir problemi uyarlamayı denedik:

Açgözlü Çözüm (Greedy algorithm) örneği

Zengin bir malikanede bulunan bazı eşyaları "taşıma görevini üstlenmiş" :-) bir şahıs, eşyalardan hangilerini torbasına atacağını düşünmektedir. Amacı toplam değeri en yüksek olacak eşyaları seçip torbalamaktır. Kararına etki eden kısıt ise kendi taşıma kapasitesidir (45 kg).

Numara atanmış eşyaların kilogram ağırlıkları ve para değerleri aşağıdaki tabloda verilmiştir:

Gönüllü taşıyıcının ilk seçtiği eşyanın ağırlığı toplam taşıma kapasitesinden düşüleceğine göre, ilk seçimi ikinci ve sonraki seçimlerini etkileyecektir. Dolayısıyla, bu problem bir dinamik programlama problemidir.

Eğer taşınacak şeyler bölünemeyecek eşyalar değil de, altın tozu gibi bölünebilir maddeler olsaydı, o zaman problem bir doğrusal programlama problemi olurdu. Taşıyıcı -ki artık ona açık açık "hırsız" diyebiliriz- her maddenin gram değerini önceden bilerek, tek bir karar verir, seçimlerini gram değeri en yüksek maddeden başlayarak yapardı.

Bölünemeyecek eşyalar için bu tür bir kolay çözüm olmayacaktır, ama açgözlü bir hırsız seçimlerini aynı şekilde, eşyaları gram değerine göre yüksekten düşüğe doğru sıralayarak yapabilir:

• İlk seçiminde gram değeri 0,20 TL olan 3 numarayla başlar.

• Yüklendiği 15 kg ile taşıma kapasitesinden 30 kg kalmış olur.

• İkinci seçiminde gram değeri 0,15 TL olan 1 numarayı alır.

• Eklediği 18 kg ile taşıma kapasitesinden 12 kg kalmış olur.

• Üçüncü seçiminde gram değeri 0,10 TL olan 4 numarayı bölüp 12 kilogramını almayı hayal eder,

• ama bu mümkün olmayacağı için bir sonraki seçeneğe atlamak zorunda kalır.

• Üçüncü seçiminde gram değeri 0,075 TL olan 2 numarayı alacaktır.

• Böylece yüklendiği toplam ağırlık 15 + 18 + 12 = 45 kg olmuştur,

• yani hırsız taşıma kapasitesini doldurmuş,

• toplamda 3000 + 2700 + 900 = 6600 TL kazancı garantilemiştir.

Açgözlü Olmayan Çözüm Örneği

Yukarıdaki özel durumda açgözlü yaklaşım en iyi çözüme erişmiş gibi duruyor, ama açgözlü olmak her durumda işe yaramaz. Bir eğitim sayfasındaki şu küçük örnek bunu en iyi şekilde gösteriyor:

Gram değerlerini yüksekten düşüğe sıralayan açgözlü bir hırsız, 60 kg taşıma kapasitesiyle en yüksek toplam kazancı elde etmek için önce A, sonra B seçecektir. Bu seçimlerle yüklemndiği ağırlık 50 kg ve toplam kazancı 380 TL olacaktır, ama önce B, sonra C seçmiş olsaydı, 60 kg kapasiteyi aşmadan (tam o kadar yüklenmiş olacak) 400 TL kazancı garantilerdi.

Bunun gibi kısacık bir problem için, olası seçim aşamalarının hepsini sıralayıp en iyi sonucu verecek seçim sırasını belirlemek kolaydır. Problem sunum tablosunu ilk aşamadaki seçenekler ve sonuca katkıları olarak düşünün, sonraki aşamaları bu ilk aşamadan dallandırarak oluşturun:

Bu basit problemdeki dallanmalar yukarıdaki gibidir. Taşıma kapasitesini aştığı için geçersiz olan durumları kırmızıyla renklendirdik.

Seçim aşamalarının ve her aşamadaki seçeneklerin çok daha fazla olduğu bir problemde bu tür bir kaba kuvvet (brute force) yaklaşımı oldukça külfetli olacaktır, ama yukarıdaki dallandırma tablomuz bize doğru yöntem hakkında bir fikir vermektedir. Şöyle ki, her aşamada yapılabilecek seçimleri içeren dallar oluştururken, çözüm kısıtına uymayan dalları kesip, "umut vaat eden" dalları izlemeye devam edebiliriz. Tureng sözlüğü ve başka bazı kaynaklar "branch and bound" denilen bu yöntemi "dal ve sınır yöntemi" olarak çevirmiştir, ama "dallandır ve buda yöntemi" diye çevirmek de mümkündür. İngilizce kaynaklarda da bu yöntemi "branch and bound pruning" adlandıranlar vardır; çünkü yapılan iş de gerçek hayatta ağaçların dallarını uzatmalarına izin verip gereksiz olanları bağlayıp budayan tarımcıların yaptığı işe benzer.

Dallandır-Buda Yöntemi Denemesi

Bu yöntemi anlatıp uyarlayan pek çok kaynak vardır, ama hepsi aynı derecede anlaşılır değildir. Biz burada bir eğitici sayfadan yararlanarak, bu yöntemi kendi oluşturduğumuz bir örnek için uyarladık. Problemdeki eşya seçenekleri ve taşıma limiti aşağıdaki gibidir:

İlk adım eşya seçeneklerini gram değerine göre tersine sıralayıp, bir açgözlü çözüm serisi oluşturmaktır:

Bundan sonrasında ise, bu açgözlü çözümün ilk ve sonraki seçimleri iptal edilip farklı bir seçim serisi izlense durum daha iyi olur mu diye bakacağız.

• 1. adımda elimizde açgözlü seçim serisi vardır:

• 10, 6, 3, 1, 13

• Toplam ağırlık 30 kg tam limite eşittir.

• Toplam değer, yani maksimum kazanç 880 TL'dir.

• 1. adımın iyileştirme denemesi için ilk seçimi iptal edip şu seçim serisini deneriz:

• 6, 3, 1, 13, 12

• Toplam ağırlık yine 30 kg limite eşittir, ama toplam değer 756 TL ilk serinin kazancından daha iyi değildir.

• Sonuç olarak bu serinin temsil ettiği dalı "buduyoruz."

• 2. adımda artık açgözlü çözümün ilk seçeneği 10 kesinleşmiştir:

• 10, 6, 3, 1, 13

• Bunu iyileştirme imkanı aramak için ikinci seimi iptal edip şu seriyi deneriz:

• 10, 3, 1, 13, 12

• Bu kez toplam ağırlık 29 kg, toplam değer 769 TL olmuştur.

• Bu seri de ümit vaat etmiyor, ama hemen bir kenara atmıyoruz.

• Limitten eksik kalan 1 kg ile bir sonraki 15 nolu eşyadan bir parça almış olsak kazanç artışı ne kadar olurdu diye bakıyoruz.

• Bulduğumuz 783.44 TL sınırı yine orijinal açgözlü serinin kazancından daha düşük olduğu için bu dalın da ümit vaat etmediğini kesinleştiriyoruz.

Limitten eksik kalan payı bir sonraki eşyanın bir parçasıyla doldurmak fikrini açıklamamız lazım:

Bir üstteki A, B, C seçim örneğini hatırlarsanız, İlk olarak A seçmek daha sonra B ile Cyi beraber seçme imkanını ortadan kaldırıyordu. "Acaba ilk olarak A seçmesem de B ve Cyi birlikte mi denesem?" sorunuza cevap bulmak için ne yapardınız? Kalan boşluğu doldurmak için C'yi bölmem mümkün olsa, ek kazancım olur muydu diye bakardınız. Bunu yaptığınızda da A ve B ile 50 kg doldurduktan sonra geri kalan 10 kg için C'nin yarısını alır ve bölümlü çözüm kazancınızın 380 + 60 = 440 TL olacağını görürdünüz. Bu değer açgözlü çözüm kazancı 380 TL'nin üzerinde olduğu için, B ve C seçim serisinin ümit vaat ettiğine karar verirdiniz. Gerçekten de B ve C serisi (440 TL değilse de) 400 TL ile, A ve B serisinden daha iyi sonuç vermiştir.

Her neyse, şimdiki örneğe dönecek olursak:

• 3. adımda, açgözlü çözüm serisinin ikinci seçimi 6 numarayı da kesinleştirmiş olduk:

• 10, 6, 3, 1, 13

• Bir sonraki, bir sonraki seçimleri de iptal edip, aynı şekilde alternatif dallar denedikten sonra açgözlü çözümün maksimum kazancı sağlayan çözüm olduğunu kesinleştirmiş oluruz.

Dallandırıp budama yolunu kullanarak açgözlü çözümümüzü doğrulamış olduk, ama bu yöntem her zaman açgözlü çözüm denemesiyle başlamak zoprunda değildir. Açgözlü çözümün en fazla kazancı sağlaması daha olasıdır, o yüzden ilk adımda onunla başladık. Eşyaların orijinal sırasıyla da başlayabilirdik, ama bu örnekteki fazla eşlya sayısı nedeniyle daha fazla dal incelemek zorunda kalırdık ve bu da (kaba kuvvet yaklaşımı kadar olmasa da) külfetli olurdu. Bir ağ yapısı üzerinde genişlik-öncelikli arama yapıyor gibi olurduk.

Öte yandan, bu yöntemin her zaman açgözlü yaklaşımın doğrulamadığını gösterebiliriz. Yukarıdaki örnekteki eşya apırlık ve değerlerini biraz değiştirip, şu yeni açgözlü çözümle başlasaydık:

Açgözlü serinin ilk alternatifi olan 10, 3, 13, 1 serisinin toplam 706 TL kazanç ile en yüksek kazancı garantilediği görürdük.

Ama bu problemin bu versiyonunda orijinal dalı hemen kaldırıp atamayız. Limitten eksik kalan 7.0 kg yi bir sonraki seçenek 1 numarayı bölerek tamamlamış olsak, kazanç sınırı 855.88 TL olur5du. Bu da ikinci dalın maksimum kazancından daha iyidir. Yani bu orijinal dalın hemen budanmayıp aktif bırakılması doğru olur. O dalın ilk seçimini değil de, ikinci seçimini iptal edip yeni bir alternatif dal oluşturursak, belki o zaman ikinci dalın vaat ettiği kazancın üstüne çıkarız. Bunu siz elle deneyin.