幂等半环上矩阵正闭包的一个计算方法

来源 :湖南科技大学 | 被引量 : 0次 | 上传用户:clarkkevin_
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
求矩阵的逆、最短路径问题和求二元关系的传递闭包是科学计算领域中的三个基本问题,它们在计算机科学与工程中有着重要的实践意义。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算法应用范围更广泛,可用于求解某些不具备完全性质和闭性质的幂等半环上的代数距离问题。
其他文献
人脸识别技术是近年来发展最为迅速的技术之一,国内外各种研究机构展开了人脸识别技术的前沿研究和探索,已逐步进入到应用推广阶段。在安防、刑侦、人机交互等领域,人脸识别
随着网络的不断发展和普及,发展迅速的现代网络教育已经成为培养人才、促进科研和教育事业发展的重要途径。现代网络教育最显著的优势在于“五个任何”:任何人、在任何时间、
基于人工智能的计算机动画自动生成技术从动画的设计和制作过程出发,研究由自然语言编写的剧本到最终动画的实现过程,旨在提高动画制作的自动化程度和智能性。虚拟角色作为动
随着计算机网络技术的不断发展,各种管理系统也不断涌现。开发一个基于网络的、具有流程处理的、具备一定管理功能的成绩管理系统是目前学校的普遍需求。  本文分析了目前成
Web服务发现与组合方法己是动态Web服务领域具有挑战的研究热点。目前,服务发现缺乏支持组件的服务质量(QoS),服务组合的匹配算法亦缺乏支持动态重组和保障全局质量。本文针