塊佈局算法

Question

我正在尋找幫助改進放置奇怪形狀塊的算法。我的問題領域很奇怪，但我最好的比方是俄羅斯方塊，除了他們可以有四個以上的東西。塊仍然是隻有直角組成，但他們可以是長期和纏繞，他們可以分支等

我想安排在最小的空間多個大型任意形狀的塊（我知道，一個裝箱問題），但我目前的解決方案看起來很醜。我基本上是放置一個，然後通過嘗試將它們放在我的網格的原點，然後緩慢地將它們推向不同的方向，直到它們不再碰撞爲止，然後蠻力強制其餘的。雖然速度並不慢，但它並沒有試圖很好地裝飾件，所以它們不會浪費整體空間。

我能想到的唯一的嘗試是按大小排序塊，放置最大的塊，然後將最小的塊放入剩餘的任何洞中。但肯定會有適得其反的方法。

有沒有可以幫助我的啓發式算法或近似算法？

結果將類似於以下內容：

而且，也許是我的gravatar贈送，這是相關的洛克人...

Answer 1

這（四角形狀包裝）一般似乎是一個不平凡的數學問題，我會告訴你一些其他人的專業知識。這傢伙在他的網站上有一些polyomino的例子，其他人可以提交解決方案。他還有Java中的解算器軟件：

http://gp.home.xs4all.nl/Site/Polyomino_Solver.html。

http://gp.home.xs4all.nl/PolyominoSolver/downloadsolver.htm

還有斯蒂芬·蒙哥馬利 - 史密斯，這個寫了一些算法，它似乎比上述更全面（它解決了一些問題，這些問題不解決的與）最終使它成爲一個xscreensaver（實時解決和酷觀看！）。屏幕保護程序中的以下屏幕截圖只顯示了五角形的形狀，但它適用於一般容器的普通形狀。

http://www.math.missouri.edu/~stephen/software/

我不能確定，如果這兩種軟件的近似四角系統允許孔的最佳選擇。但是這種方式絕對是「可判定的」，因爲您可以將額外的1x1多米諾骨牌插入您的解決方案，並查看它是否能找到適合的特定結果，然後移除1x1碎片以獲得結果。

爲您的應用程序，它可能是更有效的逆向操作。所有這些算法在每個塊中的單位單元的數量上具有複雜性。佈置塊的好方法是將它們視爲較大單元格中的「細分」，以使塊中的3x3方塊對應於重新縮放版本中的1x1方塊。然後，填充空白空間的塊，以便它們都由較大的塊組成，運行算法並剝離多餘的空間。這不僅會更快執行，而且還會在您需要的塊之間生成空間。