精华内容
下载资源
问答
  • 向量空间:比如一个维空间、维空间等等,...以 空间为例,他可以含有一个维平面子空间(过原点的一个平面)对于一个m×n的矩阵 ,其蕴含四个重要的基础子空间:1、空间(Column Space)2、空间(Row Space)...

    向量空间:比如一个二维空间、三维空间等等,一般我们定义写作

    ,它代表由
    所有含有n个成分的列向量构成的空间。比如我们
    空间就包含了所有含有3个成分的列向量

    子空间:显然一个

    空间是可以含有很多子空间的。以
    空间为例,他可以含有一个二维平面子空间(过原点的一个平面)

    对于一个m×n的矩阵

    ,其蕴含四个重要的基础子空间:

    1、列空间(Column Space)

    2、行空间(Row Space)

    3、零空间(Null Space),

    4、左零空间(Left Null Space)

    接下来我们挨个看一下。


    一、列空间

    我们对A做下列向量拆分:

    ,
    , ..... ,

    对于矩阵A而言,它包含了n个m维列向量,那么A的列空间就是:这n个m维列向量的线性长成空间(Span)。

    ①我们把矩阵A的列空间记做:

    ①由于每个列向量都是m维的,所以

    的子空间

    ②此时列空间

    中的任何一个向量都可以如下表示:
    (其中
    是一个常量). 这个式子是很精妙的,可以将其展开看一下:
    ,显然这个就代表了列向量可以构成的任意一个向量了。

    ③所以我们可以将

    认为是:A矩阵右乘一个比例因子向量
    的向量空间

    从这延伸一下:对于一个线性方程组可以写成矩阵乘法的形式

    ,只有当向量
    (也就是解向量)可以写成矩阵A的各列的线性组合的形式时,才意味着方程组有解。换句话说:当且仅当
    在矩阵A的列空间中时,方程才有解。

    二、行空间

    我们对A做行向量拆分

    ,
    ,.....,

    同上,我们可以得到如下结论:

    ①我们把矩阵A的行空间记做:

    ②由于每个行向量都是n维的,所以

    的子空间

    ②行空间

    中的任何一个向量都可以如下表示:
    (其中
    是一个常量).
    所以我们可以将
    认为是:A的转置矩阵右乘一个比例因子向量
    的向量空间

    到这一步,我们可以简单做一个总结比较:

    列空间:

    , 行空间:

    由于A的行向量就是

    的列向量, 所以:矩阵A的行空间就是
    的列空间, 最终得出来一个结论:
    =

    三、零空间

    所有满足

    的向量
    的集合就称之为矩阵A的零空间。如果矩阵A的各列线性无关,则
    就只有零向量这个唯一解,如果A的各列线性相关(意味着降维了,进一步是行列式值为零),那么
    就有非零解。


    我们把矩阵A的零空间记做:

    由于A是m*n维,所以向量

    一定是由n个成分构成。所以零空间一定是
    的子空间。

    四、左零空间

    即为

    的零空间,
    .

    之所以强调”“是因为:

    1. 零空间为
      ,是向量在右侧。
    2. 左零空间
      ,向量在
      左侧。

    证:

    按照定义是

    由于

    是n*m维,所以向量
    一定是m个成分构成。所以左零空间一定是
    的子空间。

    五、子空间的度量

    子空间的基

    中的某子空间H的一组基是H中的一个
    线性无关集,它可以生成 H。

    维数(dim): 是针对空间来说的,非零子空间H的维数dim(H)是H的任意一个基的向量个数(线性无关)

    秩(rank):是针对矩阵来说的,矩阵A列空间の维数,也就是矩阵A主元列的个数。

    从上可知:矩阵 A 的列空间 C(A) 的维度就是矩阵 A 的秩 r 。

    比如一个3*5矩阵

    , 则其列空间的维数是:
    =2,类似的,可以看起行空间的维数为
    也为2 。 (本质上维数可以针对行/列这链各个维度,而rank只针对列空间而言.)

    六、四大子空间的维度关系

    对于m*n矩阵A而言,其代表的是一个线性变换:

    1. A的输入是n个基向量各自的长度,所以输入一定是n维的
    2. A的输出,按道理每个输出向量都是由m个分量构成,但是他可能不是满秩的,所以只能算是
      的子空间(比如是3维空间,但是列基底只有2个有效,那最终其实构成的是三维空间中的一个平面而已),所以输出的真正维数是rank(A)=r.

    所以矩阵A做的降/升维转换,降/升的维数数量是n-r

    总结,从维数来看四个子空间之间的联系:

    矩阵A的列空间C(A)的维数是r

    A的行空间

    的维数也是r
    。这是因为其线性无关的行向量的个数其实是和线性无关的列向量的个数相等的。

    零空间

    的维数是n-r
    。因为零空间满足
    , 也就是说经过A变换后的输出是原点,是0维的。那就意味着输入是0+(n-r) = n-r维的。 它的输入是整个零空间,所以我们可知:零空间
    的维数是n-r 。

    左零空间

    的维数是m-r
    。 因为左零空间满足
    ,输入m维, 输出
    的线性无关的列向量个数,而这个等于A的线性无关的列向量个数,也就是其rank值r,所以左零空间的维数是m-r 。

    再观察下,我们可以延伸得出如下结论:

    1、列空间和行空间的维度一致,其实这个维度就是矩阵A的秩(rank, r)

    2、列空间和零空间的维度之和为n

    3、行空间和左零空间的维度之和为m


    七、四大子空间的正交关系

    先看正交的定义:

    1、如果两个向量的点积为零, 那么这两个向量是正交的(垂直)。

    2、如果两个空间的中任意两个向量都是垂直的, 那么这两个空间是正交空间。(两个正交空间的唯一交集是零向量)

    对于四大子空间,这里直接说结论:

    1、列空间和左零空间正交

    2、行空间和零空间正交

    证明一下列空间

    和左零空间
    正交:

    我们从两个空间各任取一个向量,使:u

    ,v

    那么按照定义

    可知:

    从而得知:

    ,.. ,

    v=

    则u·v = u·(

    )

    =

    =0

    最终我们得出如下图来:

    ae02091b0b790f12249c74e5a488af4d.png

    八、子空间正交的意义

    有了两个正交空间,那么对于空间任意一个向量:我们就可以向垂直的两个空间进行投影分解了, 例如向量

    可以向【V空间】和【V垂直空间】分别进行投影了,如下:

    8a2a8e8caa6d760e1c3cd141028273b2.png

    按照前边的结论,我们可以知道:

    1、任意

    空间中的向量:可以向【列空间】和【左零空间】进行分解投影

    2、任意

    空间中的向量:可以向【行空间】和【零空间】进行分解投影

    69587af1044845d182a80b33c0e71040.png

    好了,有了以上基础,我们可以回过头来再看看线性变换的方程的意义

    一、先来对

    进行分解:
    1. 首先
      一定是处于
      空间中的(因为A是m*n矩阵),它经过矩阵A的变换后变成了
    2. 我们可以将
      的两个正交子空间
      上进行分解,分解为:
    3. 那么就可以写成

    继续推导为:

    8caf663864bf419fc1e4e1af98e82060.png

    那么我们接下来分情况分析(对应上图):

    ①如果A是非奇异矩阵(可逆):那意味着A是满秩的方阵,那

    的维度就只能是0,我们常说”非奇异矩阵没有零空间和左零空间“,那它可以做到一一映射,那么行空间中零向量也只映射到列空间的零向量上

    ②如果A是奇异矩阵(不可逆),那A就不满秩,其只能张成r维空间(r < n),剩下的n - r维构成了零空间。 零空间中的向量可能不是零,但在A的线性变换作用下却映射到列空间的零向量上(这是零空间的定义,满足Ax=0的所有x构成的空间)

    那最终得到的结果就是

    二、我们再换个思路,来对

    进行分解:
    1. 首先
      一定是处于
      空间中的(因为A是m*n矩阵)
    2. 我们可以将
      的两个正交子空间
      上进行分解,分解为:
    3. 那么就可以写成

    d5b96484ca12668a74b2937dd401ad00.png

    三、再延伸下,对于

    1. 如果
      不为0,意味着A这个变换是降维(丢失信息,对应零空间的归零)
    2. 如果
      不为0,意味着A这个变换是升维(增加信息,对应左零空间)

    九、左零空间的意义

    在上边分析

    时,方法一是对
    进行了分解,在这个过程中:看起来左零空间在(正向的)线性变换中根本不出现,而且只是列空间的正交补,好像没什么意义。

    其实不然。默认在定义矩阵的逆的时候,只对可逆的方阵(非奇异)才有意义,因为可逆矩阵的零空间真的是个零(只有零向量),那么行空间中每个向量都可以一一映射到列空间中,自然映射也就可逆——找出逆矩阵,将原矩阵列空间中的向量再映射回行空间。

    而对于奇异矩阵:因为零空间的存在,零空间中的非零向量会被矩阵映射到零向量上。那么无论如何,我们都没法再找出一个矩阵,能把零向量映射回原零空间中的非零向量了——变成零后信息已经丢失了。这也是“不可逆”的原因。(相当于零空间是一定会压缩到一个点的)

    但是对于不可逆的矩阵,可以定义其“伪逆”(pseudo-inverse)。

    正向变换:行空间映射到列空间,零空间映射到零向量

    逆向变换:列空间映射回行空间,左零空间则映射到零向量

    求伪逆的方法,其中一种是对矩阵 A做奇异值分解(SVD),将其变成两个正交矩阵和一个对角矩阵的乘积。正交矩阵一定可逆,其伪逆就是其逆;对角矩阵如果对角线不含零元素(对角矩阵也可逆),求逆时取对角线元素的倒数即可;不可逆矩阵的 SVD 中,对角矩阵一定含有零元素,那么求伪逆时只对非零元素取倒数,零元素仍然取零(对应左零空间仍然映射到零向量),得出对角矩阵伪逆。再将三个逆和伪逆重新合成,得到 A的伪逆。

    展开全文
  • 矩阵乘法的种视角 后续图卷积网络的原理讲解主要以矩阵乘法的显示展开,这里介绍矩阵乘法的几种不同的视角,这些视角有助于我们理解图卷积网络的逻辑过程。...矩阵CCC 的第i 第 j 是由矩阵 AAA 的第iii 和

    矩阵乘法的三种视角

    后续图卷积网络的原理讲解主要以矩阵乘法的显示展开,这里介绍矩阵乘法的几种不同的视角,这些视角有助于我们理解图卷积网络的逻辑过程。

    对于矩阵 ARm×nA\in R^{m\times n} 和 矩阵 BRn×pB \in R^{n\times p},它们的乘积 CRm×pC \in R^{m \times p},可以由如下三种视角计算得到。

    • 內积视角:这是我们本科阶段就接触到的视角。矩阵CC 的第i 行第 j 列是由矩阵 AA 的第ii 和矩阵BB 的第j列做內积运算得到。
      即:ci,j=Ai,×B,j=k=1nai,kbk,jc_{i,j}=A_{i,*}\times B_{*,j}=\sum_{k=1}^{n} a_{i,k}*b_{k,j}Ai,A_{i,*}表示A的第i行,B,jB_{*,j}表示B的第j列。
    • 行向量视角:矩阵 CC的第 ii 行可以看做矩阵BB 的所有行向量以矩阵AA 的第i行为系数,线性组合而得到。这里的逻辑是:矩阵 CC 的第 ii 行的形状是 1×p1\times p,该形状与矩阵BB 的每一行的形状(1×p1 \times p)是一致的。因此我们看可以把 CC的第ii 行,看成是矩阵 BB 的所有行的线性组合。那么组合过程的系数是谁呢?因为每次组合,需要对矩阵BBmm 个行向量进行组合,那么势必需要 mm 个系数,每个系数负责去乘以一个行向量,很自然地 矩阵AA 的第ii 列 恰好是有mm 个元素的,可以充当系数。
      于是我们有:Ci,=A,i×BC_{i,*}=A_{*,i} \times B
    • 列向量视角: 矩阵 CC的第ii 列,可以看做是矩阵 AA的所有列向量,以矩阵BB 的第ii 行 为系数,线性组合而成。
      我们有:C,i=A×Bi,C_{*,i}=A \times B_{i,*}

    举个例子来说:
    对于矩阵 :
    A=[112021]B=[201101]C=A×B=[3321] A= \begin{bmatrix} 1 &-1 &2 \\ 0 & 2 &1 \end{bmatrix} \quad B=\begin{bmatrix} 2 & 0 \\ -1 & 1\\ 0 & -1 \end{bmatrix} \quad C=A\times B=\begin{bmatrix} 3 &-3\\ -2&1 \end{bmatrix}

    內积视角:c0,0=A0,×B,0=[112]×[210]=3c_{0,0}=A_{0,*}\times B_{*,0}=\begin{bmatrix}1&-1&2\end{bmatrix} \times \begin{bmatrix}2\\-1\\0\end{bmatrix}=3

    行向量视角:C0,=A0,×B=[112]×[201101]=1×(20)+1×(11)+2×(01)=(33) \begin{aligned} C_{0,*}= A_{0,*} \times B=\begin{bmatrix}1&-1&2\end{bmatrix} \times \begin{bmatrix} 2 & 0 \\ -1 & 1\\ 0 & -1 \end{bmatrix}=1\times \begin{pmatrix}2&0\end{pmatrix} + -1 \times \begin{pmatrix}-1&1\end{pmatrix}+2 \times \begin{pmatrix}0&-1\end{pmatrix}\\=\begin{pmatrix}3&-3\end{pmatrix} \end{aligned}

    列向量视角:
    C,1=A×B,1=[112021]×[011]=0×(10)+1×(12)+1×(21)=(31) C_{*,1}=A \times B_{*,1} = \begin{bmatrix} 1 &-1 &2 \\ 0 & 2 &1 \end{bmatrix} \times \begin{bmatrix} 0 \\ 1\\ -1 \end{bmatrix}=0 \times \begin{pmatrix}1\\0\end{pmatrix}+ 1 \times \begin{pmatrix}-1\\2\end{pmatrix}+ -1 \times \begin{pmatrix}2\\1\end{pmatrix}=\begin{pmatrix}-3\\1\end{pmatrix}

    图信号

    给定图 G=(V,E)G=(V,E ),其中 VV 表示节点集合,假设节点个数为 NN , E={(u,v)uV,vV}E=\{(u,v)|u\in V,v \in V\} 表示边集合。
    所谓的图信号,是图节点到mm维向量空间RmR^m的一个映射,即:VRmV\to R^m,表示成向量的形式:x=[x1x2xN]\bold{x}=\begin{bmatrix}x_1\\x_2\\\dots\\x_N\end{bmatrix},其中 xix_i 表示第ii 个节点的特征信号。

    为了方便后续的讲解,我们先把mm 限制为1。

    在研究图上面节点特征信号的时候,除了要自然而然的考虑图信号本身以外,还需要考虑图里面节点之间的连接关系,不同图上同一特征信号具有不同的性质。

    拉普拉斯矩阵是用来研究图结构性质的核心对象,它负责将图中节点之间的连接关系以矩阵的方式引入到模型之中,它充当了一个离散图信号与图拓扑关系之间的桥梁的角色。

    拉普拉斯矩阵的定义为:L=DAL=D-A ,其中AA 是图的邻接矩阵,如果Aij=1A_{ij}=1 说明存在 (i,j)E(i,j)\in E,如果Aij=0A_{ij}=0 说明(i,j)E(i,j)\notin E,而且规定Aii=0A_{ii}=0;而 DD 是节点的出度矩阵,它是一个对角矩阵,其中Dii=j=1NAijD_{ii}=\sum^{N}_{j=1}A_{ij}。因此 LL 的计算为:
    Dij={0,if (i,j)E1,if (i,j)E,ijDij,if i=j D_{ij}=\left\{ \begin{aligned} 0 &,if \space(i,j)\notin E \\ -1&,if \space (i,j) \in E, i \neq j \\ D_{ij} &, if \space i= j \end{aligned} \right.

    为啥说拉普拉斯矩阵是个桥梁呢 ?
    我们可以看到特性信号向量 x\bold{x} 里面的每个元素是独立的,如果我们往x\bold{x} 左乘它所在图的拉普拉斯矩阵 LL
    即:x=Lx\bold{x'}= L\bold{x} 。我们看可以得到什么:
    x=Lx=(DA)x \begin{aligned} \bold{x'}=L\bold{x}=(D-A)\bold{x} \end{aligned}
    因为LL 的形状是N×NN\times N,而x\bold{x}的形状为N×1N\times1,于是它们乘积的结果x\bold{x'} 的形状是N×1N\times1
    如果我们从行向量视角来看x\bold{x'}的计算的话,那么x\bold{x'}的第ii 行可以看做是 x\bold{x}的所有行的线性组合,而组合的系数是 LL的第ii 行 ,即有:
    xi=Lix \bold{x'_i}=L_{i*}\bold{x}
    LL的第ii 里面,LiiL_{ii} 是节点ii 的出度,Lij=0L_{ij}=0 如果不存在节点ii 到节点 jj的边,否则Li,j=1L_{i,j}=-1。因此
    xi=Lix=j{j(i,j)E}Aijxij{j(i,j)E}Aijxj=j{j(i,j)E}AijxiAijxj=j{j(i,j)E}(xixj) \begin{aligned} \bold{x'_i}=L_{i*}\bold{x}=\sum_{j\in\{j|(i,j)\in E\}}A_{ij}x_i-\sum_{j\in \{j|(i,j)\in E\}}A_{ij}x_{j}\\=\sum_{j\in\{j|(i,j)\in E\}}A_{ij}x_i-A_{ij}x_{j}=\sum_{j\in\{j|(i,j)\in E\}}(x_i-x_{j}) \end{aligned}
    也就是:x\bold{x'}的第ii 个元素表示用节点ii 与其他所有从它出去的节点的特征信号差的和。

    这反映了ii 节点的信号值与其他相邻节点信号值之间的差异程度。

    当然了,这个差值的和是带符号的,如果出现一正一负的数据,他们进行求和后数值本身的绝对值会下降。
    如果能够使用差的平方和就好了!

    于是在x\bold{x'} 的基础上,我们左乘一个 xT\bold{x}^T:
    p=xTx=xTLx=i=1Nxi[j{j(i,j)E}(xixj)]=i=1Nj{j(i,j)E}(xi2xixj)=x12x1x2+x12x1x3++x12x1xj+x22x1x2+x22x2x3++x22x2xj++xN2x1xN+xN2xNx2++xN2xNxj+=(x122x1x2+x22)+(x122x1x3+x32)++(x122x1xN+xN2)+(x222x2x3+x32)++(x222x2xN+xN2)+={i,j(i,j)E}(xixj)2 \begin{aligned} p=\bold{x}^T\bold{x'}=\bold{x}^TL\bold{x'}=\sum_{i=1}^{N}x_{i}[\sum_{j\in\{j|(i,j)\in E\}}(x_{i}-x_{j})]\\ =\sum_{i=1}^{N}\sum_{j\in\{j|(i,j)\in E\}}(x_{i}^2-x_{i}x_{j})\\ =x_{1}^{2}-x_1x_2+x_1^2-x_1x_3+\dots+x^2_1-x_1x_j+\\ x_{2}^{2}-x_1x_2+x_2^2-x_2x_3+\dots+x^2_2-x_2x_j+\\ \dots +\\ x_{N}^{2}-x_1x_N+x_N^2-x_Nx_2+\dots+x^2_N-x_Nx_j+\\ =(x_1^2-2x_1x_2+x^2_2)+(x^2_1-2x_1x_3+x^2_3)+\dots+(x^2_1-2x_1x_N+x^2_N)+\\ (x^2_2-2x_2x_3+x^2_3)+\dots+(x^2_2-2x_2x_N+x^2_N)+\dots\\ =\sum_{\{i,j|(i,j)\in E\}}(x_i-x_j)^2 \end{aligned}
    我们把这个标量叫做图信号的总变差,记做 TV(x)=xTLxTV(\bold{x})=\bold{x}^TL\bold{x} .
    TV(x)TV(\bold{x}) 反映了图上各节点信号的平滑程度,而且总变差总是非负的。

    展开全文
  • 目录1维数组与矩阵的联系2逆时针输出维数组元素2.1模拟...把矩阵看做列向量得出矩阵的维数,比如四行三列矩阵可以看成三个列向量表示的四维空间。 m×mm \times mm×m的矩阵可以看做是mmm阶方阵 2逆时针输出维数

    说明: 关于二维数组的题型总结会持续更新。

    1二维数组与矩阵的联系

    数组一般是指数据结构,矩阵是数学概念。
    在逻辑上一般把二维数组看成是一个具有行和列的矩阵。把矩阵看做列向量得出矩阵的维数,比如四行三列矩阵可以看成三个列向量表示的四维空间。
    m×mm \times m的矩阵可以看做是mm阶方阵

    2逆时针输出二维数组元素

    2.1模拟法

    可以模拟打印矩阵的路径。初始位置是矩阵的左上角,初始方向是向右,当路径超出界限或者进入之前访问过的位置时,则顺时针旋转,进入下一个方向。

    判断路径是否进入之前访问过的位置需要使用一个与输入矩阵大小相同的辅助矩阵visited\textit{visited},其中的每个元素表示该位置是否被访问过。当一个元素被访问时,将 visited\textit{visited} 中的对应位置的元素设为已访问。
    算法思路

    • 判断矩阵是否为空,若为空返回空
    • 定义访问记录的辅助矩阵,Boolean数组与原数组大小相同,若为true则表示该位置已经访问过了。
    • 定义方向数组,共四个方向表示逆时针遍历
    • 循环下列不走直到遍历完所有数组
      \quad 将二维数组的当前元素放置到结果一维数组中
      \quad计算下一次遍历的列下标和行下标
      \quad判断逆时针遍历一圈完成的事件有:(1)下一次行下标和下一次列下标越数组的界;(2)下一次遍历的元素已经访问过了
      \quad再次计算下一次遍历的下标

    在这里插入图片描述

    算法复杂度分析

    时间复杂度:循环次数为m×nm \times n,故时间复杂度为O(mn)O(mn)
    空间复杂度:O(mn)O(mn)。除了输出数组以外,空间复杂度是常数

    2.2按层模拟

    定义矩阵的第 k 层是到最近边界距离为 k 的所有顶点。
    对于每层,从左上方开始以顺时针的顺序遍历所有元素。假设当前层的左上角位于 (top,left)(top,left),右下角位于(bottom,right)(bottom,right),按照如下顺序遍历当前层的元素。

    • 从左到右遍历上侧元素,依次为(top,left)(top,left)(top,right)(top,right)
    • 从上到下遍历右侧元素,依次为(top+1,right)(top+1,right)(bottom,right)(bottom,right)
    • 如果left<rightleft<righttop<bottomtop<bottom,则从右到左遍历下侧元素,依次为 (bottom,right1)(bottom,right−1)(bottom,left+1)(bottom,left+1),以及从下到上遍历左侧元素,依次为 (bottom,left)(bottom,left)(top+1,left)(top+1,left)
    • 遍历完当前层的元素之后,将left 和top 分别增加 1,将right 和 bottom 分别减少 1,进入下一层继续遍历,直到遍历完所有元素为止。
      在这里插入图片描述

    算法复杂度分析

    时间复杂度:循环次数为m×nm \times n,故时间复杂度为O(mn)O(mn)
    空间复杂度:O(1)O(1)。除了输出数组以外,空间复杂度是常数

    3查找指定的元素

    3.1暴力法

    遍历数组的所有元素,直到找到目标值后结束遍历。

    3.1.1复杂度分析

    m×nm \times n的二维数组,在循环遍历时最大的循环次数为m×nm \times n,故时间复杂度为O(mn)O(mn)

    3.2 线性查找

    对数组的要求是有序,有序指的是:二维数组具备每行从左到右递增以及每列从上到下递增的特点。(非递减即可)

    思路描述: 从右上角开始查找,若当前值大于目标值则需要向左移,即列下标减1;若当前值小于目标值则需要向下移,即行下标加1;若当前值等于目标值则返回true或者返回该下标(位置);若行下标或列下标超出数组的范围,则返回false。

    算法流程:

    • 若数组为空,返回 false
    • 初始化行下标为 0,列下标为二维数组的列数减 1
    • 重复下列步骤,直到行下标或列下标超出边界
      \qquad获得当前下标位置的元素 num
      \qquad 如果 num 和 target 相等,返回 true
      \qquad如果 num 大于 target,列下标减 1
      \qquad如果 num 小于 target,行下标加 1
    • 循环体执行完毕仍未找到元素等于 target ,说明不存在这样的元素,返回 false。

    3.2.1复杂度分析

    遍历时行下标最多增加mm,列下标最多减少nn,所以最多执行m+nm + n次,所以时间复杂度为O(m+n)O(m + n)

    题型总结目录

    题型总结——前K系列(堆、优先队列).
    题型总结——二分查找(中间点计算的改进).
    题型总结——二维数组(矩阵)之逆逆时针输出、查找.
    题型总结——栈的应用.
    题型总结——双指针算法全部模型(持续更新).

    展开全文
  • 假设有一个矩阵Matrix,它共有RowCount,每有ColCount,当利用y表示行数,x表示数,那么利用Matrix[y,x]就可以访问矩阵中的任意元素。假设有一个10×10大小的矩阵,它的遍历方法有以下种:此主题相关图片...

    二、矩阵遍历

      矩阵遍历是一个数据结构方面的问题。假设有一个矩阵Matrix,它共有RowCount行,每行有ColCount列,当利用y表示行数,x表示列数,那么利用Matrix[y,x]就可以访问矩阵中的任意元素。假设有一个10×10大小的矩阵,它的遍历方法有以下三种:


    此主题相关图片如下:
    (图1)
     

    在上图中矩阵中的数字表示遍历到元素的先后次序,箭头表示遍历的方向。第一种的一般遍历法在很多编程书上都有介绍,而且经常作为循环代码的示范程序使用。这种遍历方法稍加修改就可以做到从右上角开始、从左下角开始、从右下角开始。这种遍历方法很简单,这里就不多说了。与一般遍历相反,螺旋遍历在所有的编程书和数据结构书上都没有讲到。现在详细的说明一下螺旋遍历。
     

      螺旋遍历可以做到以一个基点为中心向四周遍历,这个基点可以不是矩阵的中心点,实际上基点可以是矩阵上的任意一点,甚至可以是矩阵外的点。注意:这里所说的“点”是指可以用(y,x)访问的元素,当(y,x)坐标超出矩阵范围,例如(-1,-1),这就是矩阵外的点。可以看出螺旋遍历对于找图找色非常有用。螺旋遍历实现起来并不难,仔细观察图1中的螺旋遍历就会发现遍历可以由遍历方向和遍历步数组成。从(3,2)点开始向上遍历一步,再向右遍历一步,再向下遍历二步,再向左遍历二步,这时完成一轮,遍历方向又开始向上、向右、向下、向左一轮又一轮,同时遍历步数逐步加大。当向上遍历时y总是减1;当向右遍历时x总是加1;当向下遍历时y总是加1;当向左遍历时x总是减1,这样可以根据遍历方向计算出坐标的变化。另外螺旋遍历有可能会访问到矩阵外的点,在访问时要进行判断。正是由于螺旋遍历会访问矩阵外的点,遍历循环将无法停止从而出现死循环。这时要设定一个访问计数VisitCount,当遍历循环访问了矩阵中的所有点后退出循环。综上所述,螺旋遍历的示范代码如下:

    type
        //遍历方向
        TAspect = (asLeft, asRight, asUp, asDown);

    const
        //移动坐标差
        MoveVal : array [asLeft..asDown] of TPoint = (
            (X : -1; Y :  0), //asLeft
            (X :  1; Y :  0), //asRight
            (X :  0; Y : -1), //asUp
            (X :  0; Y :  1)  //asDown
        );

        //矩阵大小
        RowCount = 10;
        ColCount = 10;

    var
        //矩阵
        Matrix : array [0..RowCount-1,0..ColCount-1] of Integer;

    //螺旋遍历(不支持步长)
    procedure MatrixOrder1_(y,x : Integer);
    var
        Aspect : TAspect;
        VisitCount,Count,i : Integer;
    begin
        VisitCount:=0;
        Aspect:=asUp;
        Count:=1;
        while VisitCount<(RowCount*ColCount) do
        begin
            for i:=0 to Count-1 do
            begin
                if (x>=0) and (x<ColCount) and
                   (y>=0) and (y<RowCount) then
                begin

                    //访问矩阵元素
                    Matrix[y,x]:=VisitCount;

                    VisitCount:=VisitCount+1;
                end;
                x:=x+MoveVal[Aspect].X;
                y:=y+MoveVal[Aspect].Y;
            end;
            case Aspect of
                asLeft  : begin Aspect:=asUp;   Count:=Count+1; end;
                asRight : begin Aspect:=asDown; Count:=Count+1; end;
                asUp    : begin Aspect:=asRight; end;
                asDown  : begin Aspect:=asLeft;  end;
            end;
        end;
    end;

      这里还有一个步长的问题,所谓步长就是指在遍历的时候跳过一些点,只平均访问矩阵中的某些点。例如以下数据就是步长为2以(3,2)为基点的螺旋遍历后的矩阵,其中“-”表示遍历时没有访问到的点。

    输出矩阵:
       +  0  1  2  3  4  5  6  7  8  9
     0 :  -  -  -  -  -  -  -  -  -  -
     1 :  8  -  1  -  2  -  9  - 16  -
     2 :  -  -  -  -  -  -  -  -  -  -
     3 :  7  -  0  -  3  - 10  - 17  -
     4 :  -  -  -  -  -  -  -  -  -  -
     5 :  6  -  5  -  4  - 11  - 18  -
     6 :  -  -  -  -  -  -  -  -  -  -
     7 : 15  - 14  - 13  - 12  - 19  -
     8 :  -  -  -  -  -  -  -  -  -  -
     9 : 24  - 23  - 22  - 21  - 20  -

      使用步长可以实现矩阵的抽样查找,但上面给出的螺旋遍历算法却不支持步长。因为它要利用访问计数退出循环,使用步长时会使矩阵中访问到的点的数目不确定,使的上述算法出现死循环。对上述算法的一个改进是使用一个逻辑变量记录遍历一轮是否有访问到点。如果没有,说明这一轮访问已经以位于矩阵之外可以退出循环。当步长为1时这种改进的算法要比前面的算法更慢,因为它要“空转”一轮。而且这种算法也不支持矩阵外的点作为基点,它会使循环提前退出。支持步长的螺旋遍历算法的示范代码如下:注意这时的VisitCount仅作为测试使用,不作为退出循环的条件。

    type
        //遍历方向
        TAspect = (asLeft, asRight, asUp, asDown);

    const
        //遍历步长
        Interval = 2;

        //移动坐标差
        MoveVal : array [asLeft..asDown] of TPoint = (
            (X : -Interval; Y : 0), //asLeft
            (X :  Interval; Y : 0), //asRight
            (X : 0; Y : -Interval), //asUp
            (X : 0; Y :  Interval)  //asDown
        );

        //矩阵大小
        RowCount = 10;
        ColCount = 10;

    var
        //矩阵
        Matrix : array [0..RowCount-1,0..ColCount-1] of Integer;

    //螺旋遍历2(支持步长)
    procedure MatrixOrder2(y,x : Integer);
    var
        Aspect : TAspect;
        VisitCount : Integer; //访问计数,测试用
        Count,i : Integer;
        Visit : Boolean;
    begin
        VisitCount:=0; //访问计数,测试用
        Visit:=false;
        Aspect:=asUp;
        Count:=1;
        while true do
        begin
            for i:=0 to Count-1 do
            begin
                if (x>=0) and (x<ColCount) and
                   (y>=0) and (y<RowCount) then
                begin

                    //访问矩阵元素
                    Matrix[y,x]:=VisitCount;
                    VisitCount:=VisitCount+1; //访问计数,测试用

                    Visit:=true;
                end;
                x:=x+MoveVal[Aspect].X;
                y:=y+MoveVal[Aspect].Y;
            end;
            case Aspect of
                asLeft : begin
                    if not Visit then break;
                    Visit:=false;
                    Aspect:=asUp;
                    Count:=Count+1;
                end;
                asRight : begin Aspect:=asDown; Count:=Count+1; end;
                asUp    : begin Aspect:=asRight; end;
                asDown  : begin Aspect:=asLeft;  end;
            end;
        end;
    end;
     
      对于回形遍历与螺旋遍历大同小异,这里就不多说了。在下面的压缩包中是矩阵遍历的示范程序,里面有一般遍历、螺旋遍历和回形遍历的示范代码,可以用于参考。

    转载于:https://www.cnblogs.com/MaxWoods/archive/2013/06/14/3135360.html

    展开全文
  • 【线性代数】矩阵种相乘方式

    万次阅读 2017-07-24 19:58:50
    它只有在第一个矩阵数(column)和第矩阵的行数(row)相同时才有意义[1] 。一般单指矩阵乘积时,指的便是一般矩阵乘积。一个m×n的矩阵就是m×n个数排成mn的一个数阵。由于它把许多数据紧凑的集中到了...
  • 矩阵

    2020-07-16 12:39:25
    Aij是指第i,第j的元素。 、向量 向量是一种特殊的矩阵,如下图所示为四位列向量(4×1) 对于向量索引,一般采用1索引向量,如下图所示。 矩阵加法 四、矩阵乘法 1. 2. 矩阵乘法的性质: 1.矩阵...
  • 要创建包含多行的矩阵,请使用分号分隔各。 a = [1 2 3; 4 5 6; 7 8 10] 创建矩阵的另一种方法是使用ones、zeros或rand等函数。例如,创建一个由零组成的 5×1 向量。 z = zeros(5,1) 矩阵和数组...
  • 节、矩阵乘法

    2016-08-11 00:24:00
    我们之前已经接触了一些矩阵乘法的规则...即如果第一个矩阵是m×n的,那么第个必须是n×p的,其中m、n、p为任意正整数(ab可以用a×b表示) 、基本性质 满足结合律 A(BC)=(AB)C 满足交换律 A(B+C)=AB+...
  • 小凸和小方是好朋友,小方给小凸一个 N×M(N≤M)的矩阵 A,要求小凸从其中选出 N 个数,其中任意两个数字不能在同一或同一,现小凸想知道选出来的 N 个数中第 K大的数字的最小值是多少。 输入格式 第一给出...
  • 矩阵 对于2×2矩阵 总的公式: C是代数余子式公式,CTC^TCT是伴随矩阵 怎么得到这个矩阵 目的就是证明这个式子 克拉默法则 ...因为CTbC^TbCTb就是某个矩阵的行列式啊 ...三行,对应个向量,对应箱子的...
  • 矩阵中断第i,第j,就是两个相乘矩阵中第一个矩阵第i,第矩阵第j的点乘结果: C34 即位,A的第三行乘以B的第四 矩阵乘法的要求 如果A是m×n,B是n×p,那结果就是 m×p的 对矩阵相乘的种理解 ...
  • 一、矩阵的定义一个m×n矩阵M是一个m、n的矩形实数数组。的数量指定了矩阵的维数。矩阵中的数值称为元素。我们使用组成的双下标Mij来标识矩阵元素,其中,第1个下标指定了元素的所在的,第2个下标...
  • 矩阵键盘的改进(第一个专利)

    万次阅读 热门讨论 2015-12-09 21:20:25
    目前已经申请专利成功了,就拿出来...设置在第一列第一行、第二列二行、第三列第三行、第四列第四行的电路单元为二极管,设置在4×5矩阵其余位置的电路单元为按键触点;4个二极管的正极与负极分别对应相应的列的导线和
  • 矩阵乘法

    2017-08-19 22:10:00
    它只有在第一个矩阵数(column)和第矩阵的行数(row)相同时才有意义[1] 。一般单指矩阵乘积时,指的便是一般矩阵乘积。一个m×n的矩阵就是m×n个数排成mn的一个数阵。由于它把许多数据紧凑的集中到了...
  • 矩阵基本运算

    2016-01-27 12:27:00
    这m×n 个数称为矩阵A的元素,简称为元,数aij位于矩阵A的第i第j,称为矩阵A的(i,j)元,以数 aij为(i,j)元的矩阵可记为(aij)或(aij)m × n,m×n矩阵A也记作Amn 矩阵加法: 应该注意的是只有同型矩阵...
  • 我们在一维数组中已经用了很多的内容进行讲解,那么对于维数组来说...上面定义表示的是34的一个维数字,我们可以理解为3×4的一个矩阵 我们可以这样来理解, int [4] arr[3] 前面部分表示类型,后面部分表...
  • MATLAB矩阵的寻访

    2020-07-11 17:41:12
    例:A(3,5) 表示矩阵A的第三行第五。 2. 单下标标识法 以m×n的矩阵A为例,若全下标的元素位置是“第a,第b”,那么相应的单下标则为c=(b-1)m+a。      例:p=1 3 4 &...
  • 第八章第题(游戏:找到翻转的单元格)(Game: find flipped cells) *8.23(游戏:找到翻转的单元格)假设给定一个填满0和1的6×6矩阵,所有的和列都有偶数个1。让用户翻转一个单元(即从1翻成0或者从0翻...
  • 维数组

    2020-11-05 18:40:31
    位数组的背景环境: 维数组与一维数组相似,但是用法上要比一维数组复杂一点。后面的编程中,维数组用得很少,因为维数组的本质就是一维数组,...大白话 就是 三行 表示定义了一个 3×4,即 3 4 总共
  • 返回一个向量s,s的第一个元素是矩阵的行数,第个元素是矩阵数 输出:s= 3 4 [r,c]=size(A) 将矩阵A的行数返回到第一个输出变量r,将矩阵数返回到第个输出变量c 输出:r=3 c=4 [r,c,m]=size(A) ...
  • 1 更加抽象 线性代数帮助我们更好的理解多维的数据,当还是维、维...再学校里,老师只强调了 × 矩阵相乘方法,说白了就是会算就了,但是这并不利于我们理解矩阵相乘的本质,以下矩阵相乘的观点可以增加...
  • 一 目录 不折腾的前端,和咸鱼有什么区别目录一 目录 题目 解题思路四 统计分析五 解题套路 题目 编写一种算法,若M × N矩阵中某个元素为0,则将其所在的清零。 示例 ...
  • 对于一个N × M的整数矩阵A,小Hi知道每一的整数之和依次是P1, P2, … PN,每一的整数整数之和依次是Q1, Q2, … QM。 你能构造出一个矩阵A,满足每个元素Aij都是非负的,并且满足上述行列之和吗? Input 第一...
  • ,所以棋子在攻击范围的第二行,直接0分,调了几个小时 一眼看数据范围,肯定是状压没跑了 冷静分析一波,状态数64,对当前状态有影响的只有上一行,所以f[n][s0][s1]f[n][s0][s1]f[n][s0][s1]维数组,用回滚数组...
  • 维数组井字棋

    2020-08-17 18:37:52
      本游戏获胜是指在同一、同一或同一对角线上,有个相同字符。 #include <stdio.h> int main() { //定义变量 const int size = 3; int board[size][size]; int i, j; int numofXr,
  • 解题思路:通过组长的分享了解到两次单调队列的解法,思路为先用一个一维队列找出每一长度为k区间的最大值,在通过另一个维的队列找出的最大值,最后求和即为答案。 #include<iostream> #include<...

空空如也

空空如也

1 2 3 4 5
收藏数 85
精华内容 34
关键字:

二行二列×二行三列矩阵