Минимизация кусков в матрице

Ответ 1

Вы выполняете минимизацию схемы в таблице истинности. Для таблиц истинности 4x4 вы можете использовать K map. алгоритм Quine-McCluskey - это обобщение, которое может обрабатывать большие таблицы истинности.

Имейте в виду, что проблема NP-Hard, поэтому в зависимости от размера ваших таблиц истинности эта проблема может быстро вырасти до размера, который не поддается решению.

Ответ 2

Решение, которое я предлагаю, является довольно простым, но очень трудоемким.

Его можно разложить на 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:

Сочетание шаблонов также можно рассматривать как конструкцию силовой установки с некоторыми ограничениями: допустимый набор шаблонов может содержать только шаблоны, которые не перекрываются. Более поздний может быть определен как истинный для двух шаблонов, если они содержат по меньшей мере одну общую матричную ячейку. При использовании структуры данных шаблонов, описанной выше, предикат перекрытия довольно прост:

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.

Обновление:

Ссылка на полный код Я написал для этого ответа.

Ответ 3

Эта проблема сильно связана с Biclustering, для которой существует много эффективных алгоритмов (и свободно доступных реализаций). Обычно вам нужно указать число K кластеров, которые вы ожидаете найти; если у вас нет хорошей идеи, что K должно быть, вы можете продолжить двоичный поиск на K.

Если бикуляторы не перекрываются, вы делаете это, иначе вам нужно сделать некоторую геометрию, чтобы разрезать их на "блоки".