在开始之前,我必须说,对于那些具有线性代数背景的人来说,这不是您所知道的矩阵分解。请阅读以下段落以更清楚地了解我要解决的问题。
以下是矩阵及其子矩阵的显着属性/定义:
这就是(空)主矩阵的样子。矩阵中的每个正方形都简称为一个盒子。矩阵可以被视为一种“游戏板”,例如一个棋盘。纵轴使用区间标度(即实数)测量,水平轴使用单调递增的非负整数测量。
子矩阵的“正式”定义是它是包含在主矩阵中的 M 个框的配置,满足以下条件:
垂直单位是主矩阵中垂直轴线之间的间隙。在下图中,垂直单位为 100。
上图说明了一个简单的子矩阵加法。带有橙色边框/框的单位是子矩阵 - 构成我词典一部分的公认单位。你会注意到我在我的子矩阵中引入了进一步的注释。这是因为(使用国际象棋类比),我可以在棋盘上使用两种类型的棋子。 乙 表示黑色块, W (图中未显示),代表一块白色。公认的单位(或词素/子矩阵) 有一个简单的等价关系,允许在白块和黑块之间进行转换。这种关系可用于进一步分解子矩阵以仅使用黑色块、白色块或两者的组合。
为简单起见,我省略了指定等价关系。但是,如果有人觉得所提出的问题在没有额外细节的情况下并不是“太难”,我将很乐意扩大范围。现在,我试图让事情尽可能简单,以避免人们与“信息过载”混淆。
问题变得有点困难,因为上面定义的“识别单元”本身有时会与其他“识别单元”组合形成另一个“识别单元”——即子矩阵(即识别单元)是 "holons" .例如,在上面的第二幅图中,添加到矩阵中的识别单元本身可以进一步分解为“更小的”子矩阵。
这种holarchy类似于(在物理化学中),元素如何形成化合物,然后再形成更复杂的化合物(氨基酸、蛋白质等)。
回到我们的问题,给定一个主矩阵 M,我希望能够做到以下几点:
一世。识别包含在主矩阵中的子矩阵(或识别单元)。这是第一个“矩阵分解”。 (注意:子矩阵必须满足上面给出的标准)
ii.对于每个识别的子矩阵,我希望能够识别它是否可以进一步分解为 2 个或更多识别的子矩阵。这个想法是迭代分解上面步骤 i 中找到的子矩阵,直到达到指定的层次结构级别,或者直到我们有一组无法进一步分解的有限子矩阵。
我试图想出一个算法来帮助我做上面的(i)和(ii)。我将在 C++、Python 或 C# 中实现逻辑(随着优先级的增加),这取决于哪一个最容易做和/或我碰巧得到片段来让我开始实现算法。
最佳答案
我不确定我是否正确理解了这个问题。
所以首先你想找到所有符合你的 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;
}
}
我没有使用最好的数据结构,我已经简化了解决方案。我希望它在某种程度上有帮助。
关于c# - 具有完整子结构的矩阵的 "Matrix decomposition",我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/3704566/