c# - 具有完整子结构的矩阵的 "Matrix decomposition"

Question

在开始之前，我必须说，对于那些具有线性代数背景的人来说，这不是您所知道的矩阵分解。请阅读以下段落以更清楚地了解我要解决的问题。

以下是矩阵及其子矩阵的显着属性/定义:

我有一个 SxP 矩阵，它形成了一个类似 S.P“盒子”结构的网格。这是主矩阵 .

这就是(空)主矩阵的样子。矩阵中的每个正方形都简称为一个盒子。矩阵可以被视为一种“游戏板”，例如一个棋盘。纵轴使用区间标度(即实数)测量，水平轴使用单调递增的非负整数测量。

还有一个额外的子矩阵概念(如前所述)。子矩阵只是特定配置中的盒子的集合，并具有指定给盒子的特定数量和块类型(参见下面的黑色和白色块)。我有这些的有限集 子矩阵 - 我称之为我的 lexicon或用于执行有效矩阵组合/分解的词汇。

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

1 <=M<= 4

任意两个相邻框之间的“间隙”G(即距离)满足:1<= G<= 2*(垂直单位)。

垂直单位是主矩阵中垂直轴线之间的间隙。在下图中，垂直单位为 100。



上图说明了一个简单的子矩阵加法。带有橙色边框/框的单位是子矩阵 - 构成我词典一部分的公认单位。你会注意到我在我的子矩阵中引入了进一步的注释。这是因为(使用国际象棋类比)，我可以在棋盘上使用两种类型的棋子。 乙 表示黑色块， W (图中未显示)，代表一块白色。公认的单位(或词素/子矩阵) 有一个简单的等价关系，允许在白块和黑块之间进行转换。这种关系可用于进一步分解子矩阵以仅使用黑色块、白色块或两者的组合。

为简单起见，我省略了指定等价关系。但是，如果有人觉得所提出的问题在没有额外细节的情况下并不是“太难”，我将很乐意扩大范围。现在，我试图让事情尽可能简单，以避免人们与“信息过载”混淆。

子矩阵中的每个框都包含一个有符号整数，表示项目的单位数。盒子的每个“配置”(连同它的有符号整数和块类型，即黑色或白色块)被称为一个“识别单元”。

子矩阵可以以重叠的方式放置在主矩阵中。无论“框”在哪里重叠，生成的子矩阵框中的单元数都是组成框的单元数之和(如上图第二张图所示)。

问题变得有点困难，因为上面定义的“识别单元”本身有时会与其他“识别单元”组合形成另一个“识别单元”——即子矩阵(即识别单元)是 "holons" .例如，在上面的第二幅图中，添加到矩阵中的识别单元本身可以进一步分解为“更小的”子矩阵。

这种 holarchy类似于(在物理化学中)，元素如何形成化合物，然后再形成更复杂的化合物(氨基酸、蛋白质等)。

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

一世。识别包含在主矩阵中的子矩阵(或识别单元)。这是第一个“矩阵分解”。 (注意:子矩阵必须满足上面给出的标准)

ii.对于每个识别的子矩阵，我希望能够识别它是否可以进一步分解为 2 个或更多识别的子矩阵。这个想法是迭代分解上面步骤 i 中找到的子矩阵，直到达到指定的层次结构级别，或者直到我们有一组无法进一步分解的有限子矩阵。

我试图想出一个算法来帮助我做上面的(i)和(ii)。我将在 C++、Python 或 C# 中实现逻辑(随着优先级的增加)，这取决于哪一个最容易做和/或我碰巧得到片段来让我开始实现算法。

Answer 1

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

所以首先你想找到所有符合你的 2 标准的子矩阵。
我认为这就像图分解问题或集合覆盖问题，您可以在其中使用递归函数并迭代矩阵以找到所有可用的子矩阵。

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;
    }

}

我没有使用最好的数据结构，我已经简化了解决方案。我希望它在某种程度上有帮助。