0

空白の量が最小限になるように、JavaScript を使用して Web サイト ページに画像を最適にレイアウトする必要があります。

最適化問題は、基本的に以下を最小化することです。

(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

実際、これは純粋な線形計画法を使用して行うことはできません。ただし、オーバーラップなしの制約は、追加のバイナリ変数 (これにより MIP -- 混合整数計画問題) を使用するか、制約プログラミング手法を使用して定式化できます。これらの制約の例を次に示します。このプレゼンテーションブラウザでの制約プログラミングも興味深いものです。

于 2015-12-26T22:37:05.407 に答える
0

NPハードであるカッティングストックの問題に遭遇したと思います。ウィキペディアのページには、あなたにより適しているかもしれないいくつかのヒューリスティックな準最適ソリューションへの参照があると確信しています。

于 2015-12-26T21:15:14.847 に答える