Minimum alan hesaplama algoritması (Yalnızca kenarlara fayans yerleştirin)

Question

Farklı boyutlarda küçük dikdörtgenler (1 cm x 2 xm, 2 cm x 3 cm, 4 cm * 6 cm vb.) Var. Farklı tipteki dikdörtgenlerin sayısı kutuya bağlı olarak değişebilir. Farklı dikdörtgenlerin her tipi farklı sayıda sayıma sahip olabilir.

Bu küçük dikdörtgenlerin yalnızca kenarları üzerine yerleştirilebildiği tüm küçük dikdörtgenlerle büyük bir dikdörtgen oluşturmam gerekiyor. dönüş yok. Son dış dikdörtgen, ideal olarak kare bir şekle alıştırılmalıdır. X ~ Y. Tüm kenarların doldurulması gerekmemektedir. Küçük dikdörtgenler arasında boşluk olabilir. Resim Örneği:
http://i.stack.imgur.com/GqI5z.png

Oluşması mümkün olan en az alanı belirten bir kod yazmaya çalışıyorum.

Mümkün olan en az alanı bulmak için olası tüm yerleşimlerden geçen bir algoritma var. Ancak bu, farklı tipteki dikdörtgenlerin sayısı ve dikdörtgenlerin sayısı arttıkça uzun bir çalışma süresi alır. yani 2 tip dikdörtgen, her biri 100 + dikdörtgen içerir. Döngüler için 8. Bu, mümkün olan en az alanı hesaplamak için daha iyi ve daha hızlı algoritma hakkında herhangi bir fikir olacaktır? kod python'dadır, ancak herhangi bir algoritma kavramı iyidir.

for rectange_1_top_count in (range(0,all_rectangles[1]["count"]+1)): 
     for rectange_1_bottom_count in range(0,all_rectangles[1]["count"]-rectange_1_top_count+1): 
     for rectange_1_left_count in (range(0,all_rectangles[1]["count"]-rectange_1_top_count-rectange_1_bottom_count+1)): 
      for rectange_1_right_count in ([all_rectangles[1]["count"]-rectange_1_top_count-rectange_1_bottom_count-rectange_1_left_count]): 
      for rectange_2_top_count in (range(0,all_rectangles[2]["count"]+1)): 
       for rectange_2_bottom_count in (range(0,all_rectangles[2]["count"]-rectange_2_top_count+1)): 
       for rectange_2_left_count in (range(0,all_rectangles[2]["count"]-rectange_2_bottom_count-rectange_2_top_count+1)): 
        for rectange_2_right_count in [(all_rectangles[2]["count"]-rectange_2_bottom_count-rectange_2_left_count-rectange_2_top_count)]: 
         area=calculate_minimum_area() 
         if area< minimum_area: 
         minimum_area=area 

Answer 1

Bu, NP zor bir soruna benziyor, dolayısıyla basit ve verimli bir algoritma yok. Bu, kullanabileceğiniz iyi bir sezgisel olmadığı anlamına gelmez, ancak çok sayıda küçük dikdörtgenler varsa, en uygun çözümü hızlı bir şekilde bulamazsınız.

Niçin NP-zor? Tüm dikdörtgenlerinizin yükseklik 1 olduğunu varsayalım ve yükseklik 2'nin dikdörtgeni var, o zaman toplam yükseklik 2 ile bir çözüm aramak mantıklı olurdu (temelde, aynı uzunluktaki yükseklik-1 dikdörtgenin iki yatay çizgisini oluşturmaya çalışın)). Böyle bir çözümün var olup olmadığını anlamak için, her ikisi de aynı toplam genişliğe ekleyerek küçük dikdörtgenlerinizin iki alt kümesini oluşturmalısınız. Bu, partition problem olarak adlandırılır ve NP tamamlandı. Boşluklar olsa bile ve toplam genişliklerin aynı olması gerekmiyorsa da, bu hala bir NP-zor problemdir. Bölüm problemini, yukarıda açıklandığı gibi, yüksekliği 1'in dikdörtgenlerine bölme olarak dönüştürerek, dikdörtgen probleminize azaltabilirsiniz.

Sorunuzdaki yorumlarda yazdığım soruların cevabını bekleyeceğim ve sonra tekrar düşünün.