算法来组织长方形的固定矩形容器 [英] Algorithm to organise rectangles in the fixed rectangular container

问题描述

我的问题是类似的二维背包问题，或切割的股票有一个例外pretty的...适合放入容器中的矩形可以调整大小和裁剪。没有转动被允许，但。

My problem is pretty similar to 2D Knapsack problem, or cutting stock with one exception... the rectangles that fit into the container can be resized and cropped. No rotation is allowed though.

的挑战是使尽可能少的农作物尽可能和（任何无缺口）填满整个容器

The challenge is to make as little crops as possible and fill entire container (no gaps whatsoever).

有没有人遇到过一个算法，会做同样的事情。任何链接，伪code多的AP preciated。

Has anyone encountered an algorithm that would do something similar. Any links, pseudo code much appreciated.

不停的问题通用的，但我想将其应用到组织照片上的一个固定大小的页面。

Kept the question generic, but I'd like to apply it to organise photos on a fixed size page.

感谢

推荐答案

在我写这篇文章的时候，我们正试图优化确切的标准还没有得到解决的。但是，不管标准是最终决定，下面的启发式（即一般不理想）的方法可能是有用的：

At the time I write this, the exact criterion we are trying to optimise hasn't been settled on. But whatever criterion is eventually decided on, the following heuristic (i.e. generally suboptimal) approach might be useful:

只考虑少数布局的结合少量的矩形成一个较大的矩形。，然后递归来看看这些新的矩形组合成更大的矩形的方式，仅使用同样的一些布局，直到只剩下一个矩形仍然存在。

Consider only a small number of "layouts" for combining a small number of rectangles into a single larger rectangle. Then recursively look at ways of combining these new rectangles into even larger rectangles, using just the same few layouts, until only a single rectangle remains.

此不保证最佳的解决方案，因为照片部分子集受到约束，以形成最终溶液内subrectangles。但它很可能是它会给合理品质的解决方案。

This doesn't guarantee an optimal solution, because some subsets of photos are constrained to form subrectangles within the final solution. But it seems likely that it will give reasonable-quality solutions.

例如，3矩形A，B和C，请考虑以下4布局：

For example, for 3 rectangles A, B and C, consider the following 4 layouts:

A
B
C

ABC

AB   (i.e. A appears on the left)
AC

AA   (i.e. A appears on the top)
BC

修剪只会发生在第一轮，当我们结合3张照片组。对于这一步，对3张照片每一个子集，应在每个4布局上述的考虑，以及最佳的缩放和裁切来确定各自的铭记，所产生的矩形可能被放大或缩小由后面的步骤。 （的最优性准则的一个很好的选择应该具有不受所得矩形多少比例缩放和下一个特定布局裁剪为每个A，B和C的的理想量的属性，所以这应该不是一个的问题。）

Cropping will only occur in the first round, when we are combining groups of 3 photos. For this step, every subset of 3 photos should be considered under each of the 4 layouts above, and the optimal scaling and cropping determined for each, bearing in mind that the resulting rectangle could be scaled up or down by later steps. (A good choice of optimality criterion should have the property that the ideal amount of scaling and cropping for each of A, B and C under a particular layout is not affected by how much the resulting rectangle is scaled, so this shouldn't be a problem.)

随后结合回合同样行为，但不考虑任何裁剪。对于一个完整的解决方案，第2轮将涉及试图结合的3长方形回合1中，所有9张照片是不同产生的所有集合，但下面这种方法会导致指数爆破。这应该足以让只求最好少安排的照片每个子集。需要注意的是，重要的是每一张照片出现在至少有1所每轮产生的矩形。

Subsequent combining rounds will behave similarly, but without considering any cropping. For a full solution, round 2 would involve trying to combine all sets of 3 rectangles produced by round 1 in which all 9 photos are distinct, however following this approach will lead to an exponential blowup. It should suffice to keep just the best few arrangements for each subset of photos. Note that it's important that each photo appear in at least 1 of the rectangles produced by each round.

这篇关于算法来组织长方形的固定矩形容器的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！