私が提案する解決策はかなり簡単ですが、非常に時間がかかります。
それは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：
パターンの組み合わせは、いくつかの制限がありますが、パワーセット構造と見なすこともできます。有効なパターンセットには、重複しないパターンのみを含めることができます。後者は、両方に少なくとも1つの共通のマトリックスセルが含まれている場合、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.
アップデート：
この回答のために私が書いた完全なコードへのリンク。
