敬畏自然绿水青山

Category: Basics

  • P2P网络技术简要介绍

    P2P网络是一种网络技术，有很多应用场景都可以用得到，特别是当前流行的区块链技术中P2P技术将作为主要核心的技术支撑，这里先简要对P2P技术做一下相关说明。如有不正确或补充的地方欢迎读者联系指出。 P2P网络中每一台机器即可以用来做客户端，也可以用来做服务器，其中的任何两个节点不需要服务器就可以直接进行通信从而共享资源交换信息。P2P网络是去中心化的，因此也意味着没有一个中央的授权节点来控制和管理资源。 P2P网络可以有多种应用存在形式，这里几个较有影响力的P2P应用，如用于文件分享的BitTorrent, 区块链网络应用比特币（bitcoin等），去中心化的计算标准Matrix，P2P网络技术还可以用于物联网平台。这些系统虽然也都有一些挑战和平衡综合考虑，但是都是在这些应用场景下要优于传统的客户端服务器的网络模式。 libp2p是一个比较健壮的面向P2P应用的开发库，用其开发P2P的应用有如下的几个优势：1、模块化，libp2p基于组件构建，可以面向不同的应用场景去组合不同的组件去构建应用；2、可扩展的网络协议配置，libp2p支持多种传输协议; 3、提供了多种语言实现的网络发现，数据存储和检索模式的代码，方便不同的编程习惯的程序员去构建；4，支持NAT穿越，NAT穿越，以实现不同内网的机器通信，关于NAT Traversal的原理，可以参考引文7；更多的优势可以参考引文8中的说明文字。 这篇短文主要介绍了P2P技术的应用，关键的技术，以及支持P2P应用开发库libp2p。P2P网络技术可以在云平台中进行部署，如Chainmaker就可以在云平台中进行部署。后续有机会将向大家详细介绍具体技术开发的应用细节。 References

  • 动态规划较为简单的两个示例

    动态规划是编程算法里边经常会用到的一种解决问题的思路，这里向大家介绍两个相对比较简单的示例。 示例1：一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。问总共有多少条不同的路径？ 示例2：给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。 其中，第1题中可以将路径数目用二维数组path[m-1][n-1]来表示，path[i][j]就表示为从[0][0]位置起始开始走到[i][j]位置可能的路径。具体的实现方法和代码注释请参考链接。data-structures-algorithms/dp/unique-paths.cpp at main · kindlytree/data-structures-algorithms (github.com) 第2题，假设需要拼接的字符串的长度为s，则可以用一个can_concat[s+1]的数组来标记每一个从开始到index的位置是否可以有字典的单词标记出来。具体代码可以参考链接：data-structures-algorithms/dp/word-break.cpp at main · kindlytree/data-structures-algorithms (github.com)

  • einsum is all you need-einsum函数在数值计算中的应用示例说明

    在深度学习框架和numpy等数值计算库中，记住不同的矩阵计算，如内积（dot products）、外积（outer products）、矩阵转置（transposes ），矩阵和向量相乘，以及矩阵和矩阵的乘法这些运算的函数名称和参数是容易混淆的一件事情，而爱因斯坦和（einsum）是通过一种领域语言（domain-specific language），用一种优雅的方式去解决这个问题，同时更进一步还可以描述更复杂的tensor的操作。 einsum函数采用如下的格式，einsum(equation,operands)，下面为一个模板：result=einsum(“□□,□□□,□□->□□”,arg1,arg2,arg3)。其中□为占位符，表示张量的一个维度，如前面的equation的形式为“□□,□□□,□□->□□”，表示的含义为由三个输入参数，第一个和第三个为矩阵，第二是阶数为3的张量。计算的结果为矩阵。 下面将解释一些使用示例： 其中张量的缩并(tensor contraction)操作是两个多维张量中的分别两个大小相同的维度的内积，具体可以参考链接1中的示例。其中广播操作（broadcast）的实现方式可以参考引文7中的示例说明。 关于示例和相关说明，后面再根据实践会进一步补充更新或进行相关的修正，欢迎读者提出问题意见和建议。 References

  • 回溯算法示例2-n皇后问题

    上次分享过回溯问题的示例数独问题求解，今天向大家介绍一个类似的问题，n皇后问题，问题的来源是国际象棋中的皇后的摆法，两个皇后不能直面水平，垂直，对角线，否则不满足皇后摆放的要求。 这里也采用回溯的思路，假设为8皇后问题，从第一行开始摆放，用变量记录当前摆放行的candidate位置（记为valid_pos_），并且记录从第一行到当前行摆放的位置记录（path，path[i]即为第i行摆放的皇后的位置值）。我们的第一个函数即为根据已经摆放的path（前面已经摆放的行）去获取当前行的candidates，实现逻辑即为针对每一个前面的行的位置，计算其在当前行不可行的位置（竖直，对角线的位置），具体的代码如下。 其中正式的递归回溯过程的示例代码如下： 最后完整串起来的代码为： 完整的代码请参考链接： data-structures-algorithms/backtracking/n-queens.cpp at main · kindlytree/data-structures-algorithms (github.com)

  • 线性方程组求解方法简介

    线性方程组的求解可以有不同的方法，下面理解几种以备后续查阅。 1、拉默法则（Cramer’s Rule）是线性代数中一个关于求解线性方程组的定理，其证明过程见参考文献1。 2、高斯消除法求解线性方程组，将方程组转换为增广矩阵，经过一系列的初等行变换得到了行阶梯矩阵（即上三角矩阵）然后自下至上依次求解即可得到原方程的解。正是由于顺序消去法会因为值过小而引入计算误差，为了减少计算过程中舍入误差对方程组求解的影响，因此是否可以选择绝对值尽可能大的主元作为除数。基于这种思想就有了高斯消去法的改进型：部分主元消去法（Gaussian Elimination with Partial Pivoting）。 3、LU分解在实际应用中，LU分解可以通过Doolittle算法来实现，该算法从下至上对矩阵进行初等行变换，将对角线左下方的元素变成零。这些行变换的效果等同于左乘一系列单位下三角矩阵，这些单位下三角矩阵的乘积就是 ( L ) 矩阵。通过这种方式，可以将原始矩阵 ( A ) 表示为 ( L ) 和 ( U ) 的乘积，从而简化求解过程。 4、更多的方法有jacobi迭代法等，具体可以参考引文4，后续有需要再去做更详细的解释说明。 References

  • 树结构相关算法实例-递归方法遍历路径

    在数据结构这门课程中，树结构是最重要的数据结构之一，有比较多的相关算法，比较有名的有：1、树的递归和非递归遍历；2、二叉搜索树的搜索过程；3、AVL树的构建过程；4、树的深度遍历（DFS）和宽度遍历（BFS）算法；5、其他更多的基于树结构的算法。树结构是图结构的基础，在实际应用中也有很多的问题基于树数据结构去建模。更多树结构的相关算法可以参考本文最后的链接，后面有机会也会进一步补充更多的相关算法。 今天要介绍的是一个树结构的一个中等难度左右的算法，即check一颗二叉树从根节点出发到叶子节点的路径上所有节点的和是否等于一个预先设定的值。 在这里介绍两种思路：1、通过递归遍历树结构找到所有的从根节点到叶子节点的路径，这些路径作为候选，一条一条路径check是否满足条件，如果满足可以将路径打印出来；2、通过递归程序直接判断是否存在这样的路径，这种条件下只返回true或false，不能打印出满足条件的路径。 下面主要介绍第一种算法思路（第二种代码思路请参考本文最后的链接），其主要代码如下所示，这里需要特殊说明的是c++中参数的传递技巧，如下面的代码中，path是普通变量，而all_paths是引用变量。普通变量在每一函数调用时会通过拷贝重新生成一个对象，而引用变量在所有递归调用过程中指向同一个数据变量。 两个算法完整的代码请参考链接： data-structures-algorithms/trees/path-sum.cpp at main · kindlytree/data-structures-algorithms (github.com)

  • 回溯算法示例数独问题求解

    回溯（backtracking）是遍历整个求解空间的一种常见的方式，一些有名的小游戏如数独的解法，八皇后游戏等都可以通过回溯的方法去求解。回溯的思想基本是通过递归进行的实现。这里以一个数独的场景为例向大家介绍一下实现的思路。 首先对数独的尚未填上数字的格子依次从左到右，从上到下的顺序进行填数字尝试，每填写当前的格子，可以按照条件首先筛选出可能的数字，并尝试将这些数字依次进行尝试填到格子里，当可以填写一个候选时，就跳到下一个还未填写数字的格子。如果后来发现下一个未填写的格子没有解（填写数字不能满足数独条件），则尝试下一个候选，如果所有候选都尝试后整个过程还是无解，则返回上一个格子的下一个候选再进行类似的尝试过程。 回溯过程也可以将看成时一个树的搜索过程，比如在数独场景，第一层节点可以看成是第一个格子的所有候选数字节点，回溯的过程是一个动态扩展这棵树的深度优先遍历的过程。如下示例代码显示了其过程，通过递归进行的实现，如果当前填写满足条件则继续下一个格子的填写，如果不满足则当前格子不填（撤回填写的数字）并考虑下一个候选，如果所有的候选都不满足，则退回到上一层搜索的状态继续搜索树的动态构建。 完整示例代码可以参考如下链接。data-structures-algorithms/backtracking at main · kindlytree/data-structures-algorithms (github.com)

  • 几个基本的线代知识点

    这篇文章简要介绍一下线性代数的相关概念知识，如行列式，特征值，特征向量以及特征值分解，SVD分解等。在这里顺便记录一下以便后续查阅。 1、行列式（determinant），矩阵对应一个特定的值，一般记为det(A)，余子式（minor)m_{i,j}一般记为当前矩阵去除i行j列后形成的行列式（由此也可以理解为行列式为递归定义），代数余子式（cofactor）需要在m_{i,j}的基础上再乘上一个因子（-1)^{i+j}形成c_{i,j}。同时有伴随矩阵（adjoint matrix）的概念也是基于代数余子式进行定义的。需要注意，行列式只针对于方阵。 基于伴随矩阵就比较容易计算矩阵的逆。如下所示，也可以看出矩阵的逆要求其行列式不为0。 2、特征值特征向量（也是方阵，对于非方阵来说，是不存在特征值的，但是会存在条件数）：满足特征方程（characteristic equatation）det(A-lamda I)=0的lambda的值即为矩阵的特征值。实对称矩阵的特征向量相互正交。特征值有其对应的代数重数（Algebraic multiplicity），每个特征值有其对应的几何重数（Geometric multiplicity，即为其对应的线性无关的特征向量的个数）。缺陷特征值（defective eigenvalue）指的是存在这个特征值的几何重数比代数重数要小的特征值。关于代数重数大于等于几何重数的相关证明，可以参考引文的链接。 3、特征值分解和SVD分解，可以参考引文3和引文4，其中特征值分解满足方阵，实对称矩阵的特征向量线性无关且为相互正交，PCA就用到了这个特性，SVD分解可以解决不是方阵的情况，但是可以通过转化为特征值分解的方法去进行求解，具体的方法可以参考引文3。特征值的计算方法可以用QR分解来进行。 References

  • QR分解及用其求矩阵特征值方法简介

    QR分解是一种特殊的矩阵分解，将矩阵A(m,n)分解为标准正交矩阵Q(m,n)和上三角矩阵R(n,n)的乘积，QR分解可以用来求矩阵的特征值等应用。 首先解释一下施密特正交化的方法，施密特正交化将n个线性无关的向量转化为标准正交向量，其转化的步骤是首选选一个向量，然后在计算第二个向量时，将原始的第二个向量可以分解为第一个向量和垂直于第一个向量的两个向量的和。而可以利用在同一个方向上的两个向量的内积之比值即为两个向量长度的比值等特性求出第二个向量（和第一个向量垂直），以此同样的类似方法求得第三个向量，第四个向量等等。从而得出施密特正交法的公式。具体公式可以参考引文。 经过施密特正交化的方法可以得出n个标准正交的列向量，而且原始的每一个列向量都可以表示为这n个标准正交列向量的线性组合，根据施密特正交向量的生成特点，原始的列向量的线性组合的线性因子刚好符合上三角矩阵的形式。 第二种算法为Householder transformation，其依次利用列向量和标准正交基形成镜像对称的特征去找到变换的Q的关系，得出Q的特性（对称正交），具体算法请参考引文链接。 QR分解的一个用处就是用来计算矩阵的特征值，具体的原理不做特别说明，如有兴趣可以参考引文链接。下图说明了怎么用numpy基于QR分解去计算矩阵的特征值。 References

  • A*算法简介以二维数字魔方为例

    A*算法又称为启发式搜索算法，是在可能的解空间中，以更少的时间或步骤去找到路径问题答案的一种方法。用到A star算法的场景挺多，如路径规划，二维数字魔方，三维立体颜色魔方（生活中常见的魔方）等等，都可以用A*算法来加快搜索的进度。也是算法基础课中最典型的一个算法，一般要求去用代码实现，并且和原始的穷举式路径搜索，启发式函数的搜索结果（可能有多种不同的启发式函数方法）进行对比。 这里以一个二维数字魔方游戏为例来进行说明，二维数字魔方为一个9宫格，每个格子一个数字，每一个当前的状态可以用一个数字串来描述，数字串的顺序为9宫格从上到下从左到右的顺序进行依次排列而成，0代表空的格子，其邻居的格子可以移动到0这个位置，移动后相当于进行了互换。如“608435127”这个串就代表了一个二维数字魔方的状态，我们一般定义目标状态为“123456780”。要求为从当前状态通过移动方格去达到目标状态。 我们对这个问题进行建模如下，1、状态建模，可以用3*3的二维数组来表示当前状态和目标状态；并且用(x0,y0)表示空的格子（数字0的格子）的坐标，用移动的操作方向来记录移动的操作路径（D表示向下，U表示向上，L表示向左，R表示向右）；2、用g cost代表当前已经搜索到达的路径所需花销，用h cost代表从当前状态到达目标状态预估的（heuristic）的开销，总花销f cost为g cost + h cost。 具体的搜索算法有基于Dijkstra最短路径搜素算法，它从起点开始搜索时，总是优先搜索和展开当前离起点路径最短的节点，直至搜索到目标点时结束搜索。A*算法正是以“优先搜索直觉上方向靠谱的节点”为策略来减少搜索空间达到加速搜索目标点的目的。具体从代码实现上来解释即为：（1）、Dijkstra最短路径搜索算法将上述的g cost的大小作为路径展开的优先级；（2）、A*算法则用g cost + h cost的大小作为路径展开的优先级，使得搜索路径尽可能朝着目标状态的方向去展开。 以上述的二维数字魔方为例进行说明，Dijkstra最短路径搜索算法维护一个优先级队列，存放已经遍历的节点（路径）的代价函数g cost（以最小堆min heap的形式），然后每做一次搜索，就会从堆顶pop出节点并对其successors进行核查，如果没有遍历过，则将其g cost设为当前的g cost+1并push到优先级队列中；这个过程持续直至pop出的节点即为目标节点。 A*算法和Dijkstra最短路径搜索算法大体搜索流程差不多，不同的地方在于代价函数，A*算法的代价函数为g_cost+h_cost，其中g_cost和上述的Dijkstra算法相同，关键在于h_cost的设计，基于此特定问题，有两种特殊的h_cost函数，1为曼哈顿距离（每个魔方方块的位置和其目标位置的横坐标和纵坐标的距离之和），2为魔方单元块和其目标位置不对应的单元块个数。关于启发式函数的特性和设计准则，可以参考引文链接。 我们针对上述的几个搜索算法在借鉴了已有工作和相关思路的基础上提供了完整的代码实现，具体可以参考引文链接。 References