0

我需要在网站页面上使用 JavaScript 优化布局图像，以便最大限度地减少空白量。

优化问题基本上是最小化以下内容：

(rightmost x-coordinate of an image - leftmost x-coordinate of an image) +
(bottommost y-coordinate of an image - topmost y-coordinate of an image)

但是，没有图像可以重叠，因此对于每个图像，约束是：

for i in images
    for j in each other image 
        (topmost coordinate of i > bottommost coordinate of j) || 
        (bottommost coordinate of i < topmost coordinate of j) ||
        (leftmost coordinate of i > rightmost coordinate of j) ||
        (rightmost coordinate of i < leftmost coordinate of j)

此外，还有一个约束，任何图像的最右边坐标不能大于页面的宽度，并且任何图像的最左边坐标必须> 0。

首先我想把它表述为一个线性规划问题，但是我看到的所有 JavaScript 的线性规划库都不允许这样复杂的约束，所以我认为这可能不是一个线性问题。

然后我开始认为这是一个动态编程问题，但如果不尝试每种布局组合，我不确定如何解决它，这会非常慢。

有谁知道如何有效地解决这类问题？

4

2 回答 2

0

Indeed this cannot be done using pure Linear Programming. However the no-overlap constraints can be formulated using extra binary variables (this will make it a MIP -- Mixed Integer Programming problem) or using constraint programming techniques. Here is an example of these constraints. This presentation Constraint programming in the browser is also interesting.

于 2015-12-26T22:37:05.407 回答
0

我认为您遇到了NP 难的切割库存问题。我确信 Wikipedia 页面引用了一些可能更适合您的启发式次优解决方案。

于 2015-12-26T21:15:14.847 回答