具有全息子结构的矩阵的“矩阵分解”

Question

在我开始之前，我得说，对于那些有线性代数背景的人来说，这里说的并不是你们所理解的矩阵分解。请阅读以下段落，以便更清楚地理解我想要解决的问题。

下面是矩阵及其子矩阵的一些重要特性和定义：

1. 我有一个 SxP 的矩阵，它形成了一个像网格一样的结构，里面有 S.P 个“盒子”。这个就是主矩阵。

这是（空的）主矩阵的样子。矩阵中的每个方块被称为一个盒子。可以把这个矩阵看作一种“游戏棋盘”，比如说棋盘。纵轴是用一个区间尺度来测量的（也就是实数），而横轴则是用单调递增的非负整数来测量的。

2. 还有一个子矩阵的概念（如前所述）。子矩阵就是在特定配置下的一组盒子，里面有特定的数字和棋子类型（见下方的黑白棋子），分配给这些盒子。我有一组有限的子矩阵——我称之为我的词汇表，用于进行有效的矩阵组合/分解。

子矩阵的“正式”定义是，它是主矩阵中包含的 M 个盒子的配置，满足以下条件：

• 1 <= M <= 4
• 任何两个相邻盒子之间的“间隙” G（即距离）满足：1 <= G <= 2*(纵向单位)。

纵向单位是主矩阵中纵轴线之间的间隙。在下面的图像中，纵向单位是 100。

上面的图像展示了一个简单的子矩阵相加。带有橙色边框/盒子的单位就是子矩阵——它们是我词汇表中的识别单位。你会注意到我在子矩阵中添加了进一步的注释。这是因为（用棋类比喻），我可以在棋盘上使用两种类型的棋子。B 代表黑棋，而W（在图中未显示）代表白棋。一个被识别的单位（或词素/子矩阵）之间有一个简单的等价关系，可以在白棋和黑棋之间进行转换。这个关系可以用来进一步分解子矩阵，以便使用纯黑棋、纯白棋或两者的组合。

为了简单起见，我省略了等价关系的具体说明。不过，如果有人觉得这个问题没有额外细节就“太简单”了，我会很乐意扩展范围。现在，我尽量保持简单，以避免让人感到“信息过载”。

3. 子矩阵中的每个盒子包含一个带符号的整数，表示某种物品的单位数量。每个“配置”的盒子（连同它的带符号整数和棋子类型，即黑棋或白棋）被称为一个“识别单位”。

4. 子矩阵可以放置在主矩阵中，使它们重叠。无论“盒子”重叠的地方，结果子矩阵盒子中的单位数量是组成盒子中单位数量的总和（如上图第二张所示）。

问题变得稍微复杂一些，因为上面定义的“识别单位”有时会与其他“识别单位”结合，形成另一个“识别单位”——也就是说，子矩阵（即识别单位）是“整体”。例如，在上面的第二张图中，添加到矩阵中的识别单位本身可以进一步分解成“更小”的子矩阵。

这种整体结构类似于在物理化学中，元素形成化合物，然后进一步形成更复杂的化合物（氨基酸、蛋白质等）。

回到我们的问题，给定一个主矩阵 M，我想能够做到以下几点：

i. 识别主矩阵中包含的子矩阵（或识别单位）。这是第一次“矩阵分解”。（注意：子矩阵必须满足上面给出的标准）

ii. 对于每个识别出的子矩阵，我想能够识别它是否可以进一步分解成两个或更多的识别子矩阵。这个想法是迭代地分解在第一步中找到的子矩阵，直到达到指定的层级，或者直到我们得到一组有限的无法进一步分解的子矩阵。

我正在尝试设计一个算法来帮助我完成上述的 (i) 和 (ii)。我会在 C++、Python 或 C# 中实现这个逻辑（按偏好顺序），具体取决于哪个最容易实现，或者我能找到的代码片段来帮助我开始实现这个算法。

Answer 1

我不太确定我是否正确理解了这个问题。

首先，你想找到所有符合你两个标准的子矩阵。这就像是一个图的分解问题或者集合覆盖问题，我觉得可以用递归函数来遍历矩阵，找到所有可用的子矩阵。

enum PieceTypes
{
    White,
    Black
}

class Box
{
    public PieceTypes PieceType { get; set; }

    public uint Units { get; set; }

    public int s, p;
    public Box(PieceTypes piecetype, uint units)
    {
        PieceType = piecetype;
        Units = units;
    }
}

class Matrix
{
    public Box[,] Boxes;
    public int Scale, S, P, MaxNum, MaxDist;
    public List<List<Box>> Configurations;
    public Matrix(int s, int p, int scale, int maxnum, int maxdist)
    {
        S = s;
        P = p;
        Scale = scale;
        Boxes = new Box[S, P];
        MaxNum = maxnum;
        MaxDist = maxdist;
        Configurations = new List<List<Box>>();
    }

    public void Find(List<Box> Config, int s, int p)
    {
        // Check the max number thats valid for your configuration
        // Check that the current p and s are inside matrix
        if (Config.Count() < MaxNum && s >= 0 && s < S && p >= 0 && p < P)
        {

            foreach (Box b in Config)
            {
                if (Valid(b, Boxes[s, p]))
                {
                    Boxes[s, p].s = s;
                    Boxes[s, p].p = p;
                    Config.Add(Boxes[s, p]);
                    break;
                }

            }
            Find(Config, s + 1, p);
            Find(Config, s - 1, p);
            Find(Config, s, p + 1);
            Find(Config, s, p - 1);
        }
        if (Config.Count() > 0) Configurations.Add(Config);
        Config.Clear();
    }

    public bool Valid(Box b1, Box b2)
    {
        // Create your dist funtion here
        // or add your extra validation rules like the PieceType
        if (Math.Sqrt((b1.s - b2.s) ^ 2 + (b1.p - b2.p) ^ 2) <= MaxDist && b1.PieceType == b2.PieceType) return true;
        else return false;
    }

}

我没有使用最好的数据结构，而且我简化了这个解决方案。希望这对你有点帮助。