algorithm - バイナリマトリックスのカバーボックスの最小数

Question

バイナリ行列 n*m (0 と 1) があります。問題は、要素がすべて 1 である重複しないボックスですべての 1 をカバーすることです。

例：

1111
0110
0110

ボックスは、各座標の座標と長さで表すことができます(x,y,lx,ly)。この例は 2 つのボックスでカバーされてい{ (0,0,1,4), (1,1,2,2) }ます。

最小数のボックスでカバーを見つける方法を探しています。

ありがとう

score 1 · Accepted Answer

私の問題領域は計算化学で、巨大な多変量問題に取り組んでいます。ここで適用できる一般的なケースのグローバル最適化アルゴリズムが 2 つあります。これらは、数万の原子を含む系にもうまく適用されています。

どちらのアルゴリズムも、パブリックドメインの実装を十分に尊重しており、最適性の特性をよく理解しています。

algorithm - バイナリ マトリックスのカバー ボックスの最小数