Yazan : Şadi Evren ŞEKER
İyileştirme problemleri açısından klasik bir örnektir (optimisation problems). Problem basitçe bir kutunun içerisine en az boş alan bırakarak, eşyaların en iyi şekilde nasıl yerleştireceği olarak düşünülebilir.
Aslında problemi boyutlara göre incelersek aşağıdaki şekilde bir liste yapılabilir:
Tek boyutlu kutulama (1D bin packing) :Bu problemde amaç bir çizgi veya hat gibi görülebilecek yapının içerisine farklı boyutlardaki çizgileri yerleştirmek olarak düşünülebilir.
Örneğin zaman çizelgelemesinde, bir kişinin yapacağı işleri, zaman çizgisinin üzerine yerleştirmesi (ve her işin farklı miktarda zaman gerektirdiğini ve kişinin çalışma saatlerinin sınırlı olduğunu düşünürsek en fazla işi en az zamanda (örneğin 8 saatlik mesailer içinde) yapması ) bir problemdir. Buradaki hem kişinin yapacağı işler hem de bu işlerin yerleştirileceği zaman çizgisi tek boyutludur.
Daha basit olması açısından örneğin 100m uzunluğundaki bir ipi 7 ve 9m uzunluğundaki parçalara en az fire ile bölmek istiyoruz, en verimli bölme işleminde kaç adet 7 ve kaç adet 9 uzunluğunda ipimiz olur gibi soruları düşünebiliriz. Bu tip sorular tek boyutlu kutulama problemleridir.
İki boyutlu kutulama problemleri (2D bin packing optimization): Bu grupta bir tablodan ve iki boyuttan bahsedilebilir. Örneğin kot pantolon üreten bir tekstil firmasında farklı boyutlardaki Pantolon kalıplarının en az fire ile 5x5m büyüklüğündeki bir kare kumaştan kesilmesi isteniyor olsun. Bu problem iki boyutlu (x ve y boyutları) bir kutulama problemidir. Benzer bir problem, bir gazetedeki seri ilanların, en az fire ile sayfaya yerleştirilmesi olarak da düşünülebilir.
3 boyutlu kutulama (3D bin packing) problemin en zor şekli olarak tanımlanır ve 3 boyutlu bir kutunun içerisine konulan her şeklin farklı x,y ve z boyutlarında şekiller olması olarak düşünülebilir. Problemin genel tanımını yaptığımız için belirteyim, örneğin ev taşıma sırasında çıkan eşyaların kutulanması olarak düşünebilirsiniz. Bu durumu daha da karmaşık yapmaktadır çünkü kutular farklı boyut ve şekillerdedir (örneğin silindir bir varil veya küp veya dikdörtgenler prizması gibi kutuların içerisine yerleştirme yapılmakta) ve kutulanan şekillerde farklıdır ve hatta girintilidir (concave , non-convex) (örneğin avize, koltuk, sandalye gibi birbirinin içine girebilen nesneleri düşününüz). 2 ve 3 boyutlu paketleme, paketlenen nesnelerin girintili olup olmamasına göre ikiye ayrılmaktadır. Dış bükey nesnelerin paketlenmesi nispeten daha basit bir problemdir. Ancak nesnelerin iç bükey olması halinde problem biraz daha karmaşıklaşır.
Hatta literatürdeki kısıtlı aramalarım sonucunda ulaşabildiğim kadarıyla tam olarak iç bükey nesnelerin paketlenebildiği bir sonuç ne yazık ki bulamadım. Örneğin iki vidanın en verimlim paketlenmesi sırasında vidaların girinti çıkıntılarının üstüste gelmesi gerektiğini tecrübi olarak biliyoruz. N adet vida için bu durum birbirini tekrar eden bir hal alır. Gerçekten farklı boylarda ve adım sıklığında ve çaplarda vidalar verilse bu durumda en verimli paketlemeyi yapabilen bir algoritma henüz görmedim.
Paketlenen nesnelere göre problemin sınıflandırılması:
Paketlenen nesne çeşitlerinin sabit olması ve ön tanımlı olması halinde problem homojen olarak tanımlanır. Örneğin tek boyutlu kutulama probleminin tanımı sırasında verilen ve “100m uzunluğundaki bir ipi 7 ve 9m uzunluğundaki parçalara en az fire ile bölmek” şeklinde geçen örnek bu tip homojen (homogenous) bir yapıdadır. Buna karşılık heterojen bir problemde, paketlenecek nesnelerin tipleri ya tamamen birbirlerinden farklıdır ya da aynı tipte çok az tekrar vardır. Yine tek boyutlu problem örneğinde verilen zaman çizgisi üzerinde farklı uzunluklardaki randevuların yerleştirilmesi bu tiptendir.
Bu anlamda aşağıdaki problemler, kutulama probleminin birer özel hali olarak düşünülebilir:
-
kamyon yükleme problemi (truck loading),
-
konteyner yükleme problemi (Container loading problem, CLP)
-
şerit paketleme problemi (Strip Packing problem, SPP)
Yukarıda, problemin tanımını yaptıktan sonra çözümlere bir göz atalım:
Homojen tek boyutlu problem çözümü
Şayet problem tek boyutlu ise ve homojen nesnelerin paketlenmesi olarak problemin çözülmesi isteniyorsa problem oldukça basit demektir ve basit matematiksel hesaplamalar ile problemi çözebiliriz.
Örneğin tek nesne ve tek paket varsa işlem basitçe paketin nesneye bölümü olarak bulunur (zaten burada zor Bir şey de yok):
Örneğin 100m uzunluğundaki bir ipten kaç tane 5m uzunluğunda ip kesilebilir:
100 / 5 = 20
biraz daha zorlaştırıp ip sayısını 2 çeşide veya 3 çeşide çıkarırsak problem np-tam (np-complete) bir hal alır. Örneğin aşağıdaki kodu inceleyelim:
Kodda görüldüğü üzere bütün ihtimaller denenmektedir. Basitçe herhangi bir k değeri için, k-a ve k-b değerlerini denemekte ve denenen duruma göre a veya b değerini bir arttırmaktadır. Aslında kodumuz basit bir ikili ağaç (binary tree) oluşturmaktadır:
Önce 9 veya 7 ile başlanması ihtimalleri:
Sonra bu ihtimallerin de 7 veya 9 azalma ihtimalleri:
Yukarıda gösterildiği gibi her düğümden yine ikişer ihtimal indirerek bir alt seviyeye geçilebilir. Neticede 0 olana kadar yapılan bir aramadır ve 0 sonucuna birden farklı yoldan ulaşılabilir.
Kodumuz çalıştırıldığında çözüm olarak aşağıdaki sonuçları üretmektedir:
cozum : 7*4 + 9*8
cozum : 7*13 + 9*1
Gerçekten de problemin iki farklı çözümü bulunmaktadır.
Yukarıdaki kod basit bir hesaplama ile, 2’nin üstlerinin toplamı kadar adım hesaplamaktadır.
Bu değer yukarıdaki ağaçtan çıkarılabilir:
ilk düğüm için tek ihtimal 2 0
ikinci seviye için iki ihtimal: 2 1
üçüncü seviye için dört ihtimal 2 2
şeklinde gitmektedir ve örneğin problemimiz üçüncü seviyede çözülseydi (sonuç 0 olsaydı) o zaman karmaşıklığımız bu değerlerin toplamı olacaktı ve 2 0 + 2 1 + 2 2 şeklinde hesaplanacaktı.
Bu değer, ikili ağaçlardan bilindiği üzere 2 n-1 şeklinde hesaplanabilir.
Görüldüğü üzere yukarıdaki algoritma O(2 n) değerinde bir karmaşıklığa sahiptir ve bu değer bir çok terimli (polynom) değildir yani algoritmanın karmaşıklık sınıfı np-tam (NP-Complete) olarak belirtilebilir. Ayrıca yukarıdaki k değeri için bir çözüm bulunmuştur ancak çözüm bulunamasaydı bu değer k terim için denenecekti. Yani 100 için çözüm yoksa bir yaklaşığı olan 99 için ardından iki yaklaşığı 98 için … Bu işlem hiç çözüm bulunamaması halinde k terim için denenecekti.
Yukarıdaki problem, dinamik programlama (dynamic programming) kullanılarak iyileştirilebilir. Bunun sebebi arama işlemi sırasında bazı sonuçların tekrar etmesidir. Örneğin yukarıdaki ikili ağacı aşağıdaki şekilde çizebiliriz:
Farka dikkat ederseniz, 93 – 9 = 84 ve aynı zamanda 91-7 = 84 olduğu görülür. Bu durumda aslında 84 değeri bir önceki kodda iki farklı durum için aranmaktayken şimdi tek bir durum için aransın istiyoruz. Elbette 84 sadece bir örnektir ve buna bağlı olarak çok sayıda tekrar eden değer bulunmaktadır.
Hesaplanan bu değerleri bir dizi (array) içerisinde tutup tekrar hesaplanmasını engellemek istiyoruz:
Yukarıdaki yeni kodda, bir dizi içerisinde tek döngü ile sonucu hesaplattık. Buna göre algoritmamız iki elemanlı bir diziyi kullanmakta, dizinin 0. elemanları 7lerin sayısını ve 1. elemanları ile 9ların sayısını saymaktadır.
Kodumuz ilk başta 0 için 0 tane 7 ve 0 tane 9 gerektiği gerçeği ile çalışmaya başlıyor. 14-23. satırlar arasındaki döngü basitçe i. terim için i-a ve i-b değerlerine bakıyor. Şayet i. terim için i-a veya i-b değerinde bir çözüm varsa (nereden geldiğini önemsemeksizin) bu çözüme bulduğu koşulu ilave ederek mevcut i değeri için çözümü kaydediyor. Şayet bu iki terim de bulunmuyorsa o zaman bir sonraki i değerine geçiyor.
Ekran çıktısı aşağıdaki şekildedir:
Son 20 satır görülmekle birlikte daha önceki satılar alıntılanmamıştır. Ayrıca son 20 satırda görüldüğü üzere, tamamına ait bir çözüm bulunmaktadır. Örneğin 88 sayısı için 7*10 + 9*2 = 88 sonucuna ulaşılmıştır. En son satırda ise 100 için 7*13 + 9*1 sonucu görülmektedir.
Görüldüğü üzere birden fazla sonuç olsa bile tek bir sonucu görmekteyiz bunun sebebi veri yapısının bir sonuç üretmek üzere tasarlanmış olmasıdır. Elbette daha farklı veri yapıları kullanılarak diğer çözümleri de gösteren sonuçlar elde edilebilir.
Yukarıdaki algoritmanın karmaşıklığı ise bir öncekine göre oldukça iyi sayılabilecek O(n) olarak bulunur. Bunun sebebi dizideki her elemanın üzerinden tek bir kere geçiyor olması ve dolayısıyla tek bir döngünün (koddaki 14-21 satırlar arası) çalışıyor olmasıdır.
arkadaşlar ben bu kodu denedim çalışmıyor:D
dikkat ederseniz 7*13 + 9*7 = 99 demiş
az buçuk ilkokula gitmiş biri bile bunda sorun olduğunu anlar
Yorumunuz üzerine tekrar kodu denedim ve çalışıyor, belki hatalı yazıyorsunuzdur.
O bahsi geçen satır bir hata değil. Zaten dikkat ederseniz o satıra kadar olan eşitliklerin çoğu doğru değil. Eşit olduğu yeri arıyoruz ve eşitliği sağlayan çok sayıdaki çözümden sadece
7×13 + 9 x 1 = 100
denklemi eşitliğini alıyoruz ve orada durup kutulama işlemini sonuçlandırıyoruz. Sadece sonuncusunun alınmasının sebebi de yazıda yazıldığı üzere kullandığımız veri yapısının sadece tek sonuç taşıyabiliyor olması. O ekran çıktısında aranan ama eşitliği sağlayan veya sağlamayan bütün ihtimaller basılarak gösterilmiştir.
Başarılar
elinize sağlık yararlı bir paylaşım olmuş.
2 boyutlu yerleştirme problemlerine yönelik örneğiniz var mıdır?
teşekkürler…
Maalesef sitede yayınlanmış bir örnek yok. Listeme ekledim vakit bulunca bir yazı ekleyip yayınlamaya çalışacağım.
2 boyutlu yerleştirme codu lazım… yardımcı ola bilirmisiniz…