İstifleme Algoritma - mümkün olan en küçük alanda Yığın 3d nesneleri

4 Cevap php

Ben pul için en uygun boyut içine nesneleri istifleme sorunu çözmeye çalışıyorum. Nesnelerin büyüklüğü ve şekli değiştirilebilir olacaktır. Uzunluk, genişlik ve tüm nesnelerin yüksekliği bilinmektedir.

Örneğin bir müşteri 2 50x50x50cm nesneler (küpler) ile birlikte (uzun ve yassı geniş) bir (uzunluk x genişlik x yükseklik) 200x100x10cm nesne sipariş edebilirsiniz. Ben bu paketi olsaydı ben üstüne alt ve 2 küpler, yan tarafta düz, geniş bir nesne koymak istiyorum.

Herkes, ya da bu oldukça verimli algoritmik çözüm biliyor mu? Ya ben bu çözümü düşünmek gerektiğini yolda bile bir yaklaşım. Ben bütün hafta kodlama oldum, geç oldu ve beynim kızarmış. Ben umutsuz değilim henüz ama sadece yarın bir gün kapalı olmasını istiyorum.

Ben bunu öngörmektedir yolu 3d boşluk, bu alanda 1 kare / cm temsil eden her dizi elemanı temsil eden bir dizi oluşturmak olacaktır. 3d boşluk uzunluğu ve genişliği uzun nesne ve geniş nesneler dayalı olacaktır. Sonra sadece yeterli 'delik' bulma ve gitmek gibi onları doldurma, en küçük nesne aşağı büyük nesneden çalışır.

Ben eminim rağmen çok daha fazla effieiently yapar matematiksel bir formül olacaktır.

Herhangi bir fikir?

4 Cevap

İlk tavsiyem - uzak klavyeden adım, kodlama dur düşünmeye başlayın!

İkinci tavsiyem - Önerilen yaklaşım (büyük ilk, sonra bir sonraki büyük) bu sorun için bir saygın ve çok kullanılan sezgisel olduğunu. Ve yapmanız gereken paketi şeyler büyük numaraları, ya da pakette büyük numaranız yoksa, yürütme verimlilik ile çok endişe etmeyin, geliştirme verimlilik muhtemelen ilk öncelik olmalıdır.

Üçüncü tavsiyem - bin-paketleme için Google ama edebiyat büyük miktarda bu konuda var, uyarılır.

Son olarak, bu :-) için matematiksel bir formül olduğunu böylece belli olmayın

Bu kolay bir sorun değil ve ben bile NP-zor sanırım. Gerçi bazı güzel fikirleri var gibi görünüyor! Ben biraz daha teori ve yeni fikirler almak için Knapsack problem yaklaşık okuma tavsiye ederim.

Ben bu önemsiz olduğunu sanmıyorum. Bunun için uygun ad bin packing olduğuna inanıyorum, ve Google arama akademik çalışmaların çok ortaya, ama (ne istediğiniz, özellikle 3-D) basit algoritmalar.

Kaç nesneleri uygulamada işlemek için arıyorsun? (Bir TEU nakliye konteyner içine değil yani yüzlerce, ama Fedexing için bir karton kutu içine belki bir kaç) nispeten daha az ise, o zaman belki bir yerel maksimum çözüm için basit bir kaba kuvvet yaklaşımı en iyi yaklaşım olabilir.

Ben bir uzman değilim ama bir kaba kuvvet yaklaşımı kullanmadan en iyi sonucu bulmak için şu anda mümkün değil bence, ama yine de bazı şeyler önerebilirsiniz:

Eğer birinci kabın üzerinde büyük hacim ve ikinci konteyner, ilk konteyner reklam sonsuza üçüncü büyük ikinci büyük nesne ile nesne ambalaj başlatırsanız 1), sonuç en çok% 14 olacaktır (ya da% 34? Tam olarak hatırlayamıyorum!) optimum sonuç daha kötü. Ben kitap Paul Hoffman tarafından "Only Numaraları Loved Man" Bu bir yere okudum.

2) Bir genetik algoritma bazı maliyet performansı nispeten iyi sonuçlar sağlamalıdır.

Orada Logen Solutions ve MaxLoad bir yaşam için bunu gibi bazı şirketler de, bu yüzden ödemek için istekli olup olmadığını siz de kendi web hizmetlerini kullanabilirsiniz.

etiketler