6

次の問題の解決策へのポインターを探しています。高さと x 位置がわかっている四角形のセットがあり、それらをよりコンパクトな形式でパックしたいと考えています。少し描画すると（すべての長方形は同じ幅ですが、実際には幅が異なる場合があります）、代わりに.

-r1-
  -r2--
     -r3--
       -r4-
        -r5--

何かのようなもの。

-r1-  -r3-- 
  -r2-- -r4-
         -r5--

すべてのヒントをいただければ幸いです。私は必ずしも「最良の」解決策を探しているわけではありません。

4

6 に答える 6

2

Topcoderは、この問題の 3D バージョンを解決するためのコンペを開催しました。勝者は彼のアプローチについてここで議論しました。それはあなたにとって興味深い読み物かもしれません.

于 2008-09-30T16:50:34.197 に答える
2

あなたの問題はより単純な変種ですが、「ビンパッキング」の問題のために開発されたヒューリスティックについて読むと、いくつかのヒントが得られるかもしれません。これについては多くのことが書かれていますが、このページは良い出発点です。

于 2008-09-30T14:44:35.547 に答える
1

このようなもの？

  • 長方形のコレクションを x 位置で並べ替えます

  • x 軸の特定の間隔にどの長方形が存在するかをチェックするメソッドを作成する

    Collection<Rectangle> overlaps (int startx, int endx, Collection<Rectangle> rects){
...
}

  • 長方形のコレクションをループします

    Collection<Rectangle> toDraw;
Collection<Rectangle> drawn;
foreach (Rectangle r in toDraw){
Collection<Rectangle> overlapping = overlaps (r.x, r.x+r.width, drawn);
int y = 0;
foreach(Rectangle overlapRect in overlapping){
y += overlapRect.height;
}
drawRectangle(y, Rectangle);
drawn.add(r);
}
于 2008-09-30T14:41:04.713 に答える
1

長方形はすべて同じ高さですか？そうであり、問​​題が各長方形をどの行に配置するかだけである場合、問題は、「長方形 X を同じ行にすることはできない」という形式の長方形 (X,Y) のすべてのペアに対する一連の制約に要約されます。四角形 X が四角形 Y と x 方向に重なっている場合は、四角形 Y" になります。

このための「貪欲な」アルゴリズムは、四角形を左から右に並べ替えてから、各四角形をそれが収まる最小番号の行に順番に割り当てます。四角形は左から右に処理されるため、現在の四角形の左端が他の四角形とオーバーラップするかどうかを気にするだけでよく、オーバーラップ検出アルゴリズムがいくらか単純化されます。

これが最適な解決策であると証明することはできませんが、一方で、反例を思いつくこともできません。誰？

于 2008-09-30T15:05:43.343 に答える
0

あなたのウェブサイトにテトリスのようなゲームを入れてください。パラメータに基づいて、落下するブロックとプレイエリアのサイズを生成します。デザインのコンパクトさ (空きスペースが少ない = ポイントが多い) に基づいて、プレーヤーにポイントを与えます。Web サイトの訪問者に仕事をしてもらいます。

于 2008-09-30T14:44:37.807 に答える
0

私は以前にこのような問題に取り組んでいました。最も直感的な図は、おそらく、大きな長方形が下にあり、小さな長方形が上にあるものです。それらをすべて容器に入れて振って、重いものが下に落ちるようなものです. したがって、これを達成するには、まず領域 (または幅) が減少する順序で配列を並べ替えます。最初に大きなアイテムを処理し、画像を一から構築します。

問題は、x 座標が指定されている長方形のセットに y 座標を割り当てることです。

長方形の配列を反復処理します。四角形ごとに、四角形の y 座標を 0 に初期化します。次に、この四角形の y 座標を、以前に配置された四角形と交差しなくなるまで増やしてループします (以前に配置された四角形を追跡する必要があります)。見つけたばかりの y 座標にコミットし、次の四角形の処理に進みます。

于 2010-06-22T02:08:36.780 に答える