Python：將幾何形式裝配到板矩陣中？

在過去的幾天裏，我正在考慮一個AI問題的解決方案。這個問題聽起來像這樣：Python：將幾何形式裝配到板矩陣中？

我要確定這樣的方式，董事會將統一幾個給定的幾何形狀的裝置（不超過給定的電路板尺寸）在給定大小的方形板，涵蓋和形式將不重疊。

我想申請深度第一次搜索/貪婪最好的第一次搜索，但它很難找到一個適當的表格形式和實際的董事會以通過它。我是python的新手，所以使它更加困難。有什麼建議麼？

視覺例如：

來源

2016-05-22 user3293380

你能舉一個例子嗎？ –

@RosaGronchi你可以想象像俄羅斯方塊遊戲。你可能會有幾種形式與俄羅斯方塊中的完全相同，你可以一個接一個地使用它們，一個在另一個之上。您也可以旋轉表格... – user3293380

https://en.wikipedia.org/wiki/Tessellation？ –

你所描述是矩形/平方米裝修的變化。問題的版本存在於未使用的單元必須最小化以實現圖形的最佳位置，而其他版本（如您所描述的版本）要求整個板均勻覆蓋。這些被稱爲「完美的方形/矩形放置」問題。

解決這些問題的典型方法包括使用代表矩形變量的有限整數域和確保幾何位置是有效的約束的一組約束（即不跨越板邊界，不重疊彼此相互......）。

來源

2016-05-22 09:47:09 SND

可以說棋盤上的實心方塊的值爲1，空的方塊的值爲0. 我在考慮讓初始棋盤作爲矩陣，矩陣，所以當我將表單添加到板上時，我不會得到值> 1（表示重疊）。但它仍然不清楚我將如何遍歷矩陣使用DFS/GBFS。 – user3293380

添加了圖像，以便更容易理解。 – user3293380

這確實是模擬這個問題的好方法，因爲每個細胞都「知道」有多少圖形可以重疊，統一覆蓋每個細胞變得很容易。看看使用ECLiPSe作爲編程語言的[this]（http://4c.ucc.ie/~hsimonis/shikaku.pdf）文章，它可能對您有很好的用處/靈感。至於搜索，您可以選擇部分搜索（如論文中所述：預先計算所有展示位置以減少最終搜索空間），或者在同時放置數字的同時進行搜索。當然，兩者都有其優點和缺點。 – SND

Python：將幾何形式裝配到板矩陣中？

回答

相關問題