最小面積計算アルゴリズム（エッジのみのタイル配置）

Question

小さな矩形（1cm x 2xm、2cmx3cm、4cm x 6cmなど）の寸法が異なります。異なるタイプの四角形の数は、場合によって異なる場合があります。異なる長方形の各タイプは、異なる数のカウントを有することができる。

これらの小さな矩形がすべての辺にしか配置されない小さな矩形で、大きな矩形を作成する必要があります。 回転なし。最終的な外側矩形は理想的には四角形に似ていなければなりません。 X〜Y。すべてのエッジを塗りつぶす必要はありません。小さな矩形の間には隙間ができる。画像例：
http://i.stack.imgur.com/GqI5z.png

私は、形成可能な最小限の領域を見つけるコードを書こうとしています。

可能な最小限の領域を見つけるためにすべての配置をループするアルゴリズムがあります。しかし、これは、異なるタイプの矩形の数と矩形の数が増えるにつれ、実行時間が長くなります。すなわち2種類の矩形は、それぞれ100 +矩形を有する。 8 forループ。それは〜100^8回の反復になります

可能な限り最小限の領域を計算するための、より高速なアルゴリズムに関するアイデアはありますか？コードはPythonで書かれていますが、どんなアルゴリズムのコンセプトでも問題ありません。

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

これはNP困難な問題のように見えるので、単純で効率的なアルゴリズムはありません。これは、使用できる優れたヒューリスティックがないことを意味するものではありませんが、小さい四角形が多数ある場合は、最適な解決策を迅速に見つけることはできません。

なぜNP-hardですか？すべての長方形の高さが1で、長方形の高さが2であると仮定しましょう。次に、高さが2のソリューションを探すと理にかなっています（基本的に、同じ長さ）。そのような解決策が存在するかどうかを判断するには、小さい矩形の2つのサブセットを作成しなければならず、両方が同じ合計幅に加算されます。これはpartition problemと呼ばれ、NP完全です。隙間があり、幅の合計が同じである必要がない場合でも、これはNP困難な問題です。上で概説したように、要素をパーティションの高さ1の矩形に変換することで、矩形の問題に対するパーティションの問題を減らすことができます。

コメントに投稿した質問に対する回答があなたの質問になるのを待ってから、もう一度考えてみましょう。