敬畏自然绿水青山

Month: June 2024

  • ShuffleNet网络结构介绍-CNN模型系列4

    这篇文章将向大家介绍ShuffleNet网络结构的特点，同样也是问题的形式。 问题1：ShuffleNe网络结构提出了什么新的计算结构？该结构有什么特性，和其他类似结构做一个简要的对比。 回答：ShuffleNet采用了分组卷积的计算方式，分组卷积将特征图的不同通道分成一定数目的group，如分为g组（g为分组数量）。如下图左边所示，分组数为3，此时3个组各自进行普通的卷积操作，组之间的信息是隔离的，为了解决这个问题，下图2和3在第一次分组之后进行了通道之间的shuffle，使得隔离的特征可以进行融合。具体的channel shuffle的实现可以参考引文2，也可以用pytorch中的支持张量运算的permute操作进行实现。depth wise convolution可以理解为分组卷积的一种特殊情况，即分成输入通道数的那么多组数，每一组的通道数为1。 下面将要通过图示的方式向大家展示不同的模型结构的参数量上的差异： 经过分组卷积以及通道shuffle后，ShffleNet的FLOPS比ResNet和RestNext的block结构的FLOPS要小。而且合理的分组后和MobileNet相比较准确率和推理时间都有一定的优势。如下图所示。 ShuffleNet v2版本在模型设计方面在模型精度和模型计算复杂度上面做了更好的权衡，特别是模型计算复杂度不仅仅是FLOPS这样的间接指标（因为影响计算时间的还有内存访问耗时，模型并行程度等）。因此在模型推理效率上，将在目标平台上测量速度作为计算复杂度的直接考量。而且通过实验观察，得出一些模型在设计方面的一些指导原则，如：1、过度分组会增加内存访问（memory access cost），2、过度碎片化的机构会影响模型并行化的程度；3、element-wise操作的性能影响不能忽略等等。 问题：ShuffleNet和MobileNet都是面相移动端的计算，比较它们之间的不同。 回答： ShuffleNet用到了分组卷积，并在1*1卷积中用到了channel Shuffle减少了1*1卷积的计算时间，总体达到了更快的计算，适合于对算力更敏感的移动端边缘AI场景应用中。 References

  • 深度学习中反向传播算法的实现介绍-CNN模型系列3

    反向传播算法是最基础的神经网络优化求解算法，我们一般将神经网络看成是一个高维的复杂的复合函数，而且是非凸的，这里先以一个多层感知机的场景为例进行简要说明，比如当前层的每一个节点的输入是上一层的所有节点输出（组成向量x）和参数权重（向量w）的线性函数g(x)= x*w+b，然后在线性函数结果上再套上一个激活函数复sigma(g(x))。当前层的所有节点就可以看成是有多个这样的复合函数sigma(g1(x)),sigma(g2(x)),….sigma(gn(x))。这些复合函数的结果又是下一层的输入向量，以此逐层forward，最后一层输出结果。神经网络的非凸性表现在，如果在中间某一层改变节点的顺序，并且对应调整其影响到的连接到上一层和下一层节点的参数值，神经网络的输出结果不变，这也就说明神经网络如果存在着极小值，可能会出现多种参数配置情况下都能达到这个极小值。 由于神经网络的非凸性，不能直接通过公式求得函数的导数并等于0来求解方程从而得出最佳参数。而一般采用迭代更新参数的方法，每一次可以求出每个参数的梯度，将沿着梯度的方向更新参数（更新的步长与学习率和梯度本身大小都有关系），会使得loss损失逐渐减小，就好像下山的过程，沿着比较陡峭的山坡去下山所走的步数比较少，求解过程也更快。 由于神经网络的层次结构和神经网络复杂复合函数的特性，提出了反向传播算法，其基于神经网络的结构特性和复合函数求导的链式法则，得出从网络的最后层逐层反向求解相关梯度的方法。具有的梯度信息有两个：1为各层的输入的梯度，在公式中称为delta，2为参数的梯度，在公式中为w的偏导。这些梯度都是从最后一层逐层向前去进行求解的，具体的求解过程可以参考引文3和4，在这里不做重复说明。 原始的反向传播算法只针对的是MLP（多层感知机），也就是基于全连接结构的神经网络，而CNN网络结构中用了好多种不同类型的层（layer，如卷积层，池化层，全连接层等等）。而卷积层由于其连接的稀疏性，权值共享特性，其前向的计算方式和全连接有较大的不同。关于池化层和卷积层的反向传播的实现，可以参考引文1和引文2，特别是引文1中通过一个示例场景说明在卷积层的反向回传中为什么要将参数矩阵旋转180度。 References

  • MobileNet网络结构介绍-CNN模型系列2

    这篇短文向大家简要介绍MobileNet系列的CNN网络结构，也主要以问答的形式来进行，问答反应了作者对这个主题题目的思考和找到问题答案的过程，当然还有更多的问题有待读者提出来，欢迎读者朋友们反馈和一起探讨。 问题1：MobileNet 模型系列的网络结构特征和应用目标（场合）？ 回答：MoblieNet顾名思义是面向移动端的深度学习场景，如手机或算力较小的边端智能应用。其中MobileNet V1的模型结构主要采用了Depth wise Convolution取代了传统的CNN卷积进行特征提取。这里简要介绍一下两者的不同，1、一般卷积核的计算特征：在CNN网络结构中，一般在视觉场合的数据以NCHW的形状张量在不同的网络层进行数据的输流动，比如在传统的一个卷积层，其输入为四维张量(N,C_in,H,W)，输出为四维张量（N，C_out, H, W)。其中C_in为输入通道，C_out为输出通道，如果卷积核的大小为（3*3），则一个卷积核的参数量为（3*3*C_in)，即在3*3大小的特征图（feature map）上对每个通道上的数据进行相关性计算，将计算结果输出到输出特征图上的该卷积核对应的某个通道上。所有卷积核的参数量为（3*3*C_in*C_out)。2、Depwise Separable Convolution，该卷积包含两个步骤，第一步的Depth wise Convolution的计算特征：每个卷积核的参数量只为（3*3)，即只与当前自己通道的当前”像素“的周围（包含自己）的9个像素计算相关性，因此输出的通道数和输入的通道数相同，整体参数量为（3*3*C_in)，因此参数量少了C_out倍。同时每一个通道的计算量从3*3*C_in下降到3*3，降低了C_in倍。第二步的逐点卷积可以理解卷积核的大小为1*1， 但是会将不同通道上的同一个位置的点进行相关性计算，即一个卷积核的参数量为（1*1*C_in)，整个的卷积核的参数量为（1*1*C_in*C_out)。 深度可分离卷积相比标准卷积可以减少 8 到 9 倍的计算量。 问题2：MobileNet模型系列的不同版本分别在前面的版本上做了哪些性能的提升？ MobileNetV2仍旧采用了Depwise Separable Convolution来减少计算量，但也有两处重要的改进：1为采用了类似于resnet的重复结构（减少计算量，堆叠在一起可以提升网络的表达能力），缓解了特征退化问题(残差连接)。2为在通道数较少的特征图上取消了ReLU非线性激活层，而采用了线性瓶颈结构，即inverted residual block。即先将低通道数特征图通过1*1卷积上升到高通道数（高通道数采用ReLU或类似的非线性激活函数），然后在高通道数上进行深度可分离卷积然后再通过1*1卷积降低通道数（这时由于通道数较少不采用激活函数）。瓶颈结构（bottleneck）顾名思义就是先将通道数降低然后进行卷积后再还原通道数，类似时间漏斗一样的形状，故此得名。inverted residual block的意思则是反过来的，中间粗上下细的结构。MobileNetv3在之前的版本上继续做了改进，如基于网络结构搜索，和SE(squeeze and excitation)注意力机制，以及特殊的激活函数等，具体可以参考引文2。 References

  • 基于CNN和LSTM的OCR文本识别/语音识别基本原理简介-CNN模型系列1

    在深度学习流行以前，智能化的算法主要依赖传统的统计机器学习算法，这个时候特征工程(feature engineering)就显得特别重要，如何构造好的有区分度的特征成为了机器学习算法性能的关键因素之一。比如早期的基于Haar特征和Adaboost的人脸检测算法，基于HOG特征的人体检测等，都是利用了图像中区域的像素特性构造的人工特征提取算法。特征工程需要相关领域专家去人为设计和构造，针对不同的任务场景很可能要设计不同的特征提取算法，设计及验证过程周期长效率低下门槛比较高。深度学习逐渐流行后，基于CNN的深度网络自动化特征提取方法和深度学习目标任务（网络结构中的head输出）实现了端到端的训练，从而使得算法的设计和实现更加的高效，而且由于深度学习的网络表达能力强大的特性，几乎所有的视觉任务上的性能都超越了传统的基于人为设计的特征工程的传统机器学习算法。 今天向大家介绍的基于深度学习的OCR文本识别也和上面的情况相似，早期的OCR文本识别也是基于手写体或印刷体的文字特征进行人为设计的特征提取算法，整个识别过程流程复杂，不同的阶段需要设计不同的算法去解决相关问题，而基于CNN和LSTM的文本识别算法则在基于大样本的基础上实现了端到端的训练，而且在精度上也达到了更高的水平，也是当前文本识别的关键算法。在该算法过程中，一般是将文本先进行行提取（如基于目标检测的文本行检测算法实现行提取），在提取的文本行的基础上，将文本行对应的图像作为文本识别网路的输入。首先CNN对图像的特征进行提取和建模，然后将特征输入到LSTM网络，LSTM网络对基于文本行的特征进行空间序列建模（可以理解为将长条的文本行切分成一段一段的顺序拼接一起的特征，LSTM基于这个序列顺序进行建模，可以对文本行的当前位置和其前后的位置的关系进行序列建模，关于LSTM的计算实现细节可以参考引文3）。 在实际的数据集中，由于文字的特性不同(有的汉字或字母比较宽，而有的比较窄，甚至汉字或字母之间间隔的宽度在不同的数据集的样本中也不一样，还有空格的个数也不尽相同，以及空格开始或空格的位置也不尽相同。一条文本行的ground truth只有对应的汉字或字母的文本句子，并没有标记每个汉字或字母对应在图像上的位置（否则标记成本太高），因此这里有一个特别的Loss能够简化这种自动对齐的计算，这个Loss称为CTCLoss，其在语音样本和groundtruth以及文本行图像和groundtruth的自动对齐上展示了简易灵活且强大的自动对齐的作用。 CTCLoss计算每一个时刻t下经过s的所有可能的路径的后验概率（首先根据引文7中的Composing the graph部分的规则计算y(s,t), 然后基于y(s,t)采用动态规划的算法分别计算alpha(s,t),beta(s,t)等），最后的loss是所有时刻的的概率和（用log去计算），关于CTCLoss的详细算法原理的介绍可以参考引文7。 基于CNN和LSTM的语音识别的算法原理和上述的OCR文本识别的原理类似，语音样本有长短不同，有停顿时间不同等需要输入和标记（输出）进行动态对齐的功能，CTCLoss同样可以在此处得以较好应用。 References

  • 图的宽度优先遍历又一示例-最小基因变化

    今天向大家介绍另一个图的宽度优先遍历示例-最小基因变化，具体题目的内容请见引文1。这里描述一下问题的分析思路，并给出一个实现仅供参考，期待能看到更多更优秀的代码实现，从中学习以不断进步。 首先我们可以将每一个基因建模为一个图节点，如果两个节点之间只有一个基因变化，则可以认为两个节点相邻，距离为1。距离大于1的两个节点可以不考虑其距离特性（默认为-1，表示为不直接相连）。关于图的表示问题，这里可以用矩阵进行表示，而且由于对称性，我们可以只利用上矩阵来进行图的搜索。 关于起始节点，如果在gene bank里边，则以起始节点开始进行图的宽度优先搜索，如果不再gene bank里边，则需要从gene bank里边去寻找与该节点的距离为1的所有节点作为候选起始节点，然后对所有可能的起始节点，依次调用图的宽度优先遍历搜索找到最短路径。因为每次都只改变一个基因，而且从起始节点到目标节点的距离已经定下来了（按顺序计算不同字母的个数），因此如果找到，我们可以从目标节点逆序看过来，就知道这个最小路径数就是距离（当然要通过搜索才能找到这样的路径），比如起始点和终点的距离为2，有可能搜索的时候，第一个后继节点和第二个后继节点与起始节点的距离都为1，但是第一个后继节点可能与重点的距离为3（又加了一个不同的基因），因此在最短路径搜索的时候会选择基于第二个后继节点。基于此我们可以得出结论，要么没有路径（返回-1），要么就等于起始节点和目标节点的不同基因数（也可能有多个路径，只要有一个路径找到即可返回，基于这点可以对搜索进行优化）。 具体实现代码可以参看引文2，欢迎读者提出优化建议，由于撰写匆忙加以思考过程可能不够全面深入，以及针对上述的问题分析中有任何问题也欢迎提出意见建议。 References

  • 图相关算法实例题分析-蛇梯棋

    图（graph）相关的数据结构在解决实际问题时也会常用到，这里向读者介绍几个相关应用题目并给出解决思路分析和代码实现，欢迎读者朋友们针对相关问题提出意见和建议，用更好的思路和更加高效的方法去解决。 问题1：参考引文1的描述（这里就不再花文字描述问题本身），理解题目确实要花点时间，这里用图示辅以简单的文字重复描述一下，如下图所示，方格编号从左下角开始连续交错方向按数字递增进行编码，下图的示例对应着如下的输入数据：输入：board = [[-1,-1,-1,-1,-1,-1],[-1,-1,-1,-1,-1,-1],[-1,-1,-1,-1,-1,-1],[-1,35,-1,-1,13,-1],[-1,-1,-1,-1,-1,-1],[-1,15,-1,-1,-1,-1]]。可以看出从最后一行开始，第二个格子的数字为15，意思是从2到15(第四行第三列)安排了一个梯子或蛇，可以直接传送不算挪动的步骤，这样到达目标所在地分别是从1->2,15->17,13->14,35->36,四步即可到达。 首先，我们来分析一下题目的含义和根据场景用合适的数据结构建模相关问题，首先根据board去解析数据，构造合理的数据结构和算法解决问题。我们可以看到目标方格 next的编号符合范围是[curr + 1, min(curr + 6, n2)]，可以理解为从curr（当前方格的位置索引）到这些范围内的任何一个值都存在着一条边（等值边，边长为1，没有长短优先级），比如1到2-7这些格子都可以直接到达，因此我们可以将这个问题构建为一颗动态的搜索图。从根节点位置1开始，如存在着节点有梯子和蛇，则同时添加一条curr到梯子或蛇的终点位置编号的边（不需要满足next节点的1-6step的约束，而且这里特别注意一下，规则中说明梯子或蛇不能连续跳，如不能梯子跳过一些格子再连续梯子跳过一些格子），按照上述逻辑该问题为一颗有向图（如13到17存在着边，17到13也存在着边，13到17存在边时board[13]=17,17到13存在边时，即可以从位置17直接跳到13位置时board[17]=13）。 因此上述的问题就转化为了用基于图的深度优先遍历或宽度优先遍历去查找最短路径问题，搜索最短路径用宽度搜索更加合适，因为宽度搜索的过程中第一个达到目标位置的即为路径长度，而深度优先遍历算法需要遍历整个图（也存在着一些剪枝优化的行为）才能找到最短路径问题。 参考引文2提供了两个代码实现，其中第一个提供了深度优先遍历算法的实现，而且可以将搜索可能的路径都列出来，其实现主要采用了回溯递归的方法，特别需要注意的是递归过程中由于子递归返回后状态恢复的问题，由于基于深度优先遍历性能不够够，在某些测试题目上达不到时间要求，因此这道题的更为合理的方法是宽度优先遍历，采用队列结构来实现，将同一宽度的节点先后依次入队列，然后依次pop并将下一个层级的依次入栈，保证每一个访问的节点都是访问的深度最浅的某一个节点。(Solution类为基于深度优先遍历的实现，Solution2为参考的宽度优先遍历的代码，其中深度优先遍历方法做了一定的扩充，可以支持将所有可能的路径都输出出来保存到文件中）。欢迎读者对代码实现提出问题意见和建议，以便更好的去进步。 References

  • Linux常用CLI命令使用方法介绍

    linux作为服务器的常用的系统，其稳定性已经得到较为普遍的认可，在我们开发和系统运维的过程中，经常会用到相关的CLI命令程序（Command Line Interface，因为用linux系统作为服务器，如ubuntu系统，经常会裁剪掉其图形用户窗口的功能，工程师一般都使用过CLI去和系统进行交互）。 第一个向大家介绍的命令为“netstat -tulnp”，netstat是一个网络工具，用以显示当前网络相关的软件和系统网络相关硬件的信息，参数tulnp是个累积的量，t表示显示当前系统所有的tcp sockets（tcp连接），u表示udp连接，n表示显示数字形式的地址和端口，l表示当前监听的端口（一般服务程序启动后会在特定端口监听远程客户端前来访问的连接请求）p代表网络相关的进程。如安装（可以通过sudo apt install mysql-server命令进行安装）并启动（可以通过sudo systemctl start mysql命令进行启动）了mysql服务器后执行命令后会显示mysql进程相关的信息。有时提示需要系统用户才能显示相关信息时，可以在命令前面加上sudo。执行后如下： 如果只想看mysql服务相关的信息，只需执行sudo netstat -tulnp | grep mysql命令，在linux命令中 ‘|’ 可以理解为pipeline模式，前面的命令作为后面命令的输入。而grep在linux中是一个强大的文本搜索匹配工具，可以将满足条件的文本行输出到终端屏幕上。 第二个向大家介绍的命令示例在前面的基础上综合命令awk（过滤提取，和print结合着用，后面$符号后面跟着个数字表示第几列信息），grep以及xargs（将过滤提取的数据作为参数传递给命令行）的使用。比如在你的机器上，docker的本地镜像有点多，或者你想批处理一次性删除满足某些条件的镜像，可以用如下的命令示例来参考： 以上命令的含义为找到含有keyword相关字眼的docker镜像，并且过滤出第三个参数（即为docker镜像的ID），然后将满足这些条件的docker镜像一次批处理进行删除。 这篇文档后面将持续更新，将常用的命令行汇总一下，以备后需查阅。

  • 前缀树应用相关题目思路分析

    今天向大家介绍一种特殊的属性结构的应用，主要是介绍几个相关的题目的分析思路及相关实现。 题目1的描述见参考引文1，为了实现方便起见，Trie树中的单词都是小写英文中的26个字母。参考引文1的网页右边同时提供了一种基于递归的实现，同时求字符字串使用的是std::string类的substr函数（需要注意一下这个函数的参数的含义，第一个参数表示字串起始位置，第二个参数表示字串长度，而不是字串终止位置）。但是这个问题的推荐解法请参考引文2，相对第一种实现有两个地方的明显改进，第一个地方在于通过“for (char ch : word)”访问字符串的每一个单词，而且通过for方式避免了递归调用函数，节省了系统的执行资源。 题目2的要求是添加和搜索单词，具体描述参考引文3，这道题目在上述的基础上做了一定的扩展，支持通配符，需要注意一些边界条件，稍不注意就容易在某些情况出现bug。同时为了应对通配符的情况，代码中某些地方用到了递归调用。总体上也是一种扩展的前缀树应用，具体实现可以参考引文3网页的右边的代码。 题目3的详细描述请见参考引文4，这道题目的要求是已经有词汇表，根据矩形单词盘板的字母排列规则去核实词汇表中的哪些单词可以从矩形单词盘板中排列（字母之间只能和上下左右相连）得出。这里给出我的思路（欢迎读者给出更加高效的解决方案），首先通过按照题目1或2的方法根据词汇表去构建前缀树（一种特殊构造的词汇表），然后根据从矩形框中的每一个位置进行上下左右四个方向的搜索（需要考虑矩形的边界情况进行剪枝），可以理解为对一颗四叉树进行深度优先搜索，参考引文6提供了一个实现，这里也是一种回溯算法，在代码实现的过程中需要考虑回溯状态的复位。 引文5提供了上述三个问题的各一种解决方法，在前面的部分代码没有充分的从效率上进行优化，不过也可以从三个题目中去互相借鉴更优的写法。 References

  • LRU缓存设计实现思路说明

    LRU缓存机制在操作系统和其他缓存系统中常会用到，这里的题目要求是：1、以整数key，value键值对的形式进行存取；2、以一定的容量进行初始化；3、实现get和put操作，如果get传入的key有对应的value值则返回value，否则返回-1，put如果已经有key对应的cache，则更新value值，如果put时容量超限，则逐出最久未使用的关键字。并要求这些实现在O(1)的复杂度里完成。有名的缓存系统redis就是基于LRU的缓存机制实现的。 这道题如果读者没有较为系统的学习和刷题数据结构和算法，也许想不到用哈希表和双向链表相结合去实现，这道题目是数据结构的一道综合题在实际场景下的应用，主要考察两个点，1、哈希函数的即时O(1)时间复杂度寻址能力及其实现（哈希函数功能可以直接用unordered_map数据结构来实现）；2、双向链表的实现，双向链表支持从中间任何位置挪出节点并放置到表头，双向链表的表头和表尾的节点都可以作为哨兵节点（用变量存储head和tail），这样双向链表就方便实现O(1)时间内移动节点。这里补充下hash函数和双向链表的的相关知识细节供大家参考，欢迎读者关于这些内容提出问题和意见建议。 首先哈希函数可以将整数或字符串进行映射为特定范围内的整数值(取模运算，字符串作为输入的哈希函数有多种，如简单的将每个字符的ascii相加等），这样就可能存在着不同的输入值映射为相同结果的可能（如15%10和25%10都等于5）。这样不同的输入映射到同一个结果就需要解决冲突问题（hash collision)，解决hash冲突的方法有链式地址法(chaining)和开放寻址法（open addressing）。链式地址法的思想是相同结果的输入(key)所对应的value（基础树类型外也支持任何可扩展的灵活自定义的类型）值存放到该hash函数结果对应的链表中（hash函数的结果值表示的含义是以链表的节点指针类型申请的数组对应的位置的下标索引，hash值所对应的数组位置存放链表的表头）。开放寻址法的思想是通过探查（probe）去按一定的规则继续寻找可能的空闲位置，常见的探查方法有一次探查（linear probing，即索引逐渐加1直至找到），二次探查（quadratic probing，逐渐加2的次方直至找到空闲位置）以及双重哈希（两个哈希函数，第一个用来计算初始映射位置，如出现冲突，则第二函数用来计算索引的搜索步长）。在标准模板库中提供了hash函数std:hash。unordered_map提供了灵活的使用哈希函数的方式，既可以用标准提供的，也可以用自定义的。 双向链表的实现也在这里做一下简要说明，双向链表的每一个节点都会保存两个临近节点的指针，即前驱节点和后继节点（头节点的前驱节点为空，尾节点的后续节点为空，如果是双向循环链表，则首尾相连，头节点的前驱节点为尾节点，尾节点的后继节点为头节点）。在本题中，双向链表的表尾节点为记录最久未访问的key（可以理解为双向链表从表头到表尾按时间先后顺序记录着这些key的访问记录），如果缓存已满，则需要将表尾节点更新为表头节点（key和value值用最近访问的值去更新），表尾的前置节点更新为表尾节点。这里为了直接能访问表尾节点，需要在程序中将表尾节点也作为哨兵节点。如果get的key为中间某个节点，则可以通过hash函数首先找到该节点，并将该节点挪动到表头更新为表头节点，同时也说明当前的key是最近访问的。实现了LRU的按时间排序访问节点的功能，并且由于hash函数的O(1)复杂度特性，也保证了LRU的O(1)访问效率要求。 References

  • 算法实例思路分析-矩阵中严格递增的单元格数

    动态规划的题目需求各异，想法也差别比较大，有时候找出状态转移方程并不是那么容易的事情，需要具体问题具体分析。今天这篇文章将要下大家介绍一种新的基于动态规划解决的题目，并辅以自己的分析思路的阐述过程，欢迎读者基于此提出问题意见和建议。 题目的内容如下：给你一个下标从 1 开始、大小为 m x n 的整数矩阵 mat，你可以选择任一单元格作为 起始单元格 。从起始单元格出发，你可以移动到 同一行或同一列 中的任何其他单元格，但前提是目标单元格的值 严格大于 当前单元格的值。你可以多次重复这一过程，从一个单元格移动到另一个单元格，直到无法再进行任何移动。请你找出从某个单元开始访问矩阵所能访问的 单元格的最大数量 。返回一个表示可访问单元格最大数量的整数。 下面简要阐述一下我的思路分析以及一个不错的参考答案： 可能的思路1：我们先只针对问题本身，而不是提示解决的具体方法去尝试分析问题，我们可以针对矩阵的每个位置(i,j)去找到它的该行和列的可能路径(row[i][j]，为矩阵当前行中比当前单元格mat[i][j]值要大的元素的集合，同理可以找出col[i][j]),矩阵中每个元素找出之后，就可以通过树搜索的方式，找出mat[i][j]所有可能路径中最大的(搜索树中从根节点到叶子节点的最大路径数字，经过简单验证可以得出当前位置在同一行和同一列的candidate中，必然要经过同行或者同列中比它大的最小的值，因为其他大的值可以通过这个值去抵达，因此同行和同列中的大的元素可以增序进行排列，而且可以以一颗二叉树来进行构建搜索树，按行行走为左子树，按列行走为右子树）。但是问题是要针对每个元素去找这样的最大路径，所需要的时间复杂度肯定就比较高。当然也可以不用每个元素都要调用这样的搜索树，可以基于已经搜索出来的和相邻节点的大小关系算出附近节点所能访问的单元格的最大数量。还有基于当前节点去遍历的这颗最大路径和上的路径上的每一个节点的最大值也是确定的（不仅如此，每一个路径节点的值都是最大值）。这样也可以基于此去优化搜索过程。 可能的思路2（参考答案）：基于思路1，可以进行进一步的优化，基于整个矩阵可以建立一颗有向无环图（不一定是树），同一行（列）中按节点顺序构造有向边(如果存在同一行或列有相同值的时候，可以加入一个dummy节点)，然后基于有向无环图（不一定联通，可能有多个分量组成）去找到最长的路径，具体可以用动态规划的算法，后面有时间再介绍详细动态规划实现上的细节。 可能的思路3：基于初始值的多次迭代更新后收敛，比如每个元素位置的初始值可以设为其行和列中比它大的数字的个数的最大值。然后更新的规则是当前行和列中比它大的值的位置对应值里边的最大值加1，不断这个过程直至每个位置对应的结果值不再发生变化。 以上主要从解决思路上分别做了阐述，欢迎读者点评，如有逻辑问题欢迎读者批评指正，或者分享新的解题思路，谢谢。 References