バイナリ行列のカバーボックスの最小数

バイナリ行列n * m（0と1）を持っています。問題は、その要素が全て1バイナリ行列のカバーボックスの最小数

例である非重複ボックスがすべて1をカバーするものである：

1111 
0110 
0110

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

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

おかげ

2011-03-16 Ante

はボックスです重複が許されるか？ –

@ Jeff：指定された問題については、重複しても利益は得られません。 –

これは便利です：http://stackoverflow.com/questions/4701887/find-the-set-of-largest-contiguous-rectangles-to-cover-multiple-areas/4701966#4701966 – biziclop

この問題は、直線多面体のパーティションと呼ばれます。似たような質問の上に良いのはanswerですbiziclopはコメントに投稿しました。アルゴリズムの

アイデアは、二部グラフの最大マッチングに問題を低減することである（頂点が可能カットである。）

私の元の問題は、3Dで同じ話題でした。そのバージョンがNP-completeであることが示されている： - いくつかの研究の後/

、私はAnujジャイナ教の論文で説明ヒューリスティックに基づくソリューションを実装：

2014-08-23 09:32:12 Ante

私の問題ドメインは計算化学であり、そこに私たちは巨大な多変量問題に取り組みます。また、成功した数十原子の何千ものを含むシステムに適用されてきたここで適用することができる2つの一般的なケースのグローバル最適化アルゴリズムがあります

どちらのアルゴリズムも、パブリックドメインの実装がよく理解されており、よく理解されている最適性プロパティを持っています。

2011-05-20 06:01:44

答えて