3

さまざまなサイズの長方形があり、それらを中心から大きな長方形に合わせようとしています。以下に、何を行う必要があるかを視覚的に説明するために作成したアニメーションを示します。

私は、この動作をモデル化する方法を考え出すのに苦労しています。これに似たものはありますか？私はただ正しい方向に向けられる必要があります。

ここに画像の説明を入力

以下は非常に大雑把な説明です。

初期化する

  • n長方形から始める
  • 密度順 (実際には 3D 立方体の鳥瞰図です)
  • 最初の長方形を中央に配置

残りの長方形（できるだけ多く収まる） は、中央に最も密度の高いものをグループ化し、外側に移動しようとします

Dimensions = { width: 400, height: 300 }
Boundries = {
  WEST = 0,
  EAST = Dimensions.width,
  NORTH = 0,
  SOUTH = Dimensions.height
}

// each rectangle has width, height, and other information
rectArr = Array of {width:60, height:40}

root = { x:EAST/2, y:SOUTH/2 }

foreach rect in rectArr {
  // I will always traverse from the root and try to go left and right. If I cannot, I move up and try the same thing. I then move down. The problem is if there are 5 or more rows. I will be starting from the root and going up, then down, then up-up, then down. It's like I have two parallel trees.

  // Try to branch left or right
  if rect.width <= (Boundries.EAST - ('rightmost rectangle'.x + 'rightmost rectangle'.width/2)) branch-right
  if rect.width <= (('leftmost rectangle'.x + 'leftmost rectangle'.width/2) - Boundries.WEST) branch-left
  // Try to branch up or down
  if rect.height <= ((root.x + root.height/2) - Boundries.NORTH) branch-up
  if rect.height <= (Boundries.SOUTH - (root.x + root.height/2)) branch-down
}
4

1 に答える 1

1

編集：これを書き始めたのは早すぎました。このソリューションは、小さい長方形の位置が静的であると仮定して、大きい長方形をできるだけ多くの小さい長方形で埋めることにのみ関係します。

ここでは、動的計画法ソリューションが最適に機能するように聞こえます。アルゴリズムを勉強したことがない場合は、欲張りアルゴリズムの定義、動的計画法アルゴリズムの定義、各種類の例、およびどちらを使用するかを検討することをお勧めします。

この問題は、重み付きスケジューリング問題と非常に似ていますが、2次元です。加重スケジューリングでは、間隔とサブ間隔のセットが与えられ、合計された重みが最大で範囲が重複しないサブ間隔のセットを決定するように求められます。

|--------------------------|
|{--a--}-------------------|
|----{------b-------}------|
|--------{----c----}-------|
|--------------------{-d-}-|

これを2次元に拡張すると、大きい方の間隔は境界の長方形のx / yの長さ、サブの間隔は小さい方の長方形のx / yの長さ、サブの間隔の重みは小さい方の長方形の面積になります。 。

欲張りアルゴリズムでは、境界の長方形を可能な限り多くの最大のサブ長方形で埋めてから、2番目に大きい、次に3番目に大きい、というように、どの長方形も収まらなくなるまで収まるようにします。 。それに関する問題は、2番目に大きい4つを使用する場合よりも最大のサブ長方形の1つを使用する場合に、境界長方形の塗りつぶしが少なくなる可能性があることです（辺のサイズが6の境界正方形がある場合を考えてみてください。最大のサブスクエアの辺のサイズは5で、2番目に大きいサブスクエアの辺のサイズは3）です。最初の解決策でこれと同じ問題が発生する可能性があるようです。

動的計画法ソリューションは、より大きな問題を重複するサブ問題に分解し、サブ問題の結果に基づいてソリューションを構築します。長方形の場合、セット内のすべての長方形について同じ質問をしたいと思います。それを含めるか、ソリューションに含めない場合の結果が良くなります。この質問への回答に基づいて、ソリューションセットに長方形を追加し、それが重なっている他のすべての長方形を削除するか、その長方形のみを削除して続行します。次の疑似コードを提案します。

compute_opt ( set of rectangles ){
  if(set.size == 0)
    return 0
  return max (area of selected rectangle i +  
              compute_opt( rectangles that don't overlap with i) ,
              compute_opt( rectangles without rectangle i included) )
}

私はメモ化に少し錆びているので、ここでは説明しません。ただし、加重スケジューリングの詳細については、動的計画法に関するこのプリンストンの講義を参照してください。区間問題の詳細を考えると、長方形の問題の詳細を理解できるはずです。

于 2013-02-26T02:32:24.170 に答える