在表面上嵌套最大數量的形狀

Question

在工業中，通常存在一個問題，需要計算材料的最有效使用，無論是織物，木材，金屬等。因此，起點是X的形狀給定尺寸，由多邊形和/或曲線組成，目標是給定尺寸的另一個多邊形。

我假設很多當前的CAM套件都實現了這個功能，但是沒有經驗使用它們或者它們的內部結構，用什麼樣的計算算法來找到最有效的空間使用？有人能指向我的書或討論這個話題的其他參考嗎？

Answer 1

之後安德魯在他的回答向我指出了正確的方向和命名問題對我來說，我決定在這裏傾倒我的研究成果，在一個單獨的答案。

這實際上是一個包裝問題，更準確地說，它是一個嵌套問題。這個問題在數學上是NP難的，因此目前使用的算法是啓發式方法。似乎沒有任何解決方案可以在線性時間內解決問題，除了微不足道的問題集。如果您想要獲得具有良好材料利用率的解決方案，那麼使用當前硬件解決複雜問題需要幾分鐘到幾個小時。有幾十種商業軟件解決方案可以提供形狀嵌套，但我無法找到任何開源解決方案，因此沒有真正的例子可以看到實際實現的算法。

哥本哈根大學BennyKjærNielsen撰寫的論文（Nielsen）發表了有關歷史解決方案的嵌套和帶嵌套問題的極佳描述。

一般的方法似乎是混合和使用多個已知的算法，以找到最佳的嵌套解決方案。這些算法包括（指導/迭代）本地搜索，快速鄰域搜索是基於臨界多邊形，並擾攘的啓發式。我在這個主題上找到了一篇關於算法如何工作的圖片。到目前爲止，它還具有不同軟件實施的基準。這篇論文在S. Umetani等人的國際研討會2006中提出（Umetani）。

一個相對較新和可能迄今最好的辦法是基於混合遺傳算法（HGA），由混合模擬退火和遺傳算法已經通過描述武清大學武清明等（Quanming）。他們通過在MatLab中使用Visual Studio，SQL數據庫和遺傳算法優化工具箱（GAOT）來實現這一點。

Answer 2

你指的是一個衆所周知的計算機科學領域的包裝，其中有2個二維空間以及三維空間定義和研究的各種問題。

網絡上有相當多的材料可用於定義的問題，但要找到它必須知道要搜索的問題的名稱。

一些軟件包可能會採用啓發式appraoch（我懷疑他們會這麼做），有些軟件包可能會花費很長時間來計算所有可能性以獲得絕對正確的答案。

http://en.wikipedia.org/wiki/Packing_problem