最小化矩阵中的块

Question

假设我有以下矩阵:

可以将矩阵分解为块,使得对于所有行,每个块必须具有相同数量的列,其中该值被标记为该行的真.

例如,以下块是有效的:

这意味着行不必是连续的.

列也不必是连续的,因为以下是有效的块:

但是,以下内容无效:

也就是说,什么是可用于选择块的算法,以便在找到所有块时使用最少数量的块？

鉴于上面的示例,正​​确的解决方案是(具有相同颜色的项表示有效的块):

在上面的示例中,三个是可以分解为最小数量的块.

请注意,以下也是一个有效的解决方案:

实际上,没有偏好解决方案,只是为了获得最少数量的块.

我想过使用相邻单元格进行计数,但这并不能说明列值不必是连续的.

我认为关键在于找到具有约束的最大区域的块,移除那些项目,然后重复.

采用这种方法,解决方案是:

但是如何遍历矩阵并找到最大的区域就是在逃避我.

另请注意,如果您想在操作期间重新洗牌行和/或列,这是一个有效的操作(为了找到最大的区域),但我想你只能在从中删除最大的区域之后才能这样做矩阵(在找到一个区域并移动到下一个区域之后).

Answer 1

我提出的解决方案相当简单，但非常耗时。

它可以分解为4个主要步骤：

1. 找到矩阵中所有现有的模式，
2. 找到这些模式的所有可能的组合，
3. 删除所有不完整的模式集，
4. 扫描剩余列表以获取元素数量最少的集合

首先，下面的算法适用于列主矩阵或行主矩阵。我选择了列来进行解释，但您可以在方便时将其替换为行，只要它在整个过程中保持一致即可。

答案附带的示例代码是 OCaml 语言，但没有使用该语言的任何特定功能，因此应该很容易移植到其他 ML 方言。

步骤1：

每一列都可以看作一个位向量。观察到一个模式（你在问题中所说的块）可以通过相交（即和ing）所有列，或组成它的所有行，甚至组合来构造。因此，第一步实际上是生成行和列的所有组合（如果愿意的话，可以是矩阵的行和列的幂集），同时将它们相交，并过滤掉重复项。

我们考虑矩阵数据类型的以下接口：

 module type MATRIX = sig
    type t
    val w : int (* the width of the matrix *)
    val h : int  (* the height ........             *)
    val get : t -> int -> int -> bool  (* cell value getter *)

end

现在让我们看一下这一步的代码：

let clength = M.h
let rlength = M.w

(* the vector datatype used throughought the algorithm
   operator on this type are in the module V *)
type vector = V.t

(* a pattern description and comparison operators *)
module Pattern = struct
    type t = {
        w : int; (* width of thd pattern *)
        h : int; (* height of the pattern *)
        rows : vector; (* which rows of the matrix are used *)
        cols : vector; (* which columns... *)
    }
    let compare a b = Pervasives.compare a b
    let equal a b = compare a b = 0
end
(* pattern set : let us store patterns without duplicates *)
module PS = Set.Make(Pattern)

(* a simple recursive loop on @f @k times *)
let rec fold f acc k =
    if k < 0 
    then acc
    else fold f (f acc k) (pred k)

(* extract a column/row of the given matrix *)
let cr_extract mget len =
    fold (fun v j -> if mget j then V.set v j else v) (V.null len) (pred len)

let col_extract m i = cr_extract (fun j -> M.get m i j) clength
let row_extract m i = cr_extract (fun j -> M.get m j i) rlength

(* encode a single column as a pattern *)
let col_encode c i =
    { w = 1; h = count c; rows = V.set (V.null clength) i; cols = c }

let row_encode r i =
    { h = 1; w = count r; cols = V.set (V.null rlength) i; rows = r }

(* try to add a column to a pattern *)
let col_intersect p c i =
    let col = V.l_and p.cols c in
    let h = V.count col in
    if h > 0 
    then
        let row = V.set (V.copy p.rows) i in
        Some {w = V.count row; h = h; rows = row; clos = col}
    else None

let row_intersect p r i =
    let row = V.l_and p.rows r in
    let w = V.count row in
    if w > 0
    then
        let col = V.set (V.copy p.cols) i in
        Some { w = w; h = V.count col; rows = row; cols = col }
    else None

let build_patterns m =
    let bp k ps extract encode intersect =
        let build (l,k) =
            let c = extract m k in
            let u = encode c k in
            let fld p ps =
                match intersect p c k with
                      None         -> l
                    | Some npc -> PS.add npc ps
             in
             PS.fold fld (PS.add u q) q, succ k
        in
        fst (fold (fun res _ -> build res) (ps, 0) k)
    in
    let ps = bp (pred rlength) PS.empty col_extract col_encode col_intersect in
    let ps = bp (pred clength) ps row_extract row_encode row_intersect in
    PS.elements ps

V模块整个算法必须遵守以下签名：

module type V = sig
    type t
    val null : int -> t  (* the null vector, ie. with all entries equal to false *)
    val copy : t -> t (* copy operator *)
    val get : t -> int -> bool (* get the nth element *)
    val set : t -> int -> t (* set the nth element to true *)
    val l_and : t -> t -> t (* intersection operator, ie. logical and *)
    val l_or : t -> t -> t (* logical or *)
    val count : t -> int (* number of elements set to true *)
    val equal : t -> t -> bool (* equality predicate *)
end

第2步：

组合模式也可以被视为幂集构造，但有一些限制：有效的模式集只能包含不重叠的模式。如果两个模式都包含至少一个公共矩阵单元，则后者可以被定义为 true。使用上面使用的模式数据结构，重叠谓词非常简单：

let overlap p1 p2 =
    let nullc = V.null h
    and nullr = V.null w in
    let o v1 v2 n = not (V.equal (V.l_and v1 v2) n) in
    o p1.rows p2.rows nullr && o p1.cols p2.cols nullc

cols模式记录的 和指示rows矩阵中的哪些坐标包含在模式中。因此，两个字段上的逻辑与将告诉我们模式是否重叠。

为了将模式包含在模式集中，我们必须确保它不与该集中的任何模式重叠。

type pset = {
    n : int; (* number of patterns in the set *)
    pats : pattern list;
}

let overlap sp p =
    List.exists (fun x -> overlap x p) sp.pats

let scombine sp p =
    if overlap sp p
    then None
    else Some {
        n = sp.n + 1;
        pats = p::sp.pats;
    }

let build_pattern_sets l =
    let pset l p = 
        let sp = { n = 1; pats = [p] } in
        List.fold_left (fun l spx -> 
            match scombine spx p with
                None -> l
             | Some nsp -> nsp::l
        ) (sp::l) l
    in List.fold_left pset [] l

此步骤产生大量集合，因此内存和计算量很大。这当然是这个解决方案的弱点，但我还不知道如何减少折叠。

步骤3：

如果在用模式集重建矩阵时没有获得原始模式集，则该模式集是不完整的。所以这个过程相当简单。

let build_matrix ps w =
    let add m p =
        let rec add_col p i = function
            | []     -> []
            | c::cs -> 
                let c = 
                    if V.get p.rows i
                    then V.l_or c p.cols
                    else c
                in c::(add_col p (succ i) cs)
        in add_col p 0 m
    in
    (* null matrix as a list of null vectors *)
    let m = fold (fun l _ -> V.null clength::l) [] (pred rlength) in
    List.fold_left add m ps.pats

let drop_incomplete_sets m l =
    (* convert the matrix to a list of columns *)
    let m' = fold (fun l k -> col_extract m k ::l) [] (pred rlength) in
    let complete m sp =
        let m' = build_matrix sp in
        m = m'
    in List.filter (fun x -> complete m' x) l

步骤4：

最后一步是选择元素数量最少的集合：

let smallest_set l =
    let smallest ps1 ps2 = if ps1.n < ps2.n then ps1 else ps2 in
    match l with
        | []    -> assert false (* there should be at least 1 solution *)
        | h::t  -> List.fold_left smallest h t

整个计算只是每个步骤的链接：

let compute m =
   let (|>) f g = g f in
   build_patterns m |> build_pattern_sets |> drop_incomplete_sets m |> smallest_set

笔记

上面的算法构造了幂集的幂集，并进行了一些有限的过滤。据我所知，没有一种方法可以减少搜索（正如评论中提到的，如果这是一个 NP 难题，则没有任何方法）。

该算法检查所有可能的解决方案，并正确返回最佳解决方案（使用许多矩阵进行测试，包括问题描述中给出的矩阵。

关于您在问题中提出的启发式的简短评论：

它可以使用第一步轻松实现，删除找到的最大模式并递归。这会比我的算法更快地产生解决方案。然而，找到的解决方案可能不是最佳的。

例如，考虑以下矩阵：

.x...
.xxx
xxx.
...x.

中央 4 个单元块是可能找到的最大的，但使用它的集合总共包含 5 个图案。

.1...
.223
422.
...5.

然而这个解决方案只使用了 4 个：

.1...
.122
334.
...4.

更新：

链接到我为此答案编写的完整代码。