矩形與約束

Question

包裝我想收拾一組矩形（例如）：

，使總高度儘可能低的限制就是矩形必須在結束相同的列開始。只要矩形不在最後相交，就允許矩形相互「移動」以達到最終狀態。

我們目前的算法是處理從最大高度到最小高度的矩形，並將它們放在可用的最低y位置。有沒有更優化的算法？

編輯：我不一定需要最佳的解決方案，任何生成比當前更好的解決方案的算法是有趣的。此外，矩形的數量大約爲50.

Answer 1

假設您有N矩形。對於每個矩形i，令[a_i, b_i]爲水平跨度，以​​爲高度。

您的解決方案空間看起來像y_i, i = 1, ..., N，其中矩形i的垂直跨度爲[y_i, y_i + h_i]。

不失一般性，我們可以約束y_i >= 0。然後，我們想要最小化目標函數max{y_i + h_i | i}。

你有不重疊的矩形約束條件是：

y_i + h_i <= y_j 
    OR 
y_j + h_j <= y_i 

for all i != j such that `[a_i, b_i]` and `[a_j, b_j]` intersect 

弄清楚其[a_i, b_i]彼此相交是容易的，所以找出爲其對矩形形成這些約束的應該是簡單的。

要擺脫或在我們的約束，我們可以創造二元虛擬變量z_k每個約束k和「大M」 M足夠大並改寫：

y_i + h_i <= y_j + (z_k)M 
y_j + h_j <= y_i + (1-z_k)M 

for all i != j such that `[a_i, b_i]` and `[a_j, b_j]` intersect 

我們可以引入一個虛擬變量H並添加約束y_i + h_i <= H，以便我們可以將目標函數重寫爲最小化H。

產生的優化問題是：

minimize H 
with respect to: y_i, z_k, H 
subject to: 

(1) y_i + h_i <= y_j + (z_k)M for all i != j such that [a_i, b_i] 
    y_j + h_j <= y_i + (1-z_k)M and [a_j, b_j] intersect 

(2) y_i + h_i <= H    for all i 

(3) y_i >= 0      for all i 

(4) z_k in {0, 1}    for all constraints of type (1) k 

這是一個mixed-integer linear optimization problem。對於這種類型的問題，您可以直接應用一般求解器。

通常情況下，他們將執行的技巧，比如放寬對z_k二元約束約束的算法，它變成一個linear programming problem這一點，這可以有效地解決非常期間z_k在[0,1]。

我會不是建議試圖重新發明那些解決者。

Answer 2

由於矩形只能垂直移動，因此似乎只有兩種解決方案：將所有矩形向上移動，直至發生碰撞，或將它們全部向下移動直到發生碰撞。我有一個偷偷摸摸的懷疑，這些解決方案將是相當*。當你受限於一個維度時，我不認爲有更復雜的包裝概念。也許我錯過了什麼？

*如果我正確理解了您的約束條件，最小高度始終是具有最大填充單元格數的列中已填充單元格的數量。不管翻譯是向上還是向下應用，這都不會改變。

Answer 3

在我的愚見，第一步是計算，爲每列，最低要求的高度。以圖片爲例，第一列至少需要10個高度，由紅色，綠色和小藍色矩形組成。這很容易通過遍歷每個給定的矩形並將其相應的高度添加到它所佔據的列來完成。通過這樣做，找到了所有「列高」中的最大數字，我稱之爲「支柱」。在你的圖片中，「柱子」在第8欄10處，高度爲14，由矩形1,2,4,6貢獻（從底部到頂部編號）。這意味着填料的最小高度至少是「立柱」的高度，因爲「立柱」是固體填充的，不能進一步減小。和堆疊這四個矩形起來的形式，例如圖片（未示出的非柱矩形）

然後支柱將所述圖像分割成兩個部分，一個是該區域的柱的左側，另一個在其他側。此外，「非支柱」矩形（R3,5,7,8）也分別位於兩個區域。 RHS上的R3，R7和RHS上的R5，R8。

現在先考慮左側部分。我重新安排了支柱矩形作爲畫面（圖3）所示的那樣：

隨着重排支柱矩形堆疊順序，雖然我沒有一個剛性的證明，這是非常可能的，不管是什麼矩形的形狀和數量在柱子的LHS上定位，所有給定的矩形都可以適合LHS上的空白空間（這裏的限制是這些矩形不能提供更高的固定柱，否則步驟1將已經檢測到並將其用作實際支柱）。這種佈置給LHS上的空白空間提供了最佳的「空間一致性」，這意味着每個柱狀矩形創建的空白空間從下往上依次堆疊。這種「一致性」讓每個柱狀矩形創建的空白空間「一起工作」，然後包含比單個柱狀矩形創建的任何單個空白空間更高的網格。例如，下圖中的綠色矩形適合使用由藍色和紫色矩形創建的空白空間。

假設上面的語句爲真，則定位在LHS矩形將永遠不會比所述柱更高的堆。但是，如果這些糾結需要空置空間之間的任何合作以適應LHS，那麼它們實際上限制了柱狀矩形的交換可能性。以圖3爲例，綠色的矩形要求紫色和藍色是相鄰的，然而爲了在RHS上獲得最佳的空間一致性，品紅色必須在紫色和藍色之間。這意味着LHS上的綠色使得不可能獲得RHS的最佳一致性，並且因此使得位於RHS上的矩形不能適應空的空間並且導致具有孔的堆疊並且超過支柱設置的高度。對不起，我不能在這裏設計這樣的案例，但它確實有所作爲。

結論：
第1步是找到支柱，如果每個給定的矩形都包含在支柱中，那麼可以找到一個簡單的答案 - 支柱的高度是最小填充高度。

第2步是檢查兩側的支柱。案例a：如果一側沒有定位自由矩形，那麼另一側可以容易地填充「最佳稠度」方法，並且最小包裝高度再次是支柱高度。案例b：如果一方不需要自由空間一致性，那麼該方可以填充，另一方仍然可以使用「最佳一致性」。例如:(您的原始圖片）

在這種情況下，R3中擬合的空白空間僅由R6創建，R7和R2也是如此。因此，如果R3，R7遵循交換，將R6和R2的堆疊順序與其他立方體矩形交換將不會使R3，R7不適用。這可能導致RHS的「最佳一致性」情況：

然後RHS可以填充RHS定位矩形而不超過支柱高度。
這種不一致的要求可以通過比較自由矩形的高度以及爲其創建自由空間的柱狀矩形的高度來確定。如果空閒矩形的高度不大於另一個的高度，那麼它不需要第二個矩形矩形參與，這意味着它不需要空閒空間一致性。

案例c：雙方需要自由空間一致性。這是麻煩的地方。再次以圖3爲例。圖3中的綠色組合了紫色和藍色。這意味着綠色，紫色和藍色被認爲是一個整體，將堆疊順序與其他立方體矩形進行交換，以使LHS的自由矩形最適合。在這整體中，藍色和紫色也可以互換。
如果RHS無法合身，導致包裝高度大於支柱高度，則需要重複第二步，但先安裝RHS，然後再嘗試安裝LHS。然後比較較低的包裝高度結果作爲最終結果。這種情況的邏輯不清楚，極有可能有更好的替代。

我知道這不應該被認爲是一個適當的解決方案，而是隨機的和鬆散的想法，但它顯然不適合評論。原諒我的笨拙的解釋和糟糕的圖片處理。希望這可以幫助。