算法切割矩阵为正方形子矩阵

huangapple go评论75阅读模式
英文:

Algorithm to slice into square matrix a matrix

问题

我正在寻找一个算法,它接受一个矩阵(实际上是一个双入数组),并返回一个矩阵数组,满足以下条件:

  • 是方阵(宽度=高度)。
  • 矩阵中的所有元素具有相同的值。

如果不太清楚的话,可以想象一下,你有一张由红色、蓝色或绿色像素组成的图片,我想获得一个包含最少可能的方块的数组。就像图片所示:

编辑:

好的,也许还不太清楚:我有一个由一些像这样的值组成的元素网格:

0011121

0111122

2211122

0010221

0012221

这是我的输入,我想要的输出大致如下:

|0|0|111|2|1|

|0|1|111|22|

|2|2|111|22|

|00|1|0|22|1|

|00|1|2|22|1|

这里的每个|X|都是一个输入数组的一部分。
我的目标是最小化输出数组的数量。

英文:

i'm searching for a algorithm that take a matrix (in fact, a double entry array) and return an array of matrix that:
is square (WIDTH = HEIGHT)
all of the element in the matrix has the same value.
I don't know if that is clear, so imagine that you have a image made of pixels that is red, blue or green and i want to get an array that contained the least possible squares. Like the pictures shows

EDIT:

Ok, maybe it's not clear: I've a grid of element that can have some values like that:

0011121

0111122

2211122

0010221

0012221

That was my input, and i want in output somethings like that:

|0|0|111|2|1|

|0|1|111|22|

|2|2|111|22|

|00|1|0|22|1|

|00|1|2|22|1|

When each |X| is an array that is a piece of the input array.
My goal is to minimize the number of output array

答案1

得分: 1

这个问题似乎没有一个高效的解决方案。

考虑问题的一个子集,定义如下:

  • 矩阵元素只有两个值,称为 01
  • 只考虑值为 0 的矩阵元素。
  • 将每个矩阵元素 m_ij 视为二维矩形网格中的一个单位正方形,其左下角坐标为 (i, n-j)
  • 以这种方式选择的单位正方形集合 SU 必须是“连通”的,并且不能有“洞”;形式上,对于每一对单位正方形 (m_ij, m_kl) \in SU^2:(i, j) ≠ (k, l),存在一个序列 <m_ij = m_i(0)j(0), m_i(1)j(1), ..., m_i(q)j(q) = m_kl>,其中有 q+1 个单位正方形,满足 (|i(r)-i(r+1)| = 1 _且_ j(r)=j(r+1)) _或_ (i(r)=i(r+1) _且_ |j(r)-j(r+1)| = 1 ); r=0...q(序列中相邻的单位正方形共享一条边),并且所有左下角坐标为整数且不在 SU 中的单位正方形组成的集合 SUALL 也是“连通”的。

将满足此构造条件的矩阵进行切割,使其分成最少数量的正方形子矩阵,等价于将包围 SU 的最小正交多边形(即所有 SU 元素的并集)铺成最少数量的正方形。

根据这篇 SE.CS 帖子,可以找到参考文献(以及一个证明),证明了该问题对于平铺集合中正方形的整数边长是 NP 完全的。

需要注意的是,根据同一篇帖子,使用矩形进行平铺可以在多项式时间内完成。

英文:

This problem does not seem to have an efficient solution.

Consider a subset of instances of your problem defined as follows:

  • There are only 2 values of matrix elements, say 0 and 1.
  • Consider only matrix elements with value 0.
  • Identify each matrix element m_ij with a unit square in a rectangular 2D grid whose lower left corner has the coordinates (i, n-j).
  • The set of unit squares SU chosen this way must be 'connected' and must not have 'holes'; formally, for each pair of units squares (m_ij, m_kl) \in SU^2: (i, j) != (k, l) there is a sequence <m_ij = m_i(0)j(0), m_i(1)j(1), ..., m_i(q)j(q) = m_kl> of q+1 unit squares such that (|i(r)-i(r+1)| = 1 _and_ j(r)=j(r+1)) _or_ (i(r)=i(r+1) _and_ |j(r)-j(r+1)| = 1 ); r=0...q (unit squares adjacent in the sequence share one side), and the set SUALL of all unit squares with lower left corner coordinates from the integers minus SU is also 'connected'.

Slicing matrices that admit for this construction into a minimal number of square submatrices is equivalent to tiling the smallest orthogonal polygon enclosing SU ( which is the union of all elements of SU ) into the minimum number of squares.

This SE.CS post gives the references (and one proof) that show that this problem is NP-complete for integer side lengths of the squares of the tiling set.

Note that according to the same post, a tiling into rectangles runs in polynomial time.

答案2

得分: 0

以下是翻译好的内容:

一些提示可能会有所帮助。

对于缩减矩阵的表示,也许一个向量更好,因为它需要被存储(start_x,start_y,value……不确定是否需要另一个矩阵非常有用)。

步骤1:在x上循环n次(从y=0开始)

步骤2:在y上循环n次,直到n次出现。在大多数情况下,这里的情况会比m小于n。
(除了m大于n的情况,因为无法做一个正方形)好的,只需保留最小值[m]

步骤3:在向量上标记(start_x,start_y,value)

从x=m开始,重复步骤1-3,直到结束x

步骤4:结束x,从找到的最左边的x(m-in向量,迭代向量)开始调整y。
...

继续直到矩阵结束。

需要非常小心地制定边界(正方形),以便在结果中包含初始矩阵的完全覆盖。

重新构建完整的初始矩阵可以从结果向量中精确地重新组合。

(需要找到间隙并将其放置在从步骤4导出的向量中)

注意!这不是一个完整的解决方案,也许这是如何开始的,并且在每个步骤中弄清楚要调整的内容。

英文:

Some hints may be useful.<br>
<br> For representation of reduced matrix, maybe a vector is better because it's needed to be stored (start_x,start_y,value ... not sure if another matrix very useful).<br>
<br>Step 1: loop on x for n occurrences (start with y=0)
<br>Step 2: loop on y for/untill n occurrences. Most of cases here will be m lees then n.
(case m greater then n excluded since cannot do a square) Fine, just keep the min value[m]
<br>Step 3: mark on vector (start_x,start_y, value)
<br> Repeat Step 1-3 from x=m until end x
<br>Step 4: End x, adjust y starting from most left_x found(m-in vector, reiterate vector).
...
<br>keep going till end matrix.<br>
<br>Need to be very careful of how boundary are made(squares) in order to include in result full cover of initial matrix.
<br> Reformulate full-initial matrix can be recomposed exactly from result vector.
<br>(need to find gaps and place it on vector derived from step_4)
<br><br> Note ! This is not a full solution, maybe it's how to start and figure out on each steps what is to be adjusted.

huangapple
  • 本文由 发表于 2020年4月9日 01:14:26
  • 转载请务必保留本文链接:https://go.coder-hub.com/61106258.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定