论文部分内容阅读
求矩阵的逆、最短路径问题和求二元关系的传递闭包是科学计算领域中的三个基本问题，它们在计算机科学与工程中有着重要的实践意义。Gaussian消元法、Floyd算法和Warshall算法分别是这三个问题的经典算法。1971年，Carré发现这三个算法在结构上非常相似，并基于半环代数理论提出了它们的统一形式——Gauβ-Jordan消元法。1977年，Carré和Lehmann等抽象出求矩阵的逆、最短路径问题、求二元关系的传递闭包和正则语言的有理表示问题的本质特征，正式提出了代数距离问题。 代数距离问题可以转化为计算半环上的矩阵的正闭包（即其所有正数次幂的和）的问题。本文的主要内容是考虑一类矩阵的正闭包的计算方法。本文首先引入了矩阵圈非负的概念，接着给出了幂等半环上的矩阵圈非负的充分与必要条件以及计算圈非负矩阵的正闭包的方法，再依据该方法设计了时间复杂度为O(n3)的Plus_Closure_ of_ Matrix算法（其中n为矩阵的阶数）。最后，本文还考察了Plus_Closure_of_Matrix算法在若干特殊半环上的应用。 Warshall算法和Floyd算法就是Plus_Closure_of_Matrix算法分别在二元布尔半环和热带半环上的应用。与Floyd算法，Warshall算法和幂等半环上的Gauβ-Jordan消元法相比，Plus_Closure_of_Matrix算法应用范围更广泛，可用于求解某些不具备完全性质和闭性质的幂等半环上的代数距离问题。