如何生成满足三角不等式的矩阵？
ang*_*her 5 algorithm math matrix
我们考虑方阵
(n是矩阵E的维度并且是固定的(例如n = 4或n = 5)).矩阵条目
满足以下条件:
任务是生成所有矩阵E.我的问题是如何做到这一点？有没有共同的方法或算法？这甚至可能吗？什么开始？
天真的解决方案
甲幼稚溶液要考虑的是,以产生每一个可能的n-by- n矩阵E,其中每个成分是一个非负整数不大于n,那么从那些只有满足额外的约束矩阵取.那复杂性会是什么？
每个组件都可以采用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 = 1时i是I和j是J,和D_ij = 0其他.让我们
A和B在S.然后A是相邻的对B,当且仅当存在I和J分区N使得A + D(I,J) = B.我们说
A和B是相邻的当且仅当A邻近B或B毗邻A.两个矩阵
A和B在S是路径连接的,当且仅当存在的相邻元件的序列S在它们之间.让函数
M(E)表示矩阵元素的总和E.
引理1:
E = D(I,J)是指标N.
证明:
这是除了一个从边缘去的情况下,一个简单的语句I来J.设i在I和j是J.然后E_ij = 1按照定义D(I,J).让我们k在N.如果k是I,则E_ik = 0和E_kj = 1,所以E_ik + E_kj >= E_ij.如果k是J,则E_ik = 1和E_kj = 0,所以E_ij + E_kj >= E_ij.
引理2:
设E在S这样E != zeros(n,n).则存在I与J分配N,从而E' = E - D(I,J)在S与M(E') < M(E).
证明:
让我们(i,j)这样E_ij > 0.让I成为N可以i通过定向成本路径到达的子集0.I不能为空,因为i在I.I不能N,因为j不在I.这是因为E满足三角不等式和E_ij > 0.我们
J = N - I.然后I,J都是非空的和分区N.通过定义I,不存在任何(x,y)这样E_xy = 0和x是I和y是J.因此,E_xy >= 1对于所有x在I和y中J.因此
E' = E - D(I,J) >= 0.这M(E') < M(E)是显而易见的,因为我们所做的就是减去E要获得的元素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'在S这样M(E') < M(E).然后通过归纳假设E'进行路径连接zeros(n,n).因此E是路径连接zeros(n,n).
推论:
该集合S是路径连接的.
证明:
我们A和B在S.通过定理,A并且B都是路径连接的zeros(n,n).因此A是路径连接B.
算法
该推论告诉我们,一切都在S为道路连通.因此,发现所有元素的有效方法S是对由以下定义的图执行广度优先搜索.
- 元素
S是图的节点 - 当且仅当它们相邻时,图的节点通过边连接
给定一个节点E,您可以E通过简单地枚举所有可能的矩阵D(I,J)(其中包含2^n)并E' = E + D(I,J)为每个矩阵生成来找到所有(可能)未访问的邻居.枚举D(I,J)应该是相对简单的(有一个用于每个可能子集I的D,除了空集和D).
请注意,在前一段中,E并且D(I,J)都是指标N.因此,当您生成时E' = E + D(I,J),您不必检查它是否满足三角不等式 - E'是两个度量的总和,因此它是一个度量.要检查E'是否存在S,您所要做的就是验证最大元素E'是否超过n.
您可以从任何元素开始广度优先搜索,S并保证您不会错过任何元素S.所以你可以开始搜索zeros(n,n).
请注意,集合的基数S随着n增加而增长得非常快,因此计算整个集合S只能处理小的问题n.