algorithm - グリッドを長方形に分割します

Question

0と＃のグリッドがあります。すべての0を長方形に再グループ化したい。必要な長方形の最小数はいくつですか？

例 ：

#00#00
#00#00
0000#0
000000

#11#34
#11#34
2222#4
222254

この例では、5つの長方形を使用します。他の解決策もありますが、すべての0をカバーするには、5つの長方形が最小です。

Answer 1

この問題はNP-Hardであり、 2D-binpackingと呼ばれる古典的なビンパッキング問題の 2D バリエーションとして知られています。 したがって、この問題に対する既知の多項式解はありません。

これは広く研究されています。この問題の解決策を近似する方法を扱った記事の例を次に示します。

問題を解決するために、Genthic Algorithms やその他のヒューリスティックなアプローチを試すこともできます。