2

私はこの問題の 2D バリアントを解決しようとしています: Box stacking problem

問題は、元のボックスとは異なり、同じボックスの複数のインスタンスが許可されていないことです。もちろん、2D の長方形を回転させることもできます。

高さ制限も課されているため、タワーはこの制限以下でなければなりません。

別のボックスの下にあるボックスのベースは、それよりも大きくなければなりません (厳密には大きくはなりません)。

私は LIS アルゴリズムを適用しようとしており、他の制限は処理されているようですが、重複しないルールを説明する方法が思いつきません。

だから私の主な質問は、スタックの高さを最大化し、それを制限以下に維持しようとしている場合、重複なしのルールをどのように説明するのですか? ありがとう

編集：

3D バリアントの場合と同じように、アイテムごとに 2 つの可能なローテーションを作成すると、この問題は 0-1 ナップザック問題に非常に似ていることに気付きました。最適なタワーは、この並べ替えられたリストのサブセットを使用して順番に構築する必要があるため、どのタワーを使用するかを選択する必要があります。ただし、重複が発生しないようにする方法はまだわかりません。これを解決するための助けはありますか？ありがとう

編集2：

私はこのリンクを見つけました：http://courses.csail.mit.edu/6.006/fall10/handouts/recitation11-19.pdf 4ページに単一インスタンスの3D最大高さバージョンを解決する方法が記載されていますが、これは呼び出しごとに最大の高さを返すため、高さ制限バージョンでは機能しません。多分これは高さ制限に対応するために変更できますか？

4

2 に答える 2

0

わかりましたので、2D長方形のセットは制限に従うタワーにソートできるため、順序は重要ではないことに気付いた後、ブールテーブルを除いて、解決策は0-1スタイルであることがわかりました。

于 2013-02-16T21:42:43.293 に答える
0

2D 長方形のセットは、必ずしも高さの制限に従うタワーに分類できるとは限りません。たとえそれができたとしても、特定のボックスに使用する向きを決定する必要があります (ベースが収まる場合はベースが最大になるように回転させると、幅の広い長方形を上に積み重ねることができますが、高さは低くなります)。

四角形の複数のインスタンスが許可される非 0/1 バージョンは、2 つの四角形を作成し、異なる方法で回転させ、四角形の配列を並べ替える動的プログラミングによって解決されます (半順序を強制するため、四角形 i が指定された回転で、指定された回転で、長方形 j の上に収まる場合、i は j よりも小さくなければなりません) そして、i=0...n について、i 番目のボックスで終わるタワーによって達成できる最大の高さを計算します。指定された回転。

半順序が必要です。複数の長方形/ボックスが許可されていない0/1の場合、すべての長方形/ボックスのすべての可能な回転のセットを生成し、それぞれを並べ替えて、その最大高さを計算する必要があるようです。たとえば、動的計画法を使用して、すべてのサブセットで可能な限り高いスタックの高さを追跡します (巡回セールスマン問題の動的計画法ソリューションのように、可能なサブセットの指数関数的な数があることに注意してください。セットの可能な順序付けの階乗数。) 特に、ソリューションhttp://courses.csail.mit.edu/6.006/fall10/handouts/recitation11-19.pdfi < j であるが、方向 x のボックス i が方向 y のボックス j の上に収まる場合、方向 x のボックス i で終わる最も高いタワーには、方向 y のボックス j が含まれる可能性があります。 H(i,R) が計算され、式に矛盾しました。

j 番目のボックスを i 番目のボックスの上に収めることができるかどうかは、i だけでなく、i の下に j 番目のボックスの回転バージョンがあるかどうかに依存するため、重複を作成する戦略も 0/1 の場合に失敗するように見えることに注意してください。スタックで。したがって、可能なボックスのサブセットを含まない最高のスタックを保存する必要があるようです。その場合、ボックスのサブセットごとに最高のスタックを計算することに戻ります。

于 2015-10-21T01:07:36.467 に答える