圓形矩形的最大包裝

Question

我在一個納米技術實驗室工作，我在那裏做硅片切割。 （晶圓鋸只切割平行線）當然，我們試圖最大限度地提高我們切割的模具的產量。所有的模具都是相同的尺寸，不論是矩形還是方形，並且模具都是從圓形晶圓上切割下來的。基本上，我試圖將最大的矩形打包成一個圓。

我只對MATLAB有一個非常基本的理解，並且對微積分有一箇中等的理解。有沒有（相對）簡單的方法來做到這一點，還是我的方式在我的頭上？

Answer 1

爲了滿足空間效率目標而將任意矩形包裝成圓形是一般的非凸（NP-Hard）優化。這意味着沒有優化或簡單的解決方案可以最優解決這個問題。解決方法都將取決於您可以用來修剪搜索樹或開發啓發式的任何特定領域知識。如果您對這類問題沒有經驗，您應該諮詢專家。

Answer 2

何去何從，和好運氣：

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

，並得到這裏：

http://www-sop.inria.fr/mascotte/WorkshopScheduling/2Dpacking.pdf

至少你有一些想法你在這裏解決。

Answer 3

這不像高斯的圈問題嗎？見 http://mathworld.wolfram.com/GausssCircleProblem.html

或者，這可以被看作是一個「包裝問題」 http://en.wikipedia.org/wiki/Packing_problem#Squares_in_circle

Answer 4

我很驚訝的看了你的問題，因爲我做了這個項目對我的訓練作爲一名數學教師。我也很高興知道它被認爲是一個NP問題，因爲我的項目讓我得出了同樣的結論。

通過使用基本微積分，我計算了最大尺寸矩形的前幾個'世代'，但它變得非常複雜。

你可以閱讀我的項目在這裏：

貝克特，R. 地塊Pi的：曲線裝箱問題。 Bath Spa MEC。 2009年

• Pages 1 - 15
• Pages 16 - 30

我希望我的一些研究結果是至少有趣的對你有用或。我認爲這個想法的應用很可能是計算機納米技術。

親切的問候。