Kutu paketleme problemi
Taşınırken kolileri birer birer doldurur ve daha akıllıca bir sıranın daha az koli gerektirip gerektirmeyeceğini merak edersiniz. İşte bu kutu paketleme problemidir ve zorluğuyla ünlüdür: bilgisayarlar bile büyük girdiler için en az kutuyu ancak akıllıca bir aramayla bulur. Yine de basit kurallar şaşırtıcı derecede yaklaşır.
Problem
Boyutları olan nesneler ve her biri aynı miktarı alan kutular verildiğinde, hiçbir kutu taşmayacak ve olabildiğince az kutu kullanılacak şekilde her nesneyi bir kutuya koyun. Boyutlar ağırlıkları, uzunlukları, süreleri veya dosya boyutlarını temsil edebilir. Yağmurlu bir öğleden sonra için bir bulmaca gibi görünür ama NP-zordur: her girdi için en az kutuyu hızlıca bulan bir yöntem bilinmiyor.
Hızlı kurallar
Sonraki uyan, sıradaki nesne sığmayana kadar bir kutuyu doldurur, sonra yeni bir kutu başlatır ve bir daha geri bakmaz. İlk uyan tüm kutuları açık tutar ve her nesneyi yeri olan ilk kutuya koyar. En iyi uyan her nesneyi hâlâ yeri olan en dolu kutuya koyar. Üçü de hemen karar verir; bu, nesneler tek tek geldiğinde ve hemen yerleştirilmeleri gerektiğinde işe yarar.
Önce sıralayın
Zor olanlar büyük nesnelerdir, çünkü çok boş alan isterler. Nesneleri büyükten küçüğe sıralayıp ardından ilk uyan veya en iyi uyanı kullanmak, büyük nesneleri kutular henüz boşken yerleştirir ve boşlukları küçüklerle doldurur. Azalan ilk uyan hiçbir zaman en az kutu sayısının 11/9 katı artı bir sabitten fazla kutu kullanmaz; sıralanmamış nesnelerde ilk uyan için bu oran 1,7 kattır.
Bir örnek
10 boyutunda kutular ve toplamı 40 eden 2, 3, 2, 1, 3, 4, 5, 6, 7 ve 7 nesnelerini alın. İlk uyan 2, 3, 2 ve 1'i ilk kutuya, 3 ve 4'ü ikinci kutuya koyar; ardından 5, 6, 7 ve 7'nin her biri ayrı bir kutuya ihtiyaç duyar: 6 kutu. Büyükten küçüğe sıralandığında azalan ilk uyan 7 + 3, 7 + 3, 6 + 4 ve 5 + 2 + 2 + 1 oluşturur: 4 dolu kutu; bu da 40 / 10 = 4 alt sınırına eşittir.
En az kutuyu bulmak
Az sayıda nesne için kesin cevap alt kümeler üzerinde dinamik programlamayla bulunabilir: her nesne kümesi için onu alan en az kutu sayısı ve en boş son kutu, bir nesne eksik kümelerden yola çıkarak kurulur. Bu, n nesne için yaklaşık 2ⁿ·n adım sürer. Daha büyük örnekler dal-sınır yöntemiyle veya tam sayılı programlamayla çözülür; alt sınır da bir yerleşimin en iyiden ne kadar uzak olabileceğini söyler.
Nerede kullanılır
Kamyon ve konteyner yüklemek, boruları veya kâğıt rulolarını standart uzunluklardan olabildiğince az fireyle kesmek (kesme stoku problemi), sanal makineleri sunuculara yerleştirmek ve dosyaları disklere yerleştirmek, hepsi kutu paketleme problemleridir. İki ve üç boyutta, sayılar yerine kutularla, problem daha da zordur.
Sık sorulan sorular
Çevrim içi ve çevrim dışı kutu paketleme arasındaki fark nedir?
Çevrim içi durumda her nesne, gerisi bilinmeden, gelir gelmez yerleştirilmelidir; sonraki uyan, ilk uyan ve en iyi uyan böyle çalışır. Çevrim dışı durumda tüm nesneler önceden bilinir, bu yüzden azalan ilk uyanın yaptığı gibi önce sıralanabilirler.
Azalan ilk uyan en iyiye ne kadar yaklaşır?
En fazla, en az kutu sayısının 11/9 katı artı 6/9 kutu kullanır; György Dósa 2007'de bu sınırın tam olarak sıkı olduğunu kanıtladı. Tipik girdilerde genellikle en iyi sonucu verir ya da en iyiden yalnızca bir kutu fazladır.
Kutu paketleme sırt çantası problemiyle aynı mı?
İlişkilidirler ama farklıdırlar. Sırt çantası problemi tek bir çantayı en değerli nesnelerle doldurur; kutu paketleme ise her nesneyi olabildiğince az çantaya koyar. Kesin kutu paketleme çözücüleri çoğu zaman sırt çantasına benzer problemleri tekrar tekrar çözerek çalışır.
Uygulama neden yalnızca 12 nesneye izin veriyor?
Çünkü kesin cevap her nesne kümesine bakar ve 12 nesne zaten 4.096 küme eder. Hızlı kurallar binlerce nesneyle başa çıkabilirdi, ama çizim ve kesin cevapla karşılaştırma çıkamazdı.
Denemeye hazır mısınız?
PictorX'i tarayıcınızda açın — kurulum gerekmez, başlamak için kredi kartı gerekmez.
Kutu paketlemeyi deneyin