最小面积计算算法（仅将瓷砖放置在边缘）

Question

最小面积计算算法（仅将瓷砖放置在边缘）

6

我有不同尺寸的小矩形（1cm x 2xm，2cmx3cm，4cm*6cm等）。不同类型的矩形数量可能会因情况而异。每种不同的矩形可能具有不同数量的计数。

我需要创建一个大矩形，其中所有这些小矩形只能放在边缘上。不能旋转小矩形。最终的外部矩形应该理想地类似于正方形形状。X~Y。并非所有边缘都需要填满。较小的矩形之间可以有间隙。图片示例：
http://i.stack.imgur.com/GqI5z.png 我正在尝试编写一段代码来找出可能形成的最小面积。

我有一个算法，通过所有可能的放置方式来找出可能的最小面积。但是，随着不同类型的矩形和矩形数量的增加，它需要很长时间才能运行。即2种矩形，每种矩形都有100个以上。8个循环。那将是~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

- Charles Tang

所以外部矩形的大小已知，您想要最小化中间的白色区域？ - M Oehm

外部矩形的尺寸未知，只给出了小矩形的尺寸。随着放置位置的改变，外部矩形的尺寸会发生变化。但我希望在边缘上找到最佳的小矩形放置方式，使外部矩形的面积最小。 - Charles Tang

是的，必须使用所有的方块。例如，我有10个方块。所有的10个方块只能放在边缘，并且都必须被放置。谢谢。 - Charles Tang

1

每个边缘段是否需要与矩形相邻，还是可以有间隙？显然，角落里的矩形是两条边的一部分。但是一个大矩形也可以是底部和顶部边的一部分吗？ - lex82

解决方案的高度或宽度可以为1吗？ - lex82

显示剩余9条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- lex82 · Answer 1

这看起来像是一个NP困难问题，因此不存在简单有效的算法。这并不意味着没有好的启发式算法可以使用，但如果你有许多小矩形，则无法快速找到最优解。

为什么它是NP困难问题？假设所有的矩形都有高度为1，并且您有一个高度为2的矩形，那么寻找总高度为2的解决方案是有意义的（基本上，您尝试形成两条相同长度的高度为1的水平线）。为了确定是否存在这样的解决方案，您将需要组成两个子集，它们的总宽度相等。这被称为划分问题，它是NP完全问题。即使可能存在间隙并且总宽度不需要相同，这仍然是一个NP困难问题。您可以通过将要划分的元素转换成上述高度为1的矩形，将划分问题减少到您的矩形问题中。

我会等待您在问题评论中发布的答案，然后再考虑一下。