二進制矩陣覆蓋框的最小數目

Question

我有一個二進制矩陣n * m（0和1）。問題是要覆蓋所有的1個與非重疊的框中所有元素均爲1.

實施例：

1111 
0110 
0110 

盒可以在每個座標(x,y,lx,ly)座標和長度表示。這個例子覆蓋了2個框{ (0,0,1,4), (1,1,2,2) }。

我在尋找如何用最少數量的盒子找到封面。

謝謝

Answer 1

此問題被稱爲直線多面體的分區。關於類似的問題biziclop在評論中發佈了很好的answer。

理念算法是減少問題二分圖的最大匹配（頂點是可能的削減。）

3D

我原來的問題是3D同一主題。該版本被證明是NP-complete： -/

經過一番研究，我實現了基於由Anuj耆那教在論文中描述的啓發式解決方案：

• Partitioning 3D Phantoms into Homogeneous Cuboids
• Partitioning 3D Regions into Cuboids

Answer 2

我的問題領域是計算化學，我們解決了巨大的多元問題。有跡象表明，也已成功應用於含有原子數以萬計的系統，可以在這裏應用了兩個一般情況下，全局優化算法：

一）遺傳算法
http://en.wikipedia.org/wiki/Genetic_algorithm

B）模擬退火
http://www.gnu.org/software/gsl/
ftp://ftp.alumni.caltech.edu/pub/ingber
http://www.taygeta.com/annealing/simanneal.html
http://www2.cs.uni-paderborn.de/cs/ag-monien/SOFTWARE/PARSA/
http://www.codeproject.com/KB/recipes/SimulatedAnnealing.aspx

這兩種算法都有很好的公共領域實現和良好理解的最優性質。