让我们考虑方阵
（n 是矩阵 E 的维数并且是固定的（例如 n = 4 或 n=5））。矩阵条目
满足以下条件：
任务是生成所有矩阵 E。我的问题是如何做到这一点？有没有通用的方法或算法？这甚至可能吗？从什么开始？
问问题
1798 次
1 回答
7
天真的解决方案
要考虑的一个简单的解决方案是生成每个可能n的矩阵，其中每个分量都是不大于 的非负整数，然后仅从那些矩阵中获取满足附加约束的矩阵n。那会有什么复杂性？En
每个分量都可以n + 1取值，有n^2分量，就有O((n+1)^(n^2))候选矩阵。那有一个疯狂的高增长率。
我认为这不是一种可行的方法是安全的。
更好的解决方案
一个更好的解决方案如下。它涉及很多数学。
让是满足您要求S的所有矩阵的集合。E让N = {1, 2, ..., n}.
定义：
让度量具有通常的
N定义，除了省略对称性的要求。让
I和J划分集合N。设D(I,J)为nxn矩阵，它具有D_ij = 1when和iis in ，否则。IjJD_ij = 0让
A并B在S。Then与当且仅当存在和划分这样A时相邻。BIJNA + D(I,J) = B当且仅当与 相邻或与 相邻时，我们说
A和B是相邻的。ABBA两个矩阵
A和BinS是路径连通的当且仅当它们之间存在相邻元素的序列S。让函数
M(E)表示矩阵元素的总和E。
引理 1：
E = D(I,J)是 上的度量N。
证明：
这是一个简单的陈述，除了边从I到的情况J。让我们i进来。I_ 然后根据 的定义。让在。如果在，那么和，那么。如果在，那么和，那么。jJE_ij = 1D(I,J)kNkIE_ik = 0E_kj = 1E_ik + E_kj >= E_ijkJE_ik = 1E_kj = 0E_ij + E_kj >= E_ij
引理2 ：
让E. 然后存在和分区这样与。SE != zeros(n,n)IJNE' = E - D(I,J)SM(E') < M(E)
证明：
令(i,j).E_ij > 0让是可以通过成本的有向路径到达I的子集。不能为空，因为在. 不可能，因为不在。这是因为满足三角不等式和。Ni0IiIINjIEE_ij > 0让
J = N - I. 然后I和J都是非空和分区N。根据 的定义I，不存在任何(x,y)这样的E_xy = 0和x在I和y在 中J。因此E_xy >= 1对于所有xinI和yinJ。因此
E' = E - D(I,J) >= 0。这M(E') < M(E)很明显，因为我们所做的只是从Eto get的元素中减去E'。现在，因为E是 上的度量N并且D(I,J)是N（引理 1）和上的度量E >= D(I,J)，我们有E'是 上的度量N。因此E'在S.
定理：
让E在S. 然后E和zeros(n,n)是路径连接的。
证明（通过归纳）：
如果E = zeros(n,n)，则该陈述是微不足道的。假设
E != zeros(n,n)。让M(E)是 中的值的总和E。然后，通过归纳，我们可以假设该陈述对于任何E'具有的矩阵都是正确的M(E') < M(E)。因为
E != zeros(n,n)，根据引理 2 ，我们有一些这样E'的。然后由归纳假设路径连接到。因此是路径连接到。SM(E') < M(E)E'zeros(n,n)Ezeros(n,n)
推论：
该集合S是路径连接的。
证明：
让A并且B在S。由定理和A都B路径连接到zeros(n,n)。因此A是路径连接到B。
算法
推论告诉我们，其中的一切S都是路径连接的。因此，发现所有元素的有效方法S是对以下定义的图执行广度优先搜索。
- 的元素
S是图的节点 - 图的节点由边连接当且仅当它们是相邻的
给定一个节点，您可以通过简单地枚举所有可能的矩阵（其中有）并为每个矩阵生成E来找到所有（可能）未访问的邻居。枚举应该相对简单（除了空集和 之外，每个可能的子集都有一个）。ED(I,J)2^nE' = E + D(I,J)D(I,J)IDD
请注意，在上一段中，E和D(I,J)都是关于 的度量N。因此，当您生成 时E' = E + D(I,J)，您不必检查它是否满足三角不等式-E'是两个度量的总和，因此它是一个度量。要检查它E'，S您所要做的就是验证最大元素 inE'不超过n。
您可以从 的任何元素开始广度优先搜索，S并保证不会错过任何S. 因此，您可以使用 开始搜索zeros(n,n)。
请注意，集合的基数S随着增加而增长得非常快n，因此计算整个集合S只适用于 small n。
于 2013-06-10T17:10:08.170 回答